世界熱門:各種常見排序算法實現 常見排序算法匯總

各種常見排序算法實現

排序算法算是最為簡單經典的算法問題了，因此從這個開始學習記錄，以加深印象。

(資料圖片僅供參考)

其中常見的排序算法有：

選擇排序冒泡排序插入排序合并排序快速排序堆排序

以上排序算法一定無法羅列全部排序算法的大家族，但是暫且討論以上的算法。

選擇排序和冒泡排序屬于蠻力解決問題的表現； 插入排序則使用減治法； 合并排序和快速排序使用分治法； 堆排序使用變治法。

選擇排序

蠻力法去解決排序問題沒有那么多彎彎道，選擇排序的思路：

n個元素，先找到最小的元素，然后將它交換到它該在的位置，對于升序來說即第一個位置，然后第一個元素就是有序元素了，隨后再將從剩下的n-1個尋找最小的元素，放到第二個位置上，以此類推，交換n-1次就可以得到一個有序的集合了。

實現代碼

int ChooseSort(arr* a) {//使用選擇排序//輸入：無序元素列表//輸出：成功返回1，失敗返回0for (int i = 0; i < a->length - 1; i++) {int min = i;for (int j = i; j < a->length; j++) {if (a->ite[min] > a->ite[j]) {min = j;}}if (!Swap(a, i, min)) {return 0;}}return 1;}

冒泡排序

冒泡排序很形象，過程也和冒泡一樣，思路：

從第一個元素開始，比較相鄰元素，若是有序，則不變，若是無序，則交換相鄰元素，這樣做的結果就是會將最大的元素給“頂”到最后一個位置，接著將上述過程在前n-1個元素中重復。以此類推，最后就會得到一個有序的集合。

代碼實現：

int BubbleSort(arr * a){//使用冒泡排序得到有序列表//輸入：無序元素的列表//輸出：成功返回1，失敗返回0for (int i = a->length; i > 0; i--) {for (int j = 0; j < i-1; j++) {if (a->ite[j] > a->ite[j + 1]) {if (!Swap(a, j, j + 1)) return 0;}}}return 1;}

插入排序

記得第一次看到插入排序，書上是拿撲克牌舉例的，思路：

我們先認為列表的第一個元素是有序的，那么拿起第二個元素，尋找在前面第一個元素的合適的位置，插進去，現在有序的集合元素就變成兩個了。以此類推，第三個找到合適的位置插入，一直到第n個元素，這樣，就得到了有序元素的集合。

代碼實現：

int InserSort(arr * a){//使用插入排序//輸入：無序元素的列表//輸出：返回1for (int i = 1; i < a->length; i++) {for (int j = 0; j < i; j++) {if (a->ite[j] >= a->ite[i]) {int temp = a->ite[i];for (int k = i - 1; k >= j; k--)a->ite[k + 1] = a->ite[k];a->ite[j] = temp;}}}return 1;}

合并排序

合并排序是使用遞歸的思路來做的，也即上文提到的分治法。思路：

將其中每一個元素都看作為有序的集合，雖然每個集合只有一個元素，然后將兩個有序集合合并成一個，依次合并，最終就生成了最后的有序集合。

代碼實現：

int MergeSort(arr * a){//使用合并排序//輸入：無序元素列表//輸出：成功返回1if (a->length > 1) {arr *a1 = Cut(a, 0, a->length / 2 - 1);arr *a2 = Cut(a, (a->length / 2), a->length - 1);MergeSort(a1);MergeSort(a2);arr* b = Merge(a1, a2);for (int i = 0; i < b->length; i++) {a->ite[i] = b->ite[i];}a->length = b->length;free(a1); free(a2); free(b);}return 1;}

這是上述代碼中Merge函數，即合并有序集合的函數:

arr * Merge(arr * a1, arr * a2){//合并過程，將兩個有序列表合并成一個有序列表，并釋放這兩個有序列表內存//輸入：兩個有序列表//輸出：一個有序列表arr *a = (arr*)malloc(sizeof(arr));a->length = 0;int i, j, k;for (i = 0, j = 0, k = 0; i < a1->length && j < a2->length; k++) {if (a1->ite[i] > a2->ite[j]) {a->ite[k] = a2->ite[j];j++;}else{a->ite[k] = a1->ite[i];i++;}a->length++;}if (i == a1->length) {for (; j < a2->length; j++, k++) {a->ite[k] = a2->ite[j];a->length++;}}else{for (; i < a1->length; i++, k++) {a->ite[k] = a1->ite[i];a->length++;}}return a;}

快速排序

快速排序與前面的合并排序一樣，也用到了遞歸的思想。但是在實際實現上與合并排序有很大的不同，合并排序在實現上傾向于合并上，即將每個有序元素集合合并成一個更大的有序元素集合。快速排序則是劃分與交換，從線性集合的兩端開始，選取基準數，用基準數將整個集合劃分為兩個區間，左邊全部是比基準數小的數，右邊全部是比基準數大的數。然后通過分治法繼續劃分下去，而劃分則是通過交換來實現。

代碼實現：

int QuickSort(arr * a, int l, int m){//實現快速排序算法//輸入：無序元素列表a，列表開始區間坐標和結束區間坐標//輸出：成功返回1int s;if (l < m) {s = PartPostion(a, l, m);QuickSort(a, l, s-1);QuickSort(a, s+1, m);}return 1;}

其中的ParPosition函數如下：

int PartPostion(arr* a, int l, int m) {//實現快速排序算法中的劃分區間//輸入：無序元素列表a，列表開始區間坐標和結束區間坐標//輸出：作為中軸的下標int i = l, j = m;int key = a->ite[l];while (i < j) {while (key > a->ite[i] && i < m) {i++;}while (key < a->ite[j]) {j--;}Swap(a, i, j);}Swap(a, i, j);Swap(a, i, j);return j;}

堆排序

堆排序顧名思義，用到了堆，最大堆就是一棵完全二叉樹，其中的每一個節點的值都要大于其子女的值。

堆排序的具體思路正是用到了這個最大堆：

使用這些數構造一個最大堆，然后刪除堆的最大鍵。以此類推，便可得到有序元素的集合。其中刪除最大鍵的操作其實就是刪除最大堆的根，先將根與堆最后的元素進行交換，然后刪除最后的元素，即交換后的根，然后把此時在根上的那個小數再拉下來，讓大數頂上去即可。

代碼實現：

int HeapSort(arr * a){//使用堆排序的算法排序//輸入：無序元素列表//輸出：成功返回1int size = a->length;BuildHeap(a, size);while (size != 1) {Swap(a, 0, size - 1); size--;BuildHeap(a, size);}return 1;}

以上實現的BuildHeap函數如下，作用為構造最大堆：

int BuildHeap(arr* a, int size) {//構造一個最大堆//輸入：要轉化成最大堆的無序元素列表和要生成最大堆的規模//輸出：成功返回1for (int n = size/2; n > 0; n--)for (int i = size - 1; i > 0; i--)if (a->ite[(i - 1) / 2] < a->ite[i]) Swap(a, (i - 1) / 2, i);return 1;}

這里我使用了從底而上的構建堆的方法。

總結

這些排序前三個思路都比較簡單，尤其是前兩個蠻力法的選擇排序與冒泡排序。那兩個分治法的排序方法還是不太行，合并排序感覺上要比快速排序好懂點，快速排序在通過交換來劃分區間的方法感覺還是不太理解，剩下的堆排序感覺上也比較簡單。