1、插入排序的基本思想

從初始有序的子集合開始，不斷地把新的數(shù)據(jù)元素插入到已排列有序子集合的合適位置，使得子集合中數(shù)據(jù)元素的個數(shù)不斷增多，當子集合等于集合時，插入排序算法結(jié)束。常用的插入排序有直接插入排序和希爾排序兩種。

2、直接插入排序

直接插入排序就是順序地把待排序的數(shù)據(jù)元素按照其關(guān)鍵值的大小插入到已排序的數(shù)據(jù)元素子集的適當位置。子集合的數(shù)據(jù)元素個數(shù)從只有一個數(shù)據(jù)元素開始逐漸增大，當子集合大小最終和集合大小相同時，排序完畢。
假設(shè)待排序的n個數(shù)據(jù)元素存放在數(shù)組a中，初始時子集合a[0]已排好序，第一次循環(huán)準備把數(shù)據(jù)元素a[1]插入到已排好序的子集合中，這只需要比較a[0]和a[1]，如果a[0]小于或等于a[1]，則說明序列有序，否則將a[1]插入到a[0]之前，這樣子集合的大小增的為2；第二次循環(huán)準備把數(shù)據(jù)元素a[2]插入到已排好序的子集合中，這需要比較a[2]和a[1]的值以確定是否需要把a[2]插入到a[1]之前，然后比較a[2]和a[0]，確認是否需要把a[2]插入到a[0]之前；這樣的循環(huán)過程一直到a[n-1]插入完為止。這時的數(shù)據(jù)元素集合a[0]，a[1]，···，a[n-1]就全部排好序了。
如下圖所示是直接插入排序的過程圖。

2.1、直接插入排序的代碼實現(xiàn)

void InsertSort() {
    int a[] = {9, 3, 1, 4, 2, 7, 8, 6, 5};
    int n = sizeof(a) / sizeof(a[0]);
    for (int i = 0; i < n - 1; ++i) {
        int temp = a[i + 1];
        int j = I;
        while (j > -1 && temp < a[j]) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
    }
    for (int k = 0; k < n; ++k) {
        printf("%d ", a[k]);
    }
}

2.2、直接插入排序的時間復(fù)雜度

直接插入排序算法的時間復(fù)雜度分析分為最好、最壞和隨機三種情況。

• 最好情況是原始數(shù)據(jù)元素集合已全部排好序。這時算法中內(nèi)層while循環(huán)的循環(huán)次數(shù)每次均為0，外層for循環(huán)中每次數(shù)據(jù)元素的比較次數(shù)均為1，數(shù)據(jù)元素的賦值語句執(zhí)行次數(shù)均為2。因此整個排序過程中的比較次為n-1，賦值語句執(zhí)行次數(shù)為2(n-1)。所以直接插入排序算法最好情況下的時間復(fù)雜度為。
• 最壞情況是原始數(shù)據(jù)元素集合反序排列。這時算法內(nèi)存while循環(huán)的循環(huán)次數(shù)每次均為i，整個外層for循環(huán)中的比較次數(shù)和賦值語句的執(zhí)行次數(shù)（即移動次數(shù)）計算公式如下：
  

因此直接插入排序算法最壞情況的時間復(fù)雜度為。

• 如果原始數(shù)據(jù)元素集合大小的排序是隨機的，則數(shù)據(jù)元素的期望比較次數(shù)和期望移動次數(shù)約為。因此直接插入排序算法的期望時間復(fù)雜度為。

3、希爾排序

希爾排序是把待排序的數(shù)據(jù)元素分成若干個小組，對同一個小組內(nèi)的數(shù)據(jù)元素用直接插入法排序；小組的個數(shù)逐漸減少；當完成所有數(shù)據(jù)元素都在一個組內(nèi)的排序后，排序過程結(jié)束?？偨Y(jié)來說希爾排序是在分組概念上的直接插入排序，在不斷減少組的個數(shù)時把原各個小組的數(shù)據(jù)元素插入到新組中的合適位置上。

如上圖所示是希爾排序的過程。在此我們選擇增量gap=length/2，縮小增量繼續(xù)以gap = gap/2的方式。

• 初始增量gap=length/2=5,這意味著整個數(shù)組分為5組，分別為[9,4]，[1,8]，[2,6]，[5,3]，[7,5]。對這5組分別進行直接插入排序，結(jié)果如上圖所示第一趟排序的結(jié)果所示。
• 然后縮小當量gap=5/2=2，數(shù)組被分為2組，分別為[4,2,5,8,5]和[1,3,9,6,7]
• 對這兩組數(shù)據(jù)進行直接插入排序結(jié)果如上圖第二趟排序后的結(jié)果所示。
• 縮小當量gap=2/2=1，數(shù)組分為1組，為[2,1,4,3,5,6,5,7,8,9]。
• 對這組數(shù)據(jù)進行直接插入排序得到的結(jié)果就是最后的排序結(jié)果。

3.1、希爾排序的代碼實現(xiàn)

void shellSort() {
    int arr[] = {9, 3, 1, 4, 2, 7, 8, 6, 5,10};
    int length = sizeof(arr) / sizeof(arr[0]);//計算數(shù)組的長度
    int gap = length / 2;//初始增量
    while (gap > 0) {
        for (int i = 0; i < gap; ++i) {//共有g(shù)ap個小組
            //組內(nèi)直接插入排序，每次增加gap
            for (int j = i; j < length - gap; j = j + gap) {
                int tmp = arr[j + gap];
                int k = j;
                while (k > -1 && arr[k] > tmp) {
                    arr[k + gap] = arr[k];
                    k -= gap;
                }
                arr[k + gap] = tmp;
            }
        }

        if (gap == 1) { break; }
        gap = gap / 2;
    }
    for (int k = 0; k < length; ++k) {
        printf("%d ", arr[k]);
    }
}

3.2、希爾排序的時間復(fù)雜度

比較希爾排序和直接插入排序兩個算法的代碼，希爾排序算法比直接插入排序算法要復(fù)雜些，但是分析希爾排序算法中四重循環(huán)次數(shù)可以發(fā)現(xiàn)，外面兩重的循環(huán)次數(shù)都很小，并且當增量遞減，小組變大時，小組內(nèi)的數(shù)據(jù)元素已基本有序。越接近有序時，直接插入排序算法的時間效率就越好。因此希爾排序算法的時間復(fù)雜度較直接插入排序算法的時間復(fù)雜度改善很多。
希爾排序算法的時間復(fù)雜度分析比較復(fù)雜，實際所需要的時間取決于各次排序時增量的取值。希爾排序算法的時間復(fù)雜度約為。希爾排序算法的空間復(fù)雜度為，由于希爾排序是按照增量分組進行排序的，所以希爾排序算法是一種不穩(wěn)定的排序算法。