目錄

一、排序的概念

?二、常見的排序算法

?三、插入排序

1.直接插入排序

?1.直接插入排序實現

2.直接插入排序特性及復雜度

2.希爾排序?

1.排序思路

2.希爾排序實現?

3.希爾排序的特性及復雜度?

---

一、排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。

穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次 序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排 序算法是穩定的；否則稱為不穩定的。

內部排序：數據元素全部放在內存中的排序。

外部排序：數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序。

?二、常見的排序算法

最常用的排序算法可以分為四大類：
插入排序、選擇排序、交換排序與歸并排序。插入排序的代表算法有直接插入排序與希爾排序；選擇排序的排序算法代表是選擇排序與堆排序；交換排序中我們要熟識冒泡排序與快速排序；歸并排序則主要是以歸并排序算法為主，及一些由歸并思想衍生出的排序算法。?

?三、插入排序

1.直接插入排序

直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為 止，得到一個新的有序序列 。

實際中我們玩撲克牌時，就用了插入排序的思想

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

?1.直接插入排序實現

首先我們解決單次排序，從后向前比較，如果a[end] > tmp，則把a[end + 1] 和?a[end] 進行交換，然后再向前比較，當end跑到頭時end+1剛好為0。

因為第一個數字不用排，所以需要循環n-1趟

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

2.直接插入排序特性及復雜度

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

1. 元素集合越接近有序，直接插入排序算法的時間效率越高

2. 時間復雜度：O(N^2)

3. 空間復雜度：O(1)，它是一種穩定的排序算法

4. 穩定性：穩定

2.希爾排序?

1.排序思路

????????希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數，把待排序文件中所有記錄分成個 組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序。然后，取，重復上述分組和排序的工作。當到達=1時，所有記錄在統一組內排好序。

簡單來說，意思是取一個整數，作為 間距gap ，對于每個元素，與其間隔為gap 的元素分成一個組，對每組排序 。不斷調整gap，對每組進行不斷排序，在 gap調整到 1 后進行插入排序，就可以將數據排成有序。而按照間距gap分組并排序被稱為?預排序?。

所以，希爾排序可分為兩步，預排序（讓數據接近有序）和直接插入排序

2.希爾排序實現?

希爾排序和直接插入排序思路是差不多的，當gap = 1時二者相等

所以單次希爾排序為

for (int j = 0; j < gap; j++)
{for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}
}

這里的gap不僅是每組中元素的間距，也是組數。上面代碼只完成了單組，對于完整的一組需要在外面套上一層循環，需要循環gap次

//優化
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 -= gap;}else{break;}}a[end + gap] = tmp;
}

希爾排序的特性總結：

1. 希爾排序是對直接插入排序的優化。

2. 當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就 會很快。這樣整體而言，可以達到優化的效果。我們實現后可以進行性能測試的對比。

3. 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些書中給出的希爾排序的時間復雜度都不固定?

這里為什么gap/3后要+1呢，因為每次+1，到最后必定是1?

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//gap = gap / 2;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 -= gap;}else{break;}}a[end + gap] = tmp;}}
}

3.希爾排序的特性及復雜度?

Knuth進行了大量的試驗統計，得出最接近的結論，希爾排序的最終時間復雜度為 O(N^1.3)左右。?

而空間復雜度就很簡單了，并沒有開辟額外的空間，所以空間復雜度為 O(1) 。

希爾排序是對直接插入排序的優化。
當 增量 > 1時都是預排序，目的是讓數組更接近于有序。當增量為 1 時，數組已經接近有序了，再進行排序就能提高算法執行的時間效率。
時間復雜度：O(N^1.3) 。
空間復雜度：O(1) 。
穩定性：不穩定。