插入排序 與 希爾排序

1 排序

1.1排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。
排序存在穩(wěn)定性，穩(wěn)定性是評估排序的重要標(biāo)準(zhǔn)。
穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
排序可以概括為兩大類 、六大排序：
內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。
外部排序：數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。

這篇文章我們先介紹插入排序。

2 插入排序

2.1 插入排序原理

生活中最常見的插入排序就是撲克牌，我們一張一張的拿出來，比較然后放在合適位置。所用思想就是插入排序：
把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。

2.2 排序步驟

1. 從第一個元素開始，默認(rèn)已經(jīng)有序
2. 取后一個元素tmp ，開始向前掃描
3. (升序)如果有序序列的最后一個元素大于tmp , 有序序列結(jié)尾下標(biāo)向前移動
4. 重復(fù) 3 步驟，直到有序序列最后一個元素小于tmp
5. 插入tmp在該有序序列后。
6. 再取數(shù)組下一個元素，重復(fù) 1-5 步驟
   

2.3 代碼實現(xiàn)

// 插入排序
void InsertSort(int* a, int n) {for (int i = 0; i < n - 1; i++) {int end = i;//記錄有序部分的最后下標(biāo)int tmp = a[end + 1];//被排序數(shù)while (end >= 0) {if (a[end] > tmp) {//如果有序部分最大值大于被排序數(shù)，有序下標(biāo)--a[end + 1] = a[end];end--;}else//如果有序部分最大值小于被排序數(shù)，直接退出。break;}//在比被排序數(shù)小的有序部分后賦值a[end + 1] = tmp;}
}

功能實現(xiàn)效果，非常nice。

直接插入排序的特性總結(jié)：

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

3 希爾排序

3.1 希爾排序原理

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數(shù)，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進(jìn)行排序。然后，取，重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)=1時，所有記錄在統(tǒng)一組內(nèi)排好序。

根據(jù)插入排序的特性 元素集合越接近有序，直接插入排序算法的時間效率越高。，我們進(jìn)行多次不同gap的插入排序，使其逐漸有序。進(jìn)而時間復(fù)雜度更低。
插入排序可以視為特殊的希爾排序。

3.2 排序步驟

1. 選定gap值，并分組進(jìn)行預(yù)排序
2. 每組進(jìn)行插入排序，使序列變得更加有序。
3. gap值變小（務(wù)必保證最后一次是gap==1）
4. 重復(fù) 1 - 3 步驟，直到gap為1。
5. 排序完成。
   

3.3 代碼實現(xiàn)

// 希爾排序
void ShellSort(int* a, int n) {int gap = n;//設(shè)置初始gap值while (gap > 1) {gap = gap / 2;//每次除2 直至為 1for (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;}elsebreak;}a[end + gap] = tmp;//結(jié)束后賦值}}
}

運行查看效果，very good！

希爾排序的特性總結(jié)：

1. 希爾排序是對直接插入排序的優(yōu)化。
2. 當(dāng)gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就
   會很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實現(xiàn)后可以進(jìn)行性能測試的對比。
3. 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在好些樹中給出的
   希爾排序的時間復(fù)雜度都不固定：

4 時間復(fù)雜度分析

我們設(shè)計一個100000個數(shù)據(jù)測試函數(shù)，來檢測一下插入排序，希爾排序的時間復(fù)雜度（以冒泡排序為對照組）。
請看下面測試效果：

這里希爾排序有非常明顯的優(yōu)勢，運算非常之快，其次為插入排序。普通的冒泡排序在這里就像螻蟻一般。

至于希爾排序的時間復(fù)雜度目前還沒有證明。大概為n^1.3。下面是殷老師的觀點。

Thanks?(･ω･)ﾉ

下一篇文章見！！！！！！！