引言：本章簡潔的講解一下數據結構中的幾個常見的排序 ，作復習之用，后面可能會補一些其他的排序?。并給出一些小編學習中遇到的坑，作借鑒。
1.直接插入排序
直接插入排序是一種簡單直觀的排序算法，其基本思想是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。
易寫錯的地方：?
1.?循環邊界問題
// 錯誤：可能導致數組越界 for(i = 0; i < n; i++) // 應改為 i < n-1原因：
當?i?達到?n-1?時，end?為?n-1，此時?a[end+1]?即?a[n]，會訪問數組越界。正確寫法：
for(i = 0; i < n-1; i++) // 循環到 n-2，確保 end+1 <= n-1
2.?待插入元素保存位置錯誤
錯誤寫法：
在循環內部錯誤更新?tmp?的值。// 錯誤：每次循環都重新賦值 tmp while(end >= 0) {int tmp = a[end+1]; // 錯誤：應在循環外保存一次... }原因：
tmp?應在每次外層循環開始時保存當前待插入的元素，而非在循環內部重復賦值。正確寫法：
// 正確：在循環外保存待插入元素 int tmp = a[end+1]; while(end >= 0) {... }
3.?插入位置錯誤
錯誤寫法：
插入操作位置錯誤，導致元素覆蓋。// 錯誤：可能覆蓋未處理的元素 a[end] = tmp; // 應改為 a[end+1] = tmp原因：
當?while?循環結束時，end?指向的是第一個小于等于 tmp 的元素，因此?tmp?應插入到?end+1?位置a[end+1] = tmp; // 插入到正確位置
?【示范代碼】
//直接插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++)//循環邊界是 n-1,防止越界{//單趟排序int end = i; //end是數組下標int tmp = a[end+1]; //tmp是數組元素//保存a[i+1]while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];//向后移位--end;}else{break;}}a[end + 1] = tmp;//將tmp放在正確的位置}
}2.希爾排序
希爾排序（Shell Sort）是插入排序的一種改進版本，也被叫做縮小增量排序。和直接插入排序比起來，它的效率更高，主要是通過將原始數據分成多個子序列來減少元素移動的次數，不過子序列的劃分并非簡單地逐段分割，而是依據特定的增量來進行。
希爾排序的核心思路是：先將整個待排序的記錄序列分割成若干個子序列，分別對這些子序列進行直接插入排序。隨著增量逐漸減小，子序列的長度越來越大，整個序列會變得越來越接近有序。當增量減至 1 時，整個序列就會被合并為一個，再進行一次直接插入排序，此時排序完成。
【示范代碼】?
插入排序 --- 希爾排序
void ShellSort(int* a, int n)
{int gap = n;//gap = gap/3+1;while (gap > 0){gap /= 2;for (int i = 0; i + gap < n; 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;}}}
3.選擇排序
選擇排序（Selection Sort）是一種簡單直觀的排序算法，它的基本思想是每一輪從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完(同時它也是最爛的排序)
【示范代碼】?
//選擇排序 同時選出大和小 a.
void DSelectSort(int* a, int n)
{int left = 0, right = n - 1;while (left < right){int mini = left, maxi = left;for (int i = left+1; i <= right; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[left], &a[mini]);if (left == maxi){maxi = mini;}Swap(&a[right], &a[maxi]);left++;right--;}
}//選擇排序 -- 只選出小的進行交換 b.
void SSelectSort(int* a, int n)
{int left = 0;while(left < n){int min = left;for (int i = left; i < n; i++){if (a[min] > a[i]){min = i;}}Swap(&a[left], &a[min]);left++;}
}
4.堆排序
堆排序（Heap Sort）是一種基于二叉堆數據結構的高效排序算法，它利用堆的特性進行排序，時間復雜度為 O (n log n)，且是一種原地排序算法（空間復雜度 O (1)）。
易寫錯的地方：
- AdjustDown 函數中的條件判斷
在AdjustDown函數里，要判斷右孩子是否存在，同時還要比較左右孩子的大小。要是這一步沒處理好，可能會造成數組越界。if (child + 1 < n && a[child] < a[child + 1])
- 建堆的起始位置
建堆得從最后一個非葉子節點開始，也就是(n-1-1)/2。要是起始位置搞錯了，堆的性質就無法保證。for (int i = (n - 1 - 1) / 2; i >= 0; --i)
- 交換元素和調整范圍
在排序階段，每次把堆頂元素和當前未排序部分的末尾元素交換之后，要對剩余元素重新進行調整。此時，調整范圍會逐步減小。Swap(&a[end], &a[0]); AdjustDown(a, end, 0); // 注意這里是end，而不是n
【示范代碼】?
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 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)
{//建大堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a,n,i);}//向下調整排序int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);end--;}}5.冒泡排序
冒泡排序（Bubble Sort）是一種簡單直觀的排序算法，它重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成（具有教學意義）
【示范代碼】?
// 交換排序
//冒泡排序
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){for (int i = 0; i < n - j - 1; i++){if (a[i] > a[i + 1]){Swap(&a[i], &a[i + 1]);}}}
}6.快速排序
快速排序（QuickSort）是一種基于分治（Divide and Conquer）策略的排序算法，由托尼?霍爾（Tony Hoare）于 1959 年提出。它通過選擇一個 “基準值”（Pivot），將數組分成兩部分，一部分的元素都比基準值小，另一部分都比基準值大，然后遞歸地對這兩部分進行排序，最終實現整個數組有序。
6.1 快速排序的簡單寫法
//快速排序 -- 遞歸 最簡單的一種寫法
void QuickSort(int* a, int left, int right)
{if (left >= right)return;int end = right, begin = left;//單趟排序int keyi = left;while (left < right){//右邊先走 找小while(left < right && a[right] >= a[keyi]){right--;}//找大while(left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;//遞歸循環QuickSort(a, begin,keyi-1);QuickSort(a, keyi+1,end);}6.2 優化取值
?6.21優化方式 1 -- 三數取中
1.什么是三數取中？ 2.為什么要三數取中？
1.1?三數取中（Median of Three）是快速排序的一種優化策略，核心思想是在當前排序區間中選取左端、右端、中間位置的三個元素，比較它們的值后選擇中間值作為基準值（Pivot）。
例如，對于數組區間arr[low...high]，計算中間位置mid = low + (high - low) / 2，比較arr[low]、arr[mid]、arr[high]，將中間值與區間左端（或右端）元素交換，使基準值位于區間邊界，再進行常規的快速排序分區操作。
2.1避免最壞情況
傳統快速排序若直接選擇固定端點（如左端）作為基準值，在數組已排序或接近排序時會退化為最壞時間復雜度O(n2)（每次分區極度不平衡）。
三數取中能顯著降低基準值為極值的概率，使分區更平衡，平均時間復雜度趨近于理想的O(n log n)。
2.2. 減少極端數據影響
對于存在大量重復元素或有序性較強的數組，三數取中可有效避免基準值偏向某一端，提升算法穩定性。
2.3. 實現簡單高效
僅需額外 3 次元素比較和 1 次交換操作，代價極低，卻能大幅優化基準值的選擇
6.22 優化方式2 -- 隨機取值
隨機取值（Random Pivot）是另一種基準值優化策略，具體做法是在當前排序區間內隨機選擇一個元素作為基準值，通常通過生成隨機索引（如randomIndex = low + rand() % (high - low + 1)）實現。
6.3 三種快速排序的三種優化的方法（三數取中）
a.hoare 霍爾
//a.霍爾//hoare
int Part1(int* a, int left, int right)
{int midi = GetMidNumi( a, left, right);if (midi != left){Swap(&a[midi], &a[left]);}int keyi = left;while (left < right){while (left < right && a[right] >= a[keyi]){right--;}while(left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;return keyi;}? ?b.挖坑法?
//b.挖坑法
int Part2(int* a, int left, int right)
{ int midi = GetMidNumi( a, left, right);if (midi != left){Swap(&a[midi], &a[left]);}int key = a[left];int hole = left;while (left < right){while (left < right && a[right] >= key)right--;a[hole] = a[right];hole = right;while(left < right && a[left] <= key)left++;a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}c. 前后指針?
//c.前后指針法
int Part3(int* a, int left, int right) {int midi = GetMidNumi(a, left, right);if (midi != left){Swap(&a[midi], &a[left]);}int keyi = left;int slow = left;int fast = left + 1;while (fast <= right){if(a[fast] < a[keyi] && ++slow!= fast){Swap(&a[fast], &a[slow]);}fast++;}Swap(&a[slow], &a[keyi]);keyi = slow;return keyi;}void QuickSort(int* a, int left, int right)
{if (left >= right)return;//int keyi = Part1(a, left, right);//int keyi = Part2(a, left, right);int keyi = Part3(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}7.歸并排序
歸并排序（Merge Sort）是一種基于分治思想的高效排序算法，由約翰?馮?諾伊曼（John von Neumann）于 1945 年提出。它將數組分成兩個子數組，分別對這兩個子數組進行排序，然后將排好序的子數組合并成一個最終的有序數組。
?【示范代碼】?
//歸并排序
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}void _MergeSort(int* a, int begin, int end, int* tmp)
{// 1. 遞歸終止條件if (begin >= end)return;// 2. 分割數組int mid = (begin + end) / 2;// [begin, mid] [mid+1,end]，子區間遞歸排序_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);// 3. 合并兩個已排序子數組// [begin, mid] [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++];}// 4. 將臨時數組結果復制回原數組memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
