常用排序演算法之C++實現

4 人贊了文章

所謂排序就是把集合中的數據元素按照它們的關鍵字的非遞減或非遞增序排成一個序列。

假定在待排序的集合中存在多個關鍵字值相同的數據元素。經過排序後，這些數據元素的相對次序保持不變，則這種排序方式是穩定的，否則是不穩定的。

由於數據元素的形式、數量和所存放的存儲設備不同，排序所採用的方法也不相同。按照排序過程中數據存儲的存儲設備的不同，排序可以分為內排序和外排序。內排序是指被排序的數據元素全部存放在計算機的內存中，並且在內存中調整數據元素的相對位置。它適合於數據元素個數較少的情況。外排序是指在排序的過程中，數據元素主要存放在外存儲器中，藉助於內存出奇逐步調整數據元素之間的相對位置。它適合於數據元素個數很多，不可能講所有的數據元素全部放入內存的情況。

根據排序採用的手段，可以將內排序分為插入排序、選擇排序、交換排序和歸併排序。本文將順序介紹各排序演算法及其C++實現形式。

1. 插入排序
2. 選擇排序
3. 交換排序
4. 歸併排序

1. 插入排序

每次將一個待排序的數據元素，按其關鍵字大小，插入到前面已經排好序的一組數據元素中的適當位置上，直到所有的元素全部插入為止。將一個元素插入到前面已排序序列中的過程稱為一趟排序。

如何將一個元素插入到一個有序序列有很多方法。根據在已經排好序的有序數據元素序列中尋找插入位置的不同方法，可以將插入排序進一步分為直接插入排序、二分插入排序和希爾排序。

1.1 直接插入排序

直接插入排序是適合於少量數據元素的簡單排序演算法。如果只有少量的數組元素需要排序，直接插入排序是一個很好的解決辦法，因為它的演算法非常簡短。但是如果要處理大量的數據，那麼直接插入排序會因為太費時而成為一個糟糕的選擇。

該演算法時間複雜度為 。

template <class T>void simpleInsertSort(T a[], int size){ int k; T tmp; for(int j = 1; j < size: j++) { tmp = a[j]; for(k = j - 1; a[j] < a[k] && k >= 0; --k) a[k+1] = a[k]; a[k+1] = tmp; }}

1.2 二分插入排序（暫略）

1.3 希爾排序（暫略）

2. 選擇排序

選擇排序是一種很簡單的排序演算法。假定共有個待排序的元素。首先，從這個元素中選出關鍵字最小的元素。再從剩下的 個元素中選出其中關鍵字最小的元素，即整個序列之次小的元素。以此類推，每次從剩下的元素序列中挑出關鍵字最小的元素，直至序列中最後只剩下一個元素為止。這樣，把每次得到的元素排成一個序列，就得到了按非遞減序列排列的排序序列。

2.1 直接選擇排序

直接選擇排序不是一個穩定的排序方法，該演算法時間複雜度為 。

template <class T>void simpleSelectSort(T a[], int size){ T tmp; int i, j, k; // k記錄選擇過程中最小元素的位置 for(i = 0; i < size - 1; ++i) { k = i; for(j = i + 1; j < size; ++j) if(a[j] < a[k]) k = j; tmp = a[i]; a[i] = a[k]; a[k] = tmp; }}

2.2 堆排序（暫略）

3. 交換排序

交換排序就是根據序列中兩個數據元素的比較結果來確定是夠要交換兩個數據元素在序列中的位置。交換排序的特點是：通過交換，將關鍵值較大的數據元素向序列的尾部移動，關鍵值較小的數據元素向序列的頭部移動。常用的交換排序有冒泡排序和快速排序。

3.1 冒泡排序

又稱起泡排序。其思想是，從頭到尾比較相鄰的兩個元素，將小的換到前面，大的換到後面。經過了從頭到尾的一趟比較，就把最大的元素交換到了最後一個位置。這個過程稱為一趟氣泡。然後在從頭開始到倒數第二個元素進行第二趟氣泡。經過了第二趟比較，又將第二大的元素放到了倒數第二個位置... ...以此類推，經過第趟氣泡，將倒數第個大的元素放入第二個單元。此時，最小的元素就放在了第一個單元，完成排序。冒泡排序是穩定的演算法。

該演算法時間複雜度為 。

template <class T>void BubbleSort(T a[], int size){ int i, j; T temp; bool flag; // 記錄一趟氣泡中有沒有發生過交換 for(i = 1; i < size; ++i) // (size-1) 次起泡 { flag = false; for(j = 0; j < size - i; ++j) if(a[j+1]<a[j]) { temp = a[j]; a[j+1] = a[j]; a[j+1] = temp; flag = true; } if(!flag) break; }}

3.2 快速排序

顧名思義，快速排序是一種較快的排序演算法。事實也確實如此。目前快速排序依然被認為是一種最快的內排序演算法。

快速排序的基本思想是，在待排序的序列中選擇一個數據元素，以該元素為標準，將所有數據元素分為兩組，使得第一組數據元素均小於或等於標準元素，第二組數據元素均大於標準元素。將第一組數據元素放在數組前面部分，第二組數據元素放在數組的後面部分，標準元素放在中間。這個位置就是標準元素的最終位置。這稱為一趟劃分。然後對分成的兩組數據重複上述過程，直到所有的元素都在適當位置為止。

很明顯，快速排序演算法是一個遞歸演算法。在一次劃分後，標準元素已在正確的位置上。除標準元素以外的其他元素被分成兩組，再分別對它們用快速排序演算法進行排序。除了遞歸之外，要實現快速排序還有兩個要解決的問題。一個是如何選擇標準元素，第二個是如何實現高效的劃分。一般假設採用第一個元素作為標準元素。

平均情況下快速排序的時間性能是 。

template<class T>void quickSort(T a[], int low, int high){ int mid; if(low >= high) return; mid = divide(a, low, high); quickSort(a, low, mid - 1); quickSort(a, mid + 1, high);}

上述函數原型和其他排序演算法的函數原型都不同，它包含兩個用於控制遞歸終止的參數。為了和其他排序演算法一致起來，在它外面再加一個包裹函數，該函數調用了遞歸的quickSort函數。如下代碼所示。

template<class T>void quickSort(T a[], int size){ quickSort(a, 0, size - 1);}

最後一個工具函數是劃分函數。劃分函數的實現如下。、

template <class T>int divide(T a[], int low, int high){ T k = a[low]; do { while(low < high && a[high] >= k) --high; if(low < high) { a[low] = a[high]; ++low; } while(low < high && a[low] <=k) ++low; if(low < high) { a[high] = a[low]; --high; } }while(low != high)}

4. 歸併排序

歸併排序的思想來源於合併兩個已排好序的有序表。如果A、B分別是兩張待歸併的表，由於A、B都是有序的，因此只要從兩表的表頭開始：順序比較表頭元素，小者移入另一表C中。反覆如此，直至其中一表為空為止，將另一表中剩餘元素自左至右複製到表C的剩餘位置。

歸併排序的時間性能是 ，但從空間上看，在歸併時它需要額外的空間。

函數 merge() 將數組 a 中的從 left 到 mid-1 之間的有序序列和從 mid 到 right 之間的有序序列進行歸併，歸併後的結果仍然放回數組 a 的 left 到 right 之間。該函數用了一個臨時數組 tmp 存放歸併的結果。歸併結束後再將臨時數組的內容複製回數組 a 。

歸併兩個有序序列，merge() 代碼如下。

template<class T>void merge(T a[], int left, int mid, int right){ T* tmp = new T[right - left + 1]; int i = left, j = mid, k = 0; while(i < mid && j <= right) { if(a[i] < a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } while(i < mid) temp[k++] = a[i++]; while(j<=right) temp[k++] = a[j++]; for(i = 0, k = left; k <= right;) a[k++] = tmp[i++]; delete[] tmp;}

歸併排序法就是利用遞歸和歸併實現排序。它的主要思想是，如果只有一個元素，那麼該元素就是一個已排好序的序列，排序結束；否則，對前一半和後一半分別遞歸調用歸併排序函數進行排序，將排好序的兩個序列歸併起來，就完成了整個序列的排序。代碼如下。

template<class T>void mergeSort(T a[], int left, int right){ int mid = (left + right) / 2; if(left == right) return; mergeSort(a, left, mid); mergeSort(a, mid + 1, right); merge(a, left, mid + 1, right);}

為了使歸併排序的函數原型和其他排序演算法保持一致，再給它加一個包裹函數，如下所示。

template<class T>void mergeSort(T a[], int size){ mergeSort(a, 0, size-1);}

至此，常用的排序演算法已介紹完畢。推薦網站visualgo，幫助初學者對演算法實現進行直觀的理解，本文的圖也來源於此。本文以C++演算法實現為主，輔之以演算法思想。若仍對某些演算法的思想仍不太明確，可以自行通過網站或者書籍學習。

學習數據結構和演算法，還是多練多思考，希望大家共同進步~

參考文獻 |《數據結構：思想與實現》高等教育出版社

圖 | @河馬

推薦閱讀：