---

排序圖片就不貼了吧

排序

什么是排序

以下部分動圖來自CSDN

::: tip 穩定性的概念

定義：能保證兩個相等的數，經過排序之后，其在序列的前后位置順序不變。（A1=A2，排序前A1在A2前面，排序后A1還在A2前面）

意義：穩定性本質是維持具有相同屬性的數據的插入順序，如果后面需要使用該插入順序排序，則穩定性排序可以避免這次排序。
:::

排序的分類

1. 冒泡

1.1 冒泡排序

• 一個一個往上冒

:::details 查看代碼

func BubbleSort(arr []int) []int {n := len(arr)for i := 0; i < n-1; i++ {for j := i + 1; j < n; j++ {if arr[i] > arr[j] {arr[i], arr[j] = arr[j], arr[i]}}}return arr
}

for(int i=0; i<k-1; i++)for(int j=i+1; j<k; j++){if(arr[j]<arr[i]){ // 從小到大arr[i] ^= arr[j];arr[j] ^= arr[i];arr[i] ^=arr[j];}}

:::

1.2. 快速排序

• 升級版冒泡（遞歸）

• 基本思想

通過一趟排序將待排的數據分割成兩部分，其中一部分的數據均比另一部分的數據要小，對兩組數據進行排序。

:::details 查看代碼

func QuickSort(a []int) []int {n := len(a)if n <= 1 {return a}left := make([]int, 0)right := make([]int, 0)guard := a[0]for i := 1; i < n; i++ {if a[i] < guard {left = append(left, a[i]) // 比哨兵小入左隊} else {right = append(right, a[i]) // 其他入大隊}}left, right = QuickSort(left), QuickSort(right)res := append(append(left, guard), right...)return res
}

// 左閉右開
func QuickSort1(a []int, left, right int) {if left >= right-1 {return}low := lefthigh := right - 1guard := a[low]for low < high {/*小的往左，大的往右*/for low < high && a[high] >= guard {high--}a[low] = a[high]for low < high && a[low] <= guard {low++}a[high] = a[low]}a[low] = guardQuickSort1(a, left, low)QuickSort1(a, low+1, right)
}

void q_sort(int a[], int left, int right){
// left, right 左閉右開， low、high閉區間
// a[left] 即左邊第一個元素為哨兵if(left >= right-1 ) return;int low = left, high = right-1, center = a[low];// 直到low==high 確保左邊的元素都比右邊的小while( low < high ){// 從右邊開始往回搜索，找到第一個比哨兵小的元素,比哨兵大則跳過while( low<high && a[high] >= center ) high --;// 將比哨兵小的元素移動到左邊a[low] = a[high];// 從左邊往右邊搜索， 找到第一個比哨兵大的元素，比哨兵小則跳過while( low< high && a[low] <= center) low++;// 將比哨兵大的元素移動到右邊a[high] = a[low];}// 把哨兵存入分界線位置a[low] = center;			// == a[high] = center;// 開始遞歸快排q_sort(a, left, low);		// 左邊q_sort(a, low+1, right );	// 右邊
}

快排優化版的簡單示意圖(以 3 5 2 1 6作為局部數組為例)

:::

2. 選擇

2.1 簡單選擇排序

• 選擇最小的往前放

:::details 查看代碼

func SelectSort(a []int) []int {n := len(a)for i := 0; i < n-1; i++ {minIndex := ifor j := i + 1; j < n; j++ {if a[j] < a[minIndex] {minIndex = j}}if minIndex != i {a[minIndex], a[i] = a[i], a[minIndex]}}return a
}

// 從小到大 
for(int i=0; i<length-1; i++){minIndex=i;for(int j=i+1; j<length{if(arr[j]<arr[minIndex]) minIndex=j; // 選擇最小的元素的下標}if( minIndex != i){arr[i]^=arr[minIndex];arr[minIndex] ^=arr[i];arr[i] ^= arr[minIndex];}
}

• 這里有一個小小的優化技巧

在搜索最小數下標的時候，同時搜索最大數的下標，可以使得復雜度減半。

:::

2.2 堆排序

::: details 先來了解下堆的相關概念：

堆是具有以下性質的完全二叉樹：

每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆；

或者每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆。

如下圖：

同時，我們對堆中的結點按層進行編號，將這種邏輯結構映射到數組中就是下面這個樣子

該數組從邏輯上講就是一個堆結構，我們用簡單的公式來描述一下堆的定義就是：

大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] (小到大排序)

小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] （大到小排序）

:::

:::details 堆的百度百科
堆（heap）是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。

堆總是滿足下列性質：

• 堆中某個結點的值總是不大于或不小于其父結點的值；
• 堆總是一棵完全二叉樹。

:::details 完全二叉樹

• 完全二叉樹的特點：
  • 葉子結點只能出現在最下層和次下層，且最下層的葉子結點集中在樹的左部。

需要注意的是，滿二叉樹肯定是完全二叉樹，而完全二叉樹不一定是滿二叉樹

• 判斷一棵樹是否是完全二叉樹的思路

1>如果樹為空，則直接返回錯

2>如果樹不為空：層序遍歷二叉樹

2.1>如果一個結點左右孩子都不為空，則pop該節點，將其左右孩子入隊列；

2.1>如果遇到一個結點，左孩子為空，右孩子不為空，則該樹一定不是完全二叉樹；

2.2>如果遇到一個結點，左孩子不為空，右孩子為空；或者左右孩子都為空，且則該節點之后的隊列中的結點都為葉子節點，該樹才是完全二叉樹，否則就不是完全二叉樹.
:::

了解了這些定義。接下來看看堆排序的基本思想及基本步驟：

• 堆排序基本思想及步驟

基于選擇排序

堆排序的基本思想是：將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。將其與末尾元素進行交換，此時末尾就為最大值。然后將剩余n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反復執行，便能得到一個有序序列了

:::details 查看代碼

// 構建小頂堆， 大到小排序// 交互a數組中的x跟y
void swap(int a[], int x, int y){a[x] ^= a[y];a[y] ^= a[x];a[x] ^= a[y];
}// 調整堆
void heapAdjust(int a[], int i, int len){int flag = a[i];for(int j=2*i; j<=len; j*=2 ){if( j<len && a[j]>a[j+1] ) ++j;if( flag < a[j] ) break;a[i] = a[j]; i=j;}a[i] = flag;
}// 堆排序
void heapSort(int a[], int len){for(int i=len/2; i>0; --i){heapAdjust(a, i, len);}for(int i=len; i>1; i--){swap(a, 1, i);heapAdjust(a, 1, i-1);}
}

:::

3. 插入

::: tip 與現實場景的聯系
存在一個已經排好的隊伍（從矮到高），這時，來了個還沒排的家伙，他需要去找他需要站的位置。

:::

3.1 直接插入

• 從后往前， 默認前面已排好序
• 假設j前面j-1的元素已經是有序的，接下來要對a[j] 的位置查找

:::details 查看代碼

func InsertSort(a []int) []int {n := len(a)for i := 1; i < n; i++ {for j := i; j > 0 && a[j] < a[j-1]; j-- {a[j-1], a[j] = a[j], a[j-1]}}return a
}

// 從小到大
for(int i=1; i<length; i++){for(int j=i; (j>0) && ( arr[j]<arr[j-1] ); j--){arr[j]^=arr[j-1];arr[j-1] ^= arr[j];arr[j] ^=arr[j-1];}
}

:::

3.2 折半插入

從1開始，對后面的元素進行折半查找插入

:::details 查看代碼

func BinarySearchInsertSort(a []int) []int {n := len(a)var low, high, mid, reg intfor i := 1; i < n; i++ {low = 0high = i - 1reg = a[i]for low <= high {mid = (low + high) >> 1if reg > a[mid] {low = mid + 1} else {high = mid - 1}}/*low是還沒排序的元素應該去的位置，所以low后面已排序的元素都要往后站*/for j := i; j > low; j-- {a[j] = a[j-1]}a[low] = reg}return a
}

// 降序（從大到小）
void z_sort(int a[], int len){int low = 0,high = 0,mid;int temp = 0;for (int i=1; i<len; i++) {low=0;high=i-1;temp=a[i];		// 要插入的元素while (low<=high) {mid=(low+high)>>1;// 決定順序的位置if (a[mid]<temp) {high=mid-1;}else{low=mid+1;}}// 把元素后移for (int j=i; j>low; j--) {a[j]=a[j-1];}a[low]=temp;//插入元素}
}

:::

3.3 希爾排序

::: tip 百度百科
希爾排序(Shell’s Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因 D.L.Shell 于 1959 年提出而得名。
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個文件恰被分成一組，算法便終止。

---

希爾排序是基于插入排序的以下兩點性質而提出改進方法的：

• 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率。
• 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位。
  :::

希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。

• 重點：注意對每個子序列進行插入排序

:::details 查看代碼

func shellSort(a []int) []int {n := len(a)/*@gap: 增量每次減半*/for gap := n >> 1; gap >= 1; gap >>= 1 {for i := gap; i < n; i += gap {for j := i; j > 0 && a[j] < a[j-gap]; j -= gap {a[j-gap], a[j] = a[j], a[j-gap]}}}return a
}

void shellSort(int* a, int n)
{int i,gap,j;// gap為步長，每次減為原來的一半。for (gap = n / 2; gap >=1 ; gap /= 2){// 組內排序for (i = gap ;i < n; i+= gap) {for(j = i; j>0 && a[j] < a[j-gap]; j-= gap) {swap(a[j-gap], a[j]);}}}
}

:::

4. 歸并排序

• 基本思想

歸并排序是用分治思想，分治模式在每一層遞歸上有三個步驟：

• 分解（Divide）：將n個元素分成個含n/2個元素的子序列。
• 解決（Conquer）：用合并排序法對兩個子序列遞歸的排序。
• 合并（Combine）：合并兩個已排序的子序列已得到排序結果。

• 實現邏輯

2.1 迭代法

① 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列

② 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置

③ 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置

④ 重復步驟③直到某一指針到達序列尾

⑤ 將另一序列剩下的所有元素直接復制到合并序列尾

2.2 遞歸法

① 將序列每相鄰兩個數字進行歸并操作，形成floor(n/2)個序列，排序后每個序列包含兩個元素

② 將上述序列再次歸并，形成floor(n/4)個序列，每個序列包含四個元素

③ 重復步驟②，直到所有元素排序完畢

• 動圖演示

• 歸并排序演示

具體的我們以一組無序數列｛14，12，15，13，11，16｝為例分解說明，如下圖所示：

上圖中首先把一個未排序的序列從中間分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一個一個的數據，再把這些數據兩兩歸并到一起，使之有序，不停的歸并，最后成為一個排好序的序列。

• 文字版

:::details

有序數組A：[3 8 9 11 13]
有序數組B：[1 5 8 10 17 19 20 23]
[] 表示比較的范圍。因為 1 < 3，所以 1 加入輔助數組
有序數組A：[3 8 9 11 13]
有序數組B：1 [5 8 10 17 19 20 23] 
輔助數組：1因為 3 < 5，所以 3 加入輔助數組
有序數組A：3 [8 9 11 13]
有序數組B：1 [5 8 10 17 19 20 23] 
輔助數組：1 3因為 5 < 8，所以 5 加入輔助數組
有序數組A：3 [8 9 11 13]
有序數組B：1 5 [8 10 17 19 20 23] 
輔助數組：1 3 5
因為 8 == 8，所以 兩個數都 加入輔助數組有序數組A：3 8 [9 11 13]
有序數組B：1 5 8 [10 17 19 20 23] 
輔助數組：1 3 5 8 8
因為 9 < 10，所以 9 加入輔助數組有序數組A：3 8 9 [11 13]
有序數組B：1 5 8 [10 17 19 20 23] 
輔助數組：1 3 5 8 8 9因為 10 < 11，所以 10 加入輔助數組
有序數組A：3 8 9 [11 13]
有序數組B：1 5 8 10 [17 19 20 23] 
輔助數組：1 3 5 8 8 9 10因為 11 < 17，所以 11 加入輔助數組
有序數組A：3 8 9 11 [13]
有序數組B：1 5 8 10 [17 19 20 23] 
輔助數組：1 3 5 8 8 9 10 11因為 13 < 17，所以 13 加入輔助數組
有序數組A：3 8 9 11 13
有序數組B：1 5 8 10 [17 19 20 23] 
輔助數組：1 3 5 8 8 9 10 11 13因為數組A已經沒有比較元素，將數組B剩下的元素拼接在輔助數組后面。
結果：1 3 5 8 8 9 10 11 13 17 19 20 23

:::

代碼實現

• 自頂向下歸并(遞歸)

:::details 查看代碼

// 二路歸并
func MergeSort(a []int) []int {n := len(a)if n <= 1 {return a}mid := n >> 1left, right := MergeSort(a[:mid]), MergeSort(a[mid:])return merge(left, right)
}func merge(left, right []int) (res []int) {l, r := 0, 0len_l, len_r := len(left), len(right)for l < len_l && r < len_r {if left[l] < right[r] {res = append(res, left[l])l++} else {res = append(res, right[r])r++}}// 把兩個子切片的剩余元素直接入隊res = append(append(res, left[l:]...), right[r:]...)return
}

// 歸并排序（C-遞歸版）void merge_sort_recursive(int arr[], int reg[], int start, int end) {if (start >= end)return;int len = end - start, mid = (len / 2) + start;int start1 = start, end1 = mid;int start2 = mid + 1, end2 = end;merge_sort_recursive(arr, reg, start1, end1);merge_sort_recursive(arr, reg, start2, end2);int k = start;// 決定是降序還是升序while (start1 <= end1 && start2 <= end2)reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];while (start1 <= end1)reg[k++] = arr[start1++];while (start2 <= end2)reg[k++] = arr[start2++];for (k = start; k <= end; k++)arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {int *reg = new int[len+1];merge_sort_recursive(arr, reg, 0, len - 1);delete[] reg;
}

:::

• 自底向上歸并（迭代）

:::details 查看代碼

func MergeSort(a []int, begin, end int) {step := 1// 步數為1開始，step長度的數組表示一個有序的數組// 1 -> 2 -> 4 -> 8for end-begin > step {// 從頭到尾對數組進行歸并操作// step << 1 = 2 * step 表示偏移到后兩個有序數組將它們進行歸并for i := begin; i < end; i += step << 1 {low := imid := low + stephigh := low + (step << 1)// 不存在第二個數組，直接返回if mid > end {return}// 第二個數組長度不夠if high > end {high = end}// 合并兩個有序的數組merge(a, low, mid, high)}step <<= 1}
}func merge(a []int, begin, mid, end int) {leftSize := mid - beginrightSize := end - midnewSize := leftSize + rightSizeresult := make([]int, 0, newSize)l, r := 0, 0for l < leftSize && r < rightSize {lval := a[begin+l]rval := a[mid+r]if lval < rval {result = append(result, lval)l++} else {result = append(result, rval)r++}}result = append(result, a[begin+l:mid]...)result = append(result, a[mid+r:end]...)for i := 0; i < newSize; i++ {a[begin+i] = result[i]}return
}

void mergeSort(int a[], int reg[], const int end){// 分for(int step=1; step<end; step*=2){for(int j=0; j < end; j += step*2 ){int low = j, mid = j+step-1, high = min(j+2*step-1, end-1);merge(a, reg, low, mid, high );}}
}void merge(int a[], int reg[],  int l, const int mid, const int r){int start = l;int end = r;int j = mid+1;int i = l;while( i<= mid &&  j<= r ){reg[l++] = a[i]>=a[j]   ? a[i++] : a[j++];}while(i<=mid) reg[l++] = a[i++];while(j<=r) reg[l++] = a[j++];for(int ii=start; ii<=end; ii++){a[ii] = reg[ii];}
}

:::

5. 基數排序

:::details 查看代碼

func getbits(a []int) int {max_num := 0for _, v := range a {if v > max_num {max_num = v}}res := 0if max_num == 0 {return 1}for max_num > 0 {max_num /= 10res++}return res
}func radixSort(a []int) {n := len(a)step := getbits(a)radix := 1var num, tail intreg := make([][]int, 10)for i := 0; i < step; i++ {radix *= 10// 每一輪都要清空桶for i := 0; i < 10; i++ {reg[i] = make([]int, 0)}for j := 0; j < n; j++ {num = a[j] % radixtail = num / (radix / 10)reg[tail] = append(reg[tail], a[j])}index := 0for k := 0; k < 10; k++ {for _, v := range reg[k] {a[index] = vindex++}}}
}

#include<iostream>
using namespace std;int maxbit(int data[], int n) //輔助函數，求數據的最大位數
{int d = 1; //保存最大的位數int p = 10;for(int i = 0; i < n; ++i){while(data[i] >= p){p *= 10;++d;}}return d;
}
void radixSort(int data[], int n) //基數排序
{// d 位int d = maxbit(data, n);int *tmp = new int[n+5];int *count = new int[10]; //計數器 --> 排序桶int *flag = new int[10];int i, j, k;int radix = 1;for(i = 1; i <= d; i++) //進行d次排序{for(j = 0; j < 10; j++){count[j] = 0; //每次分配前清空計數器（清桶）tmp[j] = -1;flag[j] = 0;}for(j = 0; j < n; j++){// k 是當前數字位置中的數字k = (data[j] / radix) % 10; //統計每個桶中的記錄數count[k]++;}for(int jj=0; jj<10; jj++){flag[jj] = count[jj];}for(j = 1; j < 10; j++)count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個桶for(j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中{k = (data[j] / radix) % 10;tmp[count[k] - 1] = data[j];count[k]--;}for(j = 0; j < n; j++){//將臨時數組的內容復制到data中data[j] = tmp[j];}radix = radix * 10;}delete[]tmp;delete[]count;
}

:::