計算機程序設計排序方法研究

朱瑩瑩

（河南師范大學，河南 新鄉(xiāng) 453007）

?

計算機程序設計排序方法研究

朱瑩瑩

（河南師范大學，河南 新鄉(xiāng) 453007）

摘 要：在計算機程序設計的算法中，存在多種排序方法。學習和研究各種排序方法是計算機工作者的重要課題之一。排序作為一種重要的算法，就是將一個數據記錄的隨意排序，重新排成一個按關鍵字排序的序列。文章將會介紹計算機程序設計中幾種常用的排序方法，并對其各種性能進行分析。

關鍵詞：選擇排序；插入排序；合并排序；快速排序；時間復雜度

為了查找方便，通常計算機中的表是按關鍵字排列有序的，因為這樣有序的順序表可以采用查找效率較高的查找方法，提高查找的速度。因此，排序是計算機程序設計中重要的操作。因為待排序記錄的數量往往是不同的，排序時使用的存儲器不同，可將排序方法分為兩大類，內部排序和外部排序。不同排序方法的性能往往存在著很大的差別，有的排序方法是穩(wěn)定的，而有的卻不穩(wěn)定，并且算法復雜性的高低有很大的差別。不言而喻，因此對任意給定的問題，設計出復雜性盡可能低的算法是設計算法時追求的一個重要目標。另一方面，當給定的問題已有多種算法時，選擇其中復雜性最低者，是選用算法時遵循的一個重要準則。因此，算法的復雜性分析對算法設計或選用有著重要的指導意義和實用價值［1］。本文除了給出了每種排序算法在進行排序時所依據的原則，還對其進行了復雜度的分析以及優(yōu)缺點的評價。

1　各種排序方法的分析

1.1 選擇排序

選擇排序（Selection Sort）需要進行多趟比較，每一趟在n-i+1（i=1，2，...，n-1）個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。其中，又分為簡單選擇排序，樹形選擇排序，堆排序。

簡單選擇排序，第i趟要通過n-i次關鍵字之間的比較，從n-i+1個記錄中選取關鍵字最小的記錄，并和第i個記錄進行交換。對含有n個元素的數組，再進行簡單選擇排序，需要進行n-1次的選擇操作。通過分析，能夠得出，當一個數組本來就從小到大有序排列時，記錄只需移動0次，而如果記錄是逆序排列的話，所需移動的次數最多為3（n-1）次。而進行選擇排序時，記錄都需要進行n（n-1）/2次比較，一般情況下，簡單選擇排序的時間復雜度為O（n2）。由上可知，選擇排序關鍵詞之間的比較操作較多，要想進行改進，可以減少關鍵詞之間的比較。

樹形選擇排序（Tree Selection Sort）是對簡單選擇排序一種改進的方法。它的思想是n個關鍵字先兩兩比較。這樣會得出個較小的關鍵字，然后再進行兩兩比較，這樣一直重復進行能夠選出最小的關鍵字。這個過程通常會用含有n個節(jié)結點的完全二叉樹表示。含有n個葉子結點的完全二叉樹的深度是，選擇次小關鍵字需要進行次比較，由此可以得出樹形選擇排序的時間復雜度。這種方法的缺點是輔助存儲空間較多。另一種選擇排序的方法，堆排序（Heap Sort）可以彌補這種缺點，它只需一個記錄大小的存儲空間。排序的過程就是將一個無序的序列建成一個堆，也稱作“篩選”。堆有“大頂堆”和“小頂堆”，排序過程可以使記錄序列按非遞減或非遞增有序隊列。堆排序在最壞的情況下，時間復雜度為O（nlogn）。單堆排序對n較大的文件進行排序有效，當n較小時并不適合，并且堆排序是一種不穩(wěn)定的排序方法。

1.2 快速排序

快速排序（Quick Sort）是對起泡排序方法的一種改進。它的基本思想是，通過一趟排序將代排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字少，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序［2］。快速排序是一種不穩(wěn)定的排序方法。

首先介紹一下起泡排序（Bubble Sort），它是一類基于“交換”進行排序的方法。以將數據從小到大排序為例，其基本思路就是每次將相鄰的兩個數進行比較，每一次排序可將最大的數“沉底”。例如，若有6個數，8，7，5，2，1，4。經過第一趟交換為7，5，2，1，4，8，最大的數8已經“沉底”。每一趟的比較都是使該趟最大的數“沉底”。如果有n個數需要進行n-1趟比較，在第j趟中需要進行n-j次比較。通過對冒泡排序法的排序過程進行分析，冒泡排序在排序過程中只需要一個輔助單元，其空間復雜度為O（1）。它的時間效率與數據的n有關，若數據元素的狀態(tài)保持不變，正序冒泡法的比較次數為n-1，移動次數為0，逆序冒泡法的比較次數為n（n-1）/2，移動次數為3n（n-1）/2［3］。通過分析可知冒泡排序法的平均時間復雜度為O（n2）。

快速排序在排序前需要任意選取一個記錄作為“樞紐”。通常情況下選取第一個記錄，然后將使所有關鍵字比它小的記錄都放在它的位置之前，所有關鍵字比它大的記錄都放在它之后。這樣可以將序列分為兩個子序列，分界線是“樞紐”所在的位置i。整個快速排序的過程可以用遞歸算法來實現，當待排序列中只含有一個記錄時，則該隊列一定是有序的。否則，需要再次進行快速排序，即對分割的兩個子序列進行排序。例如初始序列為49，38，65，97，76，13，27，49。選擇第一個關鍵字為49，經過一次快速排序后變?yōu)椋?7，38，13｝49｛76，97，65，49｝，然后再分別對分割的兩個子序列進行排序，直至排序完成。就平均時間而言，快速排序是目前最好的一種排序方法。當初始記錄序列按關鍵字有序或基本有序時，快速排序將蛻化為冒泡排序。

1.3 插入排序的分析

直接插入排序（Straight Insertion Sort）的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的，記錄數增1的有序表。由于需要查找插入位置，為了避免出界，通常要在首址設置監(jiān)視哨。插入排序也是分趟操作，在第i趟排序時，則從i-1往前搜索來查找合適的插入位置，對n個記錄進行排序，整個排序過程需要進行n-1趟插入。直接插入排序是一種最簡單的排序方法。當被排列的n個記錄序列為正序時，需要的比較次數最少，僅需n-1次，并且不需要移動記錄。最差的情況下需要移動記錄（n+2）（n-1）/2次，移動次數為（n+4）（n-1）/2。通常情況下，記錄是雜亂無章地排列著，可以取上述分析的最差和最好情況下的平均值，易得時間復雜度為O（n2）。

直接插入排序在記錄n的值不大時，易于操作，并且很容易實現，但當n很大時，并不適合使用，由此出現了其他改進的排序方法。從減少比較次數方面考慮，出現了折半查找。2-路插入排序，可以減少排序過程中的記錄的移動次數，但不能避免移動，且所需的輔助存儲空間增多。表插入排序可以通過改變存儲結構，避免移動。希爾排序（Shell’s Sort）與上面所述的幾種改進的插入排序方法相比，在時間效率上又有較大改進。它不是直接對全體記錄進行排序，而是將待排記錄分割為若干個子序列進行排序。子序列的構成也不是簡單的“逐段分割”，其中的記錄都是相隔一定的“增量”。因此在進行一趟插入排序時，關鍵字的記錄可以跳躍式的移動。當序列已經基本有序時，直至最后才進行一次增量為1的插入排序。由于增量序列并且影響著希爾排序的時間復雜度，增量序列的選擇是一個復雜的問題。但是希爾排序從使待排序列按關鍵字“基本有序”和使每次排序時n的取值盡量小兩個方面，對直接插入排序進行了改進。

1.4 合并排序

合并排序（Merging Sort）是一種運用分治策略的思想的算法，它將n個待排序的記錄分成大小大致相同的兩個集合，分別對兩個子集合進行排序，最后將各個排好序的子集合合并成按要求排序的集合，整個算法要通過遞歸調用實現。具體實現過程是：將待排元素一分為二，每個子集繼續(xù)遞歸拆分直到分解到僅一個元素為止，然后兩合并為一個有續(xù)集即完成了排序。因此通過合并排序算法進行排序，在最壞的情況下時間復雜度的計算：

通過解這個方程可以得出T（n）=O（nlogn）。與快速排序相比，合并排序最大的特點就是一種穩(wěn)定的排序算法。

2　排序方法的比較與總結

簡單排序的平均時間為O（n2），最壞情況下也是O （n2），需要輔助的存儲空間是O（1）。快速排序的平均時間是O（nlogn）。最壞情況是O（n2），輔助存儲空間是O （logn）。合并排序的平均時間是O（nlogn），最壞情況下是O（nlogn），需要的輔助存儲空間是O（n）。通過分析不難得出，當待排序的n的值較大時，宜采用合并排序的排序算法，所需時間較省，但是需要的輔助存儲空間較多。快速排序在平均性能上需要的時間最少，但是在最壞的情況下需要的時間較多。當待排序的記錄“基本有序”或者n的值不大時，直接插入排序較簡單，可以認為是最佳的排序方法。它經常和快速排序，合并排序等其他的排序方法一起配合使用。

3　結語

通過對幾種排序方法的分析和比較，不難得出每一種排序方法就其全面性能而言，很難判斷出哪一種方法最好。不同的排序方法有不同的適應場合，應根據具體地實際情況選擇合適的排序方法。在一個程序設計中，方法的選擇可以不局限于一種，為了達到最好的效果，可以多種排序方法配合著使用。在學習每一種排序方法的思想與原理時，深入了解每種算法的精髓，有助于創(chuàng)造出新的合適的算法。

［參考文獻］

［1］王曉東.計算機算法設計與分析［M］.4版北京：電子工業(yè)出版社，2012（2）：15-17.

［2］嚴蔚敏.吳偉民.數據結構，C語言版［M］.北京：清華大學出版社，2007.

［3］張健.計算機程序設計中的排序問題探討［J］.計算機光盤軟件與應用，2014（14）:169-170.

Research of Computer Programming Sorting Methods

Zhu Yingying
（Henan Normal University，Xinxiang 453007，China）

Abstract:In computer programming，algorithms，there are various sorting methods. Learning and research various sorting methods is an important issue for computer workers. As an important sorting algorithm is a data record of arbitrary sorting，re-arranged in a sequence ordered by keywords. In this paper，a computer program will introduce the design of several commonly used sorting method，and to analyze the various properties.

Key words:choose sort；insertion sort；merge sort；quick sort；the time complexity

作者簡介：朱瑩瑩（1995-），女，河南周口；研究方向：計算機算法。