前言
兜兜轉轉，一晃年關將至。時間證明了一個道理，學啥忘啥，學的越快忘得越快，還不如踏踏實實寫點筆記心得來的實在。
編程初學期間，排序算法是讓人抓頭最多的一塊。為什么我連最簡單的冒泡排序都理解不了，我是不是不選錯專業了，很多人會有這樣的疑問，然后就有人做gif冒泡懵逼排序，別說，還挺形象的。
其實排序算法這塊，著急不得，這個排序算法不會就換一個排序算法來學，總有一種排序算法你能夠理解的，等需要用到排序的時候，你只要會一種就可以了。
在這里我列舉了7中常見的排序算法并用C語言實現，你們可能就要問了，不是十種嗎？怎么還能缺斤短兩，不是我不會寫啊，是寫起來麻煩，你們也用不到后面那幾種，跟別說去研究了，能看懂常見的七種排序算法你就能在學校里橫著走了。
后臺回復【排序算法】可以拿到全部代碼
目錄
相信大家最熟悉的就是冒泡排序了，這個我就不多說
直接上動圖演示原理，外加代碼實現冒泡排序：
C語言代碼實現：
void BubbleSort(int arr[], int n){//從小到大排序 相鄰來兩個數比較，將大的數字往后放for (int i = 0; i < n - 1; i++) //n-1是因為數組下標最大為n-1 要進行10輪比較{//n-1是因為數組下標最大為n-1 要進行10次比較，再減i是因為每最后的i個元素已經有序不需要繼續排序for (int j = 0; j < n - 1 - i; j++){if (arr[j] > arr[j + 1]) //兩兩比較，將小的數據放前面{swap(arr, j + 1, j); //交換arr數組arr[j+1]和arr[j]的值}}}}//交換函數后面就不列舉了，凡是swap都是下面代碼實現的void swap(int arr[], int x, int y){int temp = arr[x];arr[x] = arr[y];arr[y] = temp;}
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾，重復操作。
動圖演示原理，外加代碼實現選擇排序：
C語言代碼實現：
void SelectSort(int arr[], int n){for (int i = 0; i < n - 1; i++){for (int j = i + 1; j < n; j++){if (arr[i] > arr[j]){swap(arr, i, j); //交換arr數組arr[i]和arr[j]的值}}}}
插入排序的代碼實現雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應該是最容易理解的，就是將未排序的數字插入到已排序的數列中。
動圖演示原理，外加代碼實現插入排序：
C語言代碼實現：
void InsertSort(int arr[], int n){int tempVal;for (int i = 1, j; i < n; i++){tempVal = arr[i]; //保存要插入的值for (j = i - 1; tempVal < arr[j] && j >= 0; --j) //數據往后移動，給要插入的值騰位{arr[j + 1] = arr[j];}arr[j + 1] = tempVal; //插入數據}}
快速排序由于涉及到遞歸，理解起來難度是最大的，但是如果你靜下心來獨自對一組數組用快速排序的原理進行排序就能夠很快的理解它，也能夠理解遞歸的原理。
動圖演示原理，外加代碼實現選擇排序：
C語言代碼實現：
void QuickSort(int arr[], int left, int right){if (left >= right) return; //只有一個元素不排int i = left, j = right;while (i < j){while (i < j&&arr[j] >= arr[left]) //從右向左找第一個小于arr[left]的數--j;while (i < j&&arr[i] < arr[left]) //從左向右找第一個大于等于arr[left]的數++i;if (i < j)swap(arr, i, j);}QuickSort(arr, left, i - 1);//排左邊QuickSort(arr, i + 1, right);//排右邊}
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。插入排序是將未排序的數字插入到已排序數列中，而希爾排序是將一個已排序的數列插入到另一個已排序的數列中。
示意圖演示原理，外加代碼實現希爾排序：
C語言代碼實現：
void ShellSort(int arr[], int n){int tempVal, j;int jump = n >> 2; //步長值while (jump != 0){for (int i = jump; i < n; i++){tempVal = arr[i]; //保存待排序的第一個數，也就是待插入的數for (j = i - jump; j >= 0 && tempVal < arr[j]; j -= jump){arr[j + jump] = arr[j];}arr[j + jump] = tempVal;}jump = jump >> 1; //步長值減半}}
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。
示意圖演示原理，外加代碼實現歸并排序：
C語言代碼實現：
void MergeSort(int arr[], int left, int right){if (left >= right)//遞歸的終止條件，left == right證明這個區間只有一個元素，不需要再拆了return;int mid = ((right - left) >> 1) + left;//求中點MergeSort(arr, left, mid); //拆分左MergeSort(arr, mid + 1, right); //拆分右//并操作_merge_in_arr(arr, left, mid, right);}void _merge_in_arr(int arr[], int left, int mid, int right){int length = right - left + 1; //定義一個輔助的空間的長度int *pData = (int*)malloc(sizeof(int)*length);//分配一個動態內存來調整元素的位置memset(pData, 0, sizeof(int)* length);//合并int low = left; //左邊區間的起始下標int hig = mid + 1; //右邊區間的起始下標int index = 0; //輔助數組的下標while (hig <= right)//右區間沒有合并完{while (low <= mid && arr[low] <= arr[hig])//證明左區間沒有合并完，且左區間的值小于右區間的值{pData[index] = arr[low]; //把左邊的值放進輔助數組low++; //左邊往高位移，下一次需要判斷左邊的新下標index++; //下一次放進輔助數組的新下標}if (low > mid) //證明左區間已經放完break;while (hig <= right && arr[low] > arr[hig])//證明右區間沒有合并完，且左區間的值大于右區間的值{pData[index] = arr[hig]; //把右邊的值放進輔助數組hig++; //右邊往高位移，下一次需要判斷右邊的新下標index++; //下一次放進輔助數組的新下標}}//到這一步，證明起碼有一個區間已經合并完成if (hig <= right) //證明右邊沒有完成memmove(&pData[index], &arr[hig], sizeof(int)* (right - hig + 1));if (low <= mid) //證明左邊沒有完成memmove(&pData[index], &arr[low], sizeof(int)* (mid - low + 1));//把所有區間都合并到了輔助區間memmove(&arr[left], pData, sizeof(int)* length);free(pData); //釋放空間}
桶排序是典型的空間換時間，在對整數排序中，沒有什么算法能比它還快，但是在空間浪費上，它是祖宗。
示意圖演示原理，外加代碼實現桶排序：
C語言代碼實現：
void radix_sort(int arr[], size_t len){int**temp = (int **)malloc(sizeof(int) * 10); //10行//申請動態內存 輔助數組temp[10][];for (int i = 0; i < 10; i++){temp[i] = (int *)malloc(sizeof(int)*len);}for (int i = 1; i <= 100; i *= 10)//循環數值可能有的位數{for (int x = 0; x < 10; ++x)//輔助數組行循環{for (int y = 0; y < len; ++y)//輔助數組列循環{temp[x][y] = -1;//輔助數組的初始化賦值，-1表示在arr里面不可能出現的數值}}//arr數組中的元素放入輔助數組for (int m = 0; m < len; ++m){int index = (arr[m] / i) % 10;temp[index][m] = arr[m];}//把輔助數組的內容放回待排序數組int k = 0;//待排序的下標for (int x = 0; x < 10; x++){for (int y = 0; y < len; ++y){if (temp[x][y] != -1)arr[k++] = temp[x][y];}}}//釋放內存for (int i = 0; i < 10; i++){free(temp[i]);}free(temp);}
續
算法復雜度
這個算法的復雜度純理論，我就放到最后來講
一個時間復雜度，一個空間復雜度
一個穩定，一個不穩定
推薦閱讀
本公眾號全部原創干貨已整理成一個目錄，點擊「干貨」即可獲得。
后臺回復「進群」，即可加入技術交流群，進群福利：免費贈送Linux學習資料。
