作者 | 李肖遙
來源 | 技術讓夢想更偉大
冒泡排序
簡介
冒泡排序是因為越小的元素會經由交換以升序或降序的方式慢慢浮到數列的頂端，就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名冒泡排序。
複雜度與穩定性
思路原理
以順序為例
從第一個元素開始一個一個的比較相鄰的元素，如果第一個比第二個大即a[1]>a[2]，就彼此交換。從第一對到最後一對，對每一對相鄰元素做一樣的操作。此時在最後的元素應該會是最大的數，我們也稱呼一遍這樣的操作為一趟冒泡排序。針對所有的元素重複以上的步驟，每一趟得到的最大值已放在最後，下一次操作則不需要將此最大值納入計算。持續對每次對越來越少的元素，重複上面的步驟。直到所有的數字都比較完成符合a[i]<a[i+1]，即完成冒泡排序。
圖示過程
以數組數據{ 70,50,30,20,10,70,40,60}為例：
如圖，每一次排序把一個最大的數被放在了最後，然後按照這個趨勢逐漸往前，直到按從小到大的順序依次排序。
到了第4輪的時候，整個數據已經排序結束了，但此時程序仍然在進行。
直到第5，6，7輪程序才算真正的結束，這其實是一種浪費算力的表現。
主要代碼實現
void bubble_sort(int a[],int n) {for(int i=0; i<n; i++) {for(int j=0; j<n-i; j++) {if(a[j]>a[j+1]) { swap(a[j],a[j+1]); //交換數據 } } }}
注意，由於C++的namespace std命名空間的使用，std自帶了交換函數swap(a,b)，可以直接使用，其功能是交換a與b的兩個值，當然你可以自定義swap函數，其模板代碼為：
template<class T> //模板類，可以讓參數為任意類型void swap(T &a,T &b) {T c(a); a=b; b=c;}
或者指定類型修改為整形，如：
void swap(int &a, int &b) { //指定類型int temp = a; a = b; b = temp;}
選擇排序
簡介
選擇排序是一種簡單直觀的排序算法，它從待排序的數據元素中選出最小或最大的一個元素，存放在序列的起始位置，然後再從剩餘的未排序元素中尋找到最小或最大元素，然後放到已排序的序列的末尾。以此類推，直到全部待排序的數據元素的個數為零。
複雜度與穩定性
過程介紹（以順序為例）
首先設置兩個記錄i和j，i從數組第一個元素開始，j從(i+1)個元素開始。接著j遍歷整個數組，選出整個數組最小的值，並讓這個最小的值和i的位置交換。i選中下一個元素(i++)，重複進行每一趟選擇排序。持續上述步驟，使得i到達(n-1)處，即完成排序 。
圖示過程：
以數據{2,10,9,4,8,1,6,5}為例
如圖所示，每次交換的數據使用紅顏色標記出，已經排好序的數據使用藍底標註，
每一趟從待排序的數據元素中選出最小的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。
我們只需要進行n-1趟排序即可，因為最後剩下的一個數據一定是整體數據中最大的數據。
代碼實現
void select_sort(int a[],int n){int temp;for(int i=0;i<n-1;i++){ temp=i; //利用一個中間變量temp來記錄需要交換元素的位置for(int j=i+1;j<n;j++){if(a[temp]>a[j]){ //選出待排數據中的最小值 temp=j; } } swap(a[i],a[temp]); //交換函數 }}
相比冒泡排序的不斷交換，簡單選擇排序是等到合適的關鍵字出現後再進行交換，並且交換一次就可以達到一次冒泡的效果。
插入排序
簡介
插入排序是一種最簡單的排序方法，對於少量元素的排序，它是一個有效的算法。
複雜度與穩定性
過程介紹
首先將一個記錄插入到已經排好序的有序表中，從而一個新的、記錄數增1的有序表。
每一步將一個待排序的元素，按其排序碼的大小，插入到前面已經排好序的一組元素的適當位置上去，直到元素全部插入為止。
可以選擇不同的方法在已經排好序數據表中尋找插入位置。根據查找方法不同，有多種插入排序方法，下面要介紹的是直接插入排序。
每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序。第一趟比較前兩個數，然後把第二個數按大小插入到有序表中；第二趟把第三個數據與前兩個數從後向前掃描，把第三個數按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以後就完成了整個排序過程。
圖示過程
以數組數據{ 70,50,30,20,10,70,40,60}為例：
將紅色的數據依次插入組成一個逐漸有序的數組
代碼實現
void insert_sort(int a[],int n) {int i,j;//外層循環標識並決定待比較的數值for(i=1; i<n; i++) { //循環從第2個元素開始if(a[i]<a[i-1]) {int temp=a[i];//待比較數值確定其最終位置for(j=i-1; j>=0 && a[j]>temp; j--) { a[j+1]=a[j]; } a[j+1]=temp;//此處就是a[j+1]=temp; } }}
希爾排序
簡介
希爾排序又稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。
希爾排序是非穩定排序算法，在對幾乎已經排好序的數據操作時，效率極高，即可以達到線性排序的效率。
複雜度與穩定性
過程介紹
先將整個待排序的記錄序列分組，對若干子序列分別進行直接插入排序，隨著增量逐漸減少即整個序列中的記錄「基本有序」時，再對全體記錄進行依次直接插入排序。
過程如下：
選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；按增量序列個數 k，對序列進行 k 趟排序；每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
圖示過程
可以看見，相比直接插入排序由於可以每趟進行分段操作，故整體效率體現較高。
主要代碼實現
void shellSort(int arr[], int n) {int i, j, gap;for (gap = n / 2; gap > 0; gap /= 2) {for (i = 0; i < gap; i++) {for (j = i + gap; j < n; j += gap) {for (int k = j; k > i && arr[k] < arr[k-gap]; k -= gap) { swap(arr[k-gap], arr[k]); } } } }}
堆排序
簡介
堆排序是指利用堆這種數據結構所設計的一種排序算法，它是一個近似完全二叉樹的結構。
同時堆滿足堆積的性質：即子結點的鍵值或索引總是小於或大於它的父節點。
複雜度與穩定性
什麼是堆？
由於堆排序比較特殊，我們先了解一下堆是什麼。
堆是一種非線性的數據結構，其實就是利用完全二叉樹的結構來維護的一維數組，利用這種結構可以快速訪問到需要的值，堆可以分為大頂堆和小頂堆。
大頂堆：每個結點的值都大於或等於其左右孩子結點的值小頂堆：每個結點的值都小於或等於其左右孩子結點的值
過程介紹
首先把待排序的元素按照大小在二叉樹位置上排列，且要滿足堆的特性，如果根節點存放的是最大的數，則叫做大根堆，反之就叫做小根堆了。
根據這個特性就可以把根節點拿出來，然後再堆化下，即用父節點和他的孩子節點進行比較，取最大的孩子節點和其進行交換，再把根節點拿出來，一直循環到最後一個節點，就排序好了。
由於堆的實現圖解需要很長篇幅，故這裡不畫圖，肖遙會單獨出一篇堆的圖解，感謝關注。其代碼實現如下。
主要代碼實現
/* Function: 交換交換根節點和數組末尾元素的值*/void Swap(int *heap, int len) {int temp;
temp = heap[0]; heap[0] = heap[len-1]; heap[len-1] = temp;}
/* Function: 構建大頂堆 */void BuildMaxHeap(int *heap, int len) {int i,temp;for (i = len/2-1; i >= 0; i--) {if ((2*i+1) < len && heap[i] < heap[2*i+1]) { /* 根節點大於左子樹 */ temp = heap[i]; heap[i] = heap[2*i+1]; heap[2*i+1] = temp;/* 檢查交換後的左子樹是否滿足大頂堆性質 如果不滿足 則重新調整子樹結構 */if ((2*(2*i+1)+1 < len && heap[2*i+1] < heap[2*(2*i+1)+1]) || (2*(2*i+1)+2 < len && heap[2*i+1] < heap[2*(2*i+1)+2])) { BuildMaxHeap(heap, len); } }if ((2*i+2) < len && heap[i] < heap[2*i+2]) { /* 根節點大於右子樹 */ temp = heap[i]; heap[i] = heap[2*i+2]; heap[2*i+2] = temp;/* 檢查交換後的右子樹是否滿足大頂堆性質 如果不滿足 則重新調整子樹結構 */if ((2*(2*i+2)+1 < len && heap[2*i+2] < heap[2*(2*i+2)+1]) || (2*(2*i+2)+2 < len && heap[2*i+2] < heap[2*(2*i+2)+2])) { BuildMaxHeap(heap, len); } } }}
歸併排序
簡介
歸併排序是建立在歸併操作上的一種有效，穩定的排序算法，該算法是採用分治法的一個非常典型的應用，其核心思想是將兩個有序的數列合併成一個大的有序的序列。
複雜度與穩定性
註：歸併排序需要創建一個與原數組相同長度的數組來輔助排序
過程介紹
首先將已有序的子序列合併，得到完全有序的序列，即先使每個子序列有序，再使子序列段間有序。
過程如下：
申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列設定兩個指針，最初位置分別為兩個已經排序序列的起始位置比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置重複步驟c直到某一指針超出序列尾將另一序列剩下的所有元素直接複製到合併序列尾
圖示過程
第一次排序將數據分為「兩個」一組，組內順序，其次再逐個的將各組進行整合，最終完成歸併排序
主要代碼實現
void merge(int arr[],int l,int mid,int r) {int aux[r-l+1];//開闢一個新的數組，將原數組映射進去for(int m=l; m<=r; m++) { aux[m-l]=arr[m]; }
int i=l,j=mid+1;//i和j分別指向兩個子數組開頭部分
for(int k=l; k<=r; k++) {if(i>mid) { arr[k]=aux[j-l]; j++; } else if(j>r) { arr[k]=aux[i-l]; i++; } else if(aux[i-l]<aux[j-l]) { arr[k]=aux[i-l]; i++; } else { arr[k]=aux[j-l]; j++; } }}
void merge_sort(int arr[],int n) {for(int sz=1; sz<=n; sz+=sz) {for(int i=0; i+sz<n; i+=sz+sz) { //i+sz防止越界//對局部：arr[i...sz-1]和arr[i+sz.....i+2*sz-1]進行排序 merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1)); //min函數防止越界 } }
}
快速排序
簡介
快速排序在1960年提出，是考察次數最多的排序，無論是在大學專業課的期末考試，還是在公司的面試測試題目中，快速排序都極大的被使用，在實際中快速排序也極大的被使用。
複雜度與穩定性
過程介紹
通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
在數組中選擇一個基準點分別從數組的兩端掃描數組，設兩個指示標誌從後半部分開始，如果發現有元素比該基準點的值小，就交換位置然後從前半部分開始掃描，發現有元素大於基準點的值，繼續交換位置如此往復循環，然後把基準點的值放到high這個位置,排序完成以後採用遞歸的方式分別對前半部分和後半部分排序，當前半部分和後半部分均有序時該數組就自然有序了。
圖示過程
可以看出，在第四趟時已經達到順序，但是仍然還是會繼續計算幾趟直到完成全部運算
主要代碼實現
void qucik_sort(int a[],int low,int high) {int i,j,temp; i=low; j=high;if(low<high) { temp=a[low]; //設置樞軸while(i!=j) {while(j>i&&a[j]>=temp) { --j; }if(i<j) { a[i]=a[j]; ++i; }
while(i<j&&a[i]<temp) { ++i; }if(i<j) { a[j]=a[i]; --j; } } a[i]=temp; qucik_sort(a,low,i-1); qucik_sort(a,i+1,high); }}
計數排序
簡介
計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。作為一種線性時間複雜度的排序，計數排序要求輸入的數據必須是有確定範圍的整數。
計數排序算法不是基於元素比較，而是利用數組下標來確定元素的正確位置。
它的優勢在於在對一定範圍內的整數排序時，它的複雜度為Ο(n+k)，快於任何比較排序算法。
當然這是一種犧牲空間換取時間的做法，而且當O(k)>O(n*log(n))的時候其效率反而不如基於比較的排序。
複雜度與穩定性
過程介紹
找出待排序的數組中最大和最小的元素統計數組中每個值為i的元素出現的次數，存入數組C的第i項對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1
圖示過程
如下圖，A為待排序的數組，C記錄A中各個值的數目。
將C[i]轉換為值小於等於i的元素個數。
為數組A從後向前的每個元素找到對應的B中的位置，每次從A中複製一個元素到B中，C中相應的計數減一。
當A中的元素都複製到B中後，B就是排序好的結果，如圖所示。
代碼實現
#include<stdio.h>#include<stdlib.h>#include<string.h>
void CountSort(int *arr, int len){if(arr == ) return;int max = arr[0], min = arr[0];for(int i = 1; i < len; i++){if(arr[i] > max) max = arr[i];if(arr[i] < min) min = arr[i]; }int size = max - min + 1;int *count =(int*)malloc(sizeof(int)*size);memset(count, 0, sizeof(int)*size);
for(int i = 0; i < len; i++) count[arr[i] - min]++;//包含了自己！for(int i = 1; i < size; i++) count[i] += count[i - 1];
int* psort =(int*)malloc(sizeof(int)*len);memset(psort, 0, sizeof(int)*len);
for(int i = len - 1; i >= 0; i--){ count[arr[i] - min]--;//要先把自己減去 psort[count[arr[i] - min]] = arr[i]; }
for(int i = 0; i < len; i++){ arr[i] = psort[i]; }
free(count);free(psort); count = ; psort = ;}
void print_array(int *arr, int len){for(int i=0; i<len; i++)printf("%d ", arr[i]);printf("\n");}
int main{int arr[8] = {2, 5, 3, 0, 2, 3, 0, 3}; CountSort(arr, 8); print_array(arr, 8);
return 0;}
桶式排序
簡介
桶排序也稱箱排序，原理是將數組分到有限數量的桶子裡。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序）。
桶排序是鴿巢排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序並不是 比較排序，他不受到 O(n log n) 下限的影響。
複雜度與穩定性
過程介紹
根據待排序集合中最大元素和最小元素的差值範圍和映射規則，確定申請的桶個數；遍歷待排序集合，將每一個元素移動到對應的桶中；對每一個桶中元素進行排序，並移動到已排序集合中。
圖示過程
元素分布在桶中：
然後，元素在每個桶中排序：
代碼實現
#include<iterator>#include<iostream>#include<vector>using namespace std;const int BUCKET_NUM = 10;
struct ListNode{ explicit ListNode(int i=0):mData(i),mNext{} ListNode* mNext; int mData;};
ListNode* insert(ListNode* head,int val){ ListNode dummyNode; ListNode *newNode = new ListNode(val); ListNode *pre,*curr; dummyNode.mNext = head; pre = &dummyNode; curr = head;while(!=curr && curr->mData<=val){ pre = curr; curr = curr->mNext; } newNode->mNext = curr; pre->mNext = newNode;return dummyNode.mNext;}
ListNode* Merge(ListNode *head1,ListNode *head2){ ListNode dummyNode; ListNode *dummy = &dummyNode;while(!=head1 && !=head2){if(head1->mData <= head2->mData){ dummy->mNext = head1; head1 = head1->mNext; }else{ dummy->mNext = head2; head2 = head2->mNext; } dummy = dummy->mNext; }if(!=head1) dummy->mNext = head1;if(!=head2) dummy->mNext = head2;
return dummyNode.mNext;}
void BucketSort(int n,int arr[]){ vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));for(int i=0;i<n;++i){ int index = arr[i]/BUCKET_NUM; ListNode *head = buckets.at(index); buckets.at(index) = insert(head,arr[i]); } ListNode *head = buckets.at(0);for(int i=1;i<BUCKET_NUM;++i){ head = Merge(head,buckets.at(i)); }for(int i=0;i<n;++i){ arr[i] = head->mData; head = head->mNext; }}
基數排序
簡介
基數排序是透過鍵值的部份資訊，將要排序的元素分配至某些「桶」中，藉以達到排序的作用，在某些時候，基數排序法的效率高於其它的穩定性排序法。
複雜度與穩定性
圖示過程
設有一個初始序列為: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。
過程介紹
任何一個阿拉伯數，它的各個位數上的基數都是以0~9來表示的。所以我們不妨把0~9視為10個桶。
我們先根據序列的個位數的數字來進行分類，將其分到指定的桶中。分類後，我們在從各個桶中，將這些數按照從編號0到編號9的順序依次將所有數取出來。得到的序列就是個位數上呈遞增趨勢的序列。按照上圖個位數排序：{50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。接下來對十位數、百位數也按照這種方法進行排序，最後就能得到排序完成的序列。
主要代碼實現
public class RadixSort {// 獲取x這個數的d位數上的數字// 比如獲取123的1位數，結果返回3public int getDigit(int x, int d) {int a = {1, 1, 10, 100}; // 本實例中的最大數是百位數，所以只要到100就可以了return ((x / a[d]) % 10); }public void radixSort(int[] list, int begin, int end, int digit) { final int radix = 10; // 基數int i = 0, j = 0;int count = new int[radix]; // 存放各個桶的數據統計個數int bucket = new int[end - begin + 1];// 按照從低位到高位的順序執行排序過程for (int d = 1; d <= digit; d++) {// 置空各個桶的數據統計for (i = 0; i < radix; i++) { count[i] = 0; }// 統計各個桶將要裝入的數據個數for (i = begin; i <= end; i++) { j = getDigit(list[i], d); count[j]++; }// count[i]表示第i個桶的右邊界索引for (i = 1; i < radix; i++) { count[i] = count[i] + count[i - 1]; }// 將數據依次裝入桶中// 這裡要從右向左掃描，保證排序穩定性for (i = end; i >= begin; i--) { j = getDigit(list[i], d);// 求出關鍵碼的第k位的數字， 例如：576的第3位是5 bucket[count[j] - 1] = list[i];// 放入對應的桶中，count[j]-1是第j個桶的右邊界索引 count[j]--; // 對應桶的裝入數據索引減一 }// 將已分配好的桶中數據再倒出來，此時已是對應當前位數有序的表for (i = begin, j = 0; i <= end; i++, j++) {list[i] = bucket[j]; } } }public int sort(int[] list) { radixSort(list, 0, list.length - 1, 3);return list; }// 列印完整序列public void printAll(int[] list) {for (int value : list) { System.out.print(value + "\t"); } System.out.println; }public static void main(String[] args) {int array = {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}; RadixSort radix = new RadixSort; System.out.print("排序前:\t\t"); radix.printAll(array); radix.sort(array); System.out.print("排序後:\t\t"); radix.printAll(array); }}
總結
10種排序算法對比，我們了解到了各種排序的原理及優缺點，記住任何一種排序都不是十全十美的，因此在我們實際應用中，最好的方式就是揚長避短。