前言
介紹
插入排序
基本知識：
直接插入排序是一種簡單的插入排序法，其基本思想是：
把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列
直接插入排序的特性總結：
- 元素集合越接近有序，直接插入排序算法的時間效率越高
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)，它是一種穩定的排序算法
- 穩定性：穩定
實現
void InsertSort(int*arr,int n)
{for (int i = 1; i < n; i++){int tmp = arr[i];int end = i - 1;while (tmp < arr[end]){arr[end + 1] = arr[end];end--;}arr[end + 1] = tmp;}}
解析：1.外層 for 循環控制遍歷每個待插入的元素，從下標 1 開始（因為下標 0 視為初始的已排序區）
2. tmp 暫存當前要插入的元素。
end 表示已排序部分的末尾元素下標，用來向左比較尋找插入位置。
3.當當前元素 tmp 小于已排序區的元素 arr[end]，說明還沒找到插入位置：
將較大的元素右移一位，給 tmp 騰出空間；
end-- 繼續向左查找。
4.找到插入位置后，將 tmp 放入空出來的位置，即 end + 1。
希爾排序
基本知識：
希爾排序法的基本思想是：先選定一個整數，把待排序文件中所有記錄分成個
組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序。然后，取，重復上述分組和排序的工作。當到達=1時，所有記錄在統一組內排好序
- 希爾排序是對直接插入排序的優化。
- 當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經 接近有序的了，這樣就會很快。
實現
void ShellSort(int*arr,int n)
{ for(int gap = n/2;gap>0;gap/=2){ for(int i = gap;i<n;i++){ int tmp = arr[i];int end = i-gap;while(end>=0 && arr[end]>tmp){arr[end+gap] =arr[end];end -= gap;}arr[end+gap] = tmp;}}
}
解析
for(int gap = n/2;gap>0;gap/=2)
設定初始間隔 gap = n/2，后續每次縮小一半。
這樣每輪都能把當前數組變得更“接近有序”。
最后當 gap == 1 時，其實就是普通的插入排序，但效率更高！
for (int i = gap; i < n; i++)從當前 gap 開始往后遍歷數組。
為啥不是 i=0？因為我們要比較 arr[i] 和它 gap 之前的數，即 arr[i - gap]，所以 i 至少得 ≥ gap。
arr[end + gap] = arr[end];
end -= gap;把大的元素往后挪出一個 gap 的位置。
指針繼續往前 gap 個單位看下一個數。
arr[end + gap] = tmp;
找到該插入的位置了，把 tmp 插進去。
完成一個元素在當前 gap 下的插入排序。
實戰演示
數組排序OJ
解答
void ShellSort(int*arr,int n)
{ for(int gap = n/2;gap>0;gap/=2){ for(int i = gap;i<n;i++){ int tmp = arr[i];int end = i-gap;while(end>=0 && arr[end]>tmp){arr[end+gap] =arr[end];end -= gap;}arr[end+gap] = tmp;}}
}int* sortArray(int* nums, int numsSize, int* returnSize) {int* arr = (int*)malloc(sizeof(int)*numsSize);for(int i = 0;i<numsSize;i++){arr[i]=nums[i];}InsertSort(arr,numsSize);*returnSize = numsSize;return arr;
}
希爾排序總結：
核心思路：先按大?gap?做分組插入排序，逐步縮小?gap?到?1。
時間復雜度：平均?≈?O(n1·3～n1·?)，最壞 O(n2)；效率取決于?gap?序列。
空間復雜度：O(1)?原地排序。
穩定性：不穩定，同值元素位置可能改變。
希爾排序補充
1.反向插排希爾
void HalfShellSort(int* arr, int n)
{int gap = 3;for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[i + gap];while (end >= 0 && arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}arr[end + gap] = tmp;}
}
差異:
for (int i = 0; i < n - gap; i++)
{int end = i;int tmp = arr[i + gap];
}
for(int i = gap;i < n;i++){ int tmp = arr[i];int end = i-gap;}
解釋：
方案一是正常思維以0為起點，即end為主角，end+gap 是tmp的位置，故為了不越界·i<n-gap。
方案二是以第二個gap為i的開始，即tmp為主角，tmp始終是end的后一個gap，所以i<n,不存在越界問題。
2.多重循環希爾
void ShellSort(int* arr, int n)
{for (int gap = n / 2; gap > 0; gap /= 2){for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i+=gap){int tmp = arr[i+gap];int end = i;while (end >= 0 && arr[i] > tmp){arr[end + gap] = arr[end];end -= gap;}arr[end + gap] = tmp;}}}
}
差異：
for (int j = 0; j < gap; j++)for (int i = j; i < n - gap; i+=gap)
for(int i = 0;i<n-gap;i++)
方案一比方案二多了一層循環
原因分析: 方案一是以gap將全部分為gap個集合，每個集合內進行希爾排序。
例如：以gap==3 為例：
分為：0開頭集合，1開頭集合，2開頭集合 以這種形式進行排序。
方案二則是按順序一個一個排。
二者沒有任何區別，時間復雜度和空間復雜度一樣。
堆排序
基本知識：
堆排序即利用堆的思想來進行排序，總共分為兩個步驟：
- 建堆
升序：建大堆
降序：建小堆- 利用堆刪除思想來進行排序
堆的復習
向上調整函數（AdjustUp）
向下調整函數（AdjustDown）
堆插入
實現
1.建堆
方案一：
void AdjustUp(int* arr,int child)
{int parent = (child - 1) / 2;while (child>0){if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}void HeapSort(int*arr,int n)
{for (int i = 1; i < n; i++){AdjustUp(arr, i);}
}
類似于堆插入，從第二個數組中元素開始插入，調整。
方案二：
void AdjustDown(int* arr, int n, int parent)
{int child = 2 * parent + 1;while (child < n){if (child + 1 < n && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}void HeapSort(int*arr,int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr,n,i);}
}
i == (n-1-1)/2 是尾（最后）葉子的父節點。
向下調整建堆的原理是：
從最后一個非葉子節點開始，逐個對子樹進行向下調整，把局部小堆變成大堆，逐層向上構造，最終整個數組就成了一個大堆結構。
總結：
方法一：向上調整（AdjustUp）
從第1個元素往后掃，每插入一個元素就“向上冒泡”一次，維護堆
時間復雜度：O(n log n)
方法二：向下調整（AdjustDown）
從最后一個非葉子節點開始，逐個節點向下調整整個子樹
最終堆頂就是整個數組的最大值（如果建大堆）
時間復雜度：O(n) 更優！
2.排序
void HeapSort(int*arr,int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr,n,i);}int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);end--;}
}
排序如圖所示。
1.交換根和尾葉子，把大數放在后面。
2.向下調整，在形成大根堆。
3.循環往復。
總結
八大排序我們學了三個，其余的將逐漸補充豐富。
