目錄

0. 前情提醒：

1. 插入排序

1.1 基本思想：

1.2?直接插入排序

?實現步驟：

?動圖演示：

?特性總結：

?代碼實現：

1.3 希爾排序（縮小增量排序）

基本思想：

步驟演示：

特性總結：

代碼實現：

2. 交換排序

2.1 基本思想：

2.2?冒泡排序

特性總結：

代碼實現：

2.3 快速排序

3.選擇排序

3.1 基本思想：

3.2 直接選擇排序

步驟思路：

動圖演示：?

特性總結：

代碼實現：

3.3 堆排序

代碼實現：

---

0. 前情提醒：

下面的所有代碼實現均為升序

1. 插入排序

1.1 基本思想：

把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排序好的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。

1.2?直接插入排序

?實現步驟：

當插入第i（i>=1）各元素時，前面的array[0]，array[1]，......，array[i-1]已經排好序，此時用array[i]的排序碼與array[i-1]，array[i-2]，......的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移

?動圖演示：

?特性總結：

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

?代碼實現：

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

1.3 希爾排序（縮小增量排序）

基本思想：

先選定一個整數，把待排序的文件中所有（n個）記錄分成（n/gap）個組，所有距離為gap的記錄分在同一個組，并對每個組內的記錄進行排序。然后去gap=gap/2，重復上述分組和排序的工作。當到達gap=1時，所有記錄在統一組內排好序（gap=1時就是直接插入排序，gap>1時屬于預排序）。

步驟演示：

特性總結：

1. 希爾排序是對直接插入排序的優化
2. 當gap>1時都是預排序，目的是讓數組更接近有序。當gap==1時，數組已經接近有序，這樣排序就會很快。這樣整體而言，可以達到優化的效果
3. 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在不同書上給出的希爾排序的時間復雜度都不一樣

代碼實現：

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

2. 交換排序

2.1 基本思想：

所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向前部移動

2.2?冒泡排序

左邊大于右邊交換，一趟排下來最大的在右邊

特性總結：

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

代碼實現：

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

2.3 快速排序

快速排序較為復雜，想了解請點擊-----》快速排序

3.選擇排序

3.1 基本思想：

每一次從待排序的數據元素中選出一個最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完

3.2 直接選擇排序

步驟思路：

• 在元素array[i]--array[n-1]中選擇關鍵碼最小（或最大）的數據元素
• 若它不是這組元素中最后一個（第一個）元素，則將它與這組元素中的最后一個（第一個）元素交換
• 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素

動圖演示：?

特性總結：

1. 思路很好理解，但效率不好，實際很少應用，主要具有教學意義
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)
4. 穩定性：不穩定

代碼實現：

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

3.3 堆排序

堆排序（HeapSort）是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數據，利用堆中某個節點的值總是不大于或不小于其父節點的值的特性。注意：升序建大堆，降序建小堆

代碼實現：

void AdjustDwon(int* a, int n, int root) {int i = 2 * root + 1;if (i < n - 1 && a[i] < a[i + 1]) {i++;}if (i < n && a[root] < a[i]) {swap(&a[root], &a[i]);AdjustDwon(a, n, i);}
}
void HeapSort(int* a, int n) {
//建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--) {AdjustDwon(a, n, i);}while (n>1) {swap(&a[0], &a[n-1]);n--;AdjustDwon(a, n, 0);}
}