---

前言

所謂排序算法，即通過特定的算法因式將一組或多組數據按照既定模式進行重新排序。這種新序列遵循著一定的規則，體現出一定的規律，因此，經處理后的數據便于篩選和計算，大大提高了計算效率。對于排序，我們首先要求其具有一定的穩定性，即當兩個相同的元素同時出現于某個序列之中，則經過一定的排序算法之后，兩者在排序前后的相對位置不發生變化。換言之，即便是兩個完全相同的元素，它們在排序過程中也是各有區別的。今天，我們介紹一下常見的排序算法。

---

一.直接插入排序

插入排序思想

插入排序算法是基于某序列已經有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大于該最大元素，則可直接插入最大元素的后面即可，否則再向前一位比較查找直至找到應該插入的位置為止。插入排序的基本思想是，每次將1個待排序的記錄按其關鍵字大小插入到前面已經排好序的子序列中，尋找最適當的位置，直至全部記錄插入完畢。執行過程中，若遇到和插入元素相等的位置，則將要插人的元素放在該相等元素的后面，因此插入該元素后并未改變原序列的前后順序。我們認為插入排序也是一種穩定的排序方法。

插入排序代碼實現

void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){int end = i;int tmp = a[end+1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

插入排序總結

直接插入排序的特性總結：

1. 元素集合越接近有序，直接插入排序算法的時間效率越高
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)，它是一種穩定的排序算法
4. 穩定性：穩定

二.希爾排序

希爾排序思想

希爾排序的思想實際上是將數列一次又一次的預排序，讓數組趨近于有序，之后在進行插入排序得到答案。預排序就是先將數組中的數進行分組，將相隔gap距離的樹分為一組，在一組中進行插入排序使之有序，再將gap逐漸縮小，最后gap等于1時，就是插入排序。通過分組的方法可以讓后面的數更快的來到前面，讓前面的數更快的來到后面。但是gap越大，越不接近有序，gap太小效率提高就不明顯，所以經過前人的多次實驗得到，當gap處于gap=gap/3+1動態變化中時效率較高。

希爾排序代碼實現

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n-gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end = end - gap;}else{break;}}a[end + gap] = tmp;}}}

希爾排序總結

希爾排序的特性總結：

1. 希爾排序是對直接插入排序的優化。
2. 當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就
   會很快。這樣整體而言，可以達到優化的效果。我們實現后可以進行性能測試的對比。
3. 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，一般認為是O（n^1.5）
4. 穩定性：不穩定

三.選擇排序

選擇排序思想

選擇排序的思想比較簡單，首先我們需要遍歷一遍數組，找到最小的值，再將最先的值與第一個值交換，這樣就排好了第一個數。以此類推，遍歷后面的數組，再找最小的數，與前面交換，最后有序。我們也可以升級一下，遍歷一次數組，找到最大最小的兩個數，最小的放前面，最大的放后面。但是要注意當你交換完最小的數后，最大的那個數可能位置會變化，要單獨討論。

選擇排序代碼實現

void SelectSort(int* a, int n)
{int right = n - 1;int left = 0;for (right = n - 1, left = 0; right > left; left++, right--){int maxi = right;int mini = left;for (int i = left; i <= right; i++){if (a[mini] > a[i]){mini = i;}if (a[maxi] < a[i]){maxi = i;}}Swap(&a[left], &a[mini]);if (maxi == left){maxi = mini;}Swap(&a[maxi], &a[right]);}
}

選擇排序總結

1. 直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)
4. 穩定性：不穩定

四.堆排序

堆排序思想

堆排序首先就是建堆，我們通過從倒數第二層開始向下調整建堆。如果排升序就建大堆，排降序建小堆。以升序為例，我們通過建堆在根節點得到最大的數，再將最大的數與最后的數交換位置，最大的數就排好了，再通過建堆找第二大的數，最后有序。

堆排序代碼實現

void AdjustDown(HPDataType* a, int n, int parent)
{int child = 2 * parent + 1;while (child < n){if (child+1<n && a[child] > a[child + 1]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{int i = 0;for (i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);end--;AdjustDown(a, end+1, 0);}}

堆排序總結

堆排序的特性總結：

1. 堆排序使用堆來選數，效率就高了很多。
2. 時間復雜度：O(N*logN)
3. 空間復雜度：O(1)
4. 穩定性：不穩定

五、冒泡排序

冒泡排序思想

冒泡排序算法是把較小的元素往前調或者把較大的元素往后調。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據比較結果和算法規則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。冒泡排序的基本思想是，首先將第1個和第2個記錄的關鍵字比較大小，如果是逆序的，就將這兩個記錄進行交換，再對第2個和第3個記錄的關鍵字進行比較，依次類推，重復進行上述計算，直至完成第(n一1)個和第n個記錄的關鍵字之間的比較，此后，再按照上述過程進行第2次、第3次排序，直至整個序列有序為止。排序過程中要特別注意的是，當相鄰兩個元素大小一致時，這一步操作就不需要交換位置，因此也說明冒泡排序是一種嚴格的穩定排序算法，它不改變序列中相同元素之間的相對位置關系。

冒泡排序代碼實現

void BubbleSort(int* a, int n)
{int j = 0, i = 0;for (j = 0; j < n ; j++){for (i = 0; i < n - j - 1; i++){if (a[i] > a[i + 1]){int tmp = a[i];a[i] = a[i + 1];a[i + 1] = tmp;}}}
}

冒泡排序總結

冒泡排序的特性總結：

1. 冒泡排序是一種非常容易理解的排序
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)
4. 穩定性：穩定

六、快速排序

快速排序思想

快速排序采用的是分治思想，即在一個無序的序列中選取一個任意的基準元素pivot，利用pivot將待排序的序列分成兩部分，前面部分元素均小于或等于基準元素，后面部分均大于或等于基準元素，然后采用遞歸的方法分別對前后兩部分重復上述操作，直到將無序序列排列成有序序列。

快速排序算法通過多次比較和交換來實現排序，其排序流程如下：
1、首先設定一個分界值，通過該分界值將數組分成左右兩部分。
2、將大于或等于分界值的數據集中到數組右邊，小于分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小于分界值，而右邊部分中各元素都大于或等于分界值。
3、然后，左邊和右邊的數據可以獨立排序。對于左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。
4、重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序后，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成后，整個數組的排序也就完成了。

快速排序代碼實現

void QiuckSort(int* a, int left, int right)
{if (left >= right){return;}int keyi = left;int begin = left, end = right;while (end > begin){while(end > begin && a[end] >= a[keyi]){end--;}while (end > begin && a[begin] <= a[keyi]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[begin], &a[keyi]);QiuckSort(a, left, begin - 1);QiuckSort(a, begin + 1, right);
}

快速排序總結

1. 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
2. 時間復雜度：O(N*logN)
3. 空間復雜度：O(logN)
4. 穩定性：不穩定

七.歸并排序

歸并排序思想

歸并排序是建立在歸并操作上的一種有效，穩定的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

歸并操作的工作原理如下：
第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
重復步驟3直到某一指針超出序列尾
將另一序列剩下的所有元素直接復制到合并序列尾

歸并排序代碼實現

void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end){return;}int mid = (begin + end) / 2;_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a+begin, tmp+begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc");return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp == NULL;
}

歸并排序總結

歸并排序的特性總結：

1. 歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
2. 時間復雜度：O(N*logN)
3. 空間復雜度：O(N)
4. 穩定性：穩定

---

總結

以上就是今天要講的內容，本文僅僅簡單介紹了幾種常見的排序算法，實際上還有計數排序，桶排序等許多排序算法。如果喜歡這篇文章，期待你的一鍵三連。