十大排序算法--插入排序（Insertion Sort）

目錄

插入排序（Insertion Sort）

算法描述

時間複雜度

穩定性分析

應用分析

C++實作 

二分插入排序算法 （BinaryInsertionSort）

算法描述

實作步驟

C++實作

插入排序（Insertion Sort）

插入排序是指在待排序的元素中，假設前面n-1(其中n>=2)個數已經是排好順序的，現将第n個數插到前面已經排好的序列中，然後找到合适自己的位置，使得插入第n個數的這個序列也是排好順序的。按照此法對所有元素進行插入，直到整個序列排為有序的過程，稱為插入排序。

每一輪将目前數插入到前面已經排序好的合适位置，是以關鍵是如何通過不斷比較以及移動來找到該位置。

算法描述

• step1. 從第一個元素開始，該元素可以認為已經被排序；
• step2. 取出下一個元素，在已經排序的元素序列中從後向前掃描；
• step3. 如果該元素（已排序）大于新元素，将該元素移到下一位置；
• step4. 重複步驟3，直到找到已排序的元素小于或者等于新元素的位置；
• step5. 将新元素插入到該位置後；
• step6. 重複步驟2~5。

時間複雜度

在插入排序中，當待排序數組是有序時，是最優的情況，隻需目前數跟前一個數比較一下就可以了，這時一共需要比較N- 1次，時間複雜度

。

最壞的情況是待排序數組是逆序的，此時需要比較次數最多，總次數記為：1+2+3+…+N-1，是以，插入排序最壞情況下的時間複雜度為

。

穩定性分析

如果待排序的序列中存在兩個或兩個以上具有相同關鍵詞的資料，排序後這些資料的相對次序保持不變，即它們的位置保持不變，則該算法是穩定的；如果排序後，資料的相對次序發生了變化，則該算法是不穩定的。關鍵詞相同的資料元素将保持原有位置不變，是以該算法是穩定的  。

應用分析

插入排序适用于已經有部分資料已經排好，并且排好的部分越大越好。一般在輸入規模大于1000的場合下不建議使用插入排序 。

C++實作 

#include <iostream> using namespace std; template<typename T> void InsertionSort(T a[], int len ){     for (int i = 1; i < len; i++){         T key = a[i];           // 儲存無序區第一個元素為key          cout << "i = " << i << "  " << "a[i] = " << a[i] << endl;         int j = i - 1;         for(j; j >= 0; j--){             if(a[j] > key)                 a[j + 1] = a[j];             else{                 break;             }         }         a[j + 1] = key;         for( int ii = 0; ii < len; ii++){               cout << a[ii]  << "  ";         }     cout << endl << endl;         } } int main(){     int i, j;     int arr[] = {2, 1, 0, 9, 11, 7, 31, 5, 8, 3, 99, 8};     int len = sizeof(arr) / sizeof(arr[0]);     InsertionSort(arr, len);     for(int i = 0; i < len; i++){         cout << ' ' << arr[i];     }     cout << endl;     float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };     len = (int) sizeof(arrf) / sizeof(arrf[0]);     InsertionSort(arrf, len);     for (int i = 0; i < len; i++)         cout << arrf[i] << ' ';     cout << endl;     getchar();     return 0; }

二分插入排序算法 （BinaryInsertionSort）

算法描述

二分插入排序是不斷對有序表二分來确定插入位置，即一次比較，通過待插入記錄與有序表中間位置的記錄按關鍵字比較，将有序表一分為二，下一次比較在其中一個有序表中進行，将子表又一分為二。這樣繼續下去，直到待比較的子表中隻有一個記錄時，比較一次便确定最終插入位置。

實作步驟

step 1、設數a[] 長度為 len ，第 i 個記錄為待插入記錄。low  = 0, high = i , temp = a[i];

step 2、若 low > high , 得到插入位置，轉到 step 5；

step 3、實作取表的中點，并将表一分為二，确定待插入區間。low <= high , mid = (low + high) / 2; 

step 4、若 temp < a[mid], 插入位置在低半區，high = mid -1 ；否則，插入位置在高半區 low = mid + 1,轉到 step 2；

step5、 high + 1 即為待插入位置。

C++實作

#include <iostream> using namespace std; template <typename T> void  BinaryInsertionSort(T a[], int len){     for(int i = 1; i < len; i++){         T temp = a[i];       //儲存待插入元素          int low = 0;         //設定初始區間          int high = i;          while(low <= high){    //該循環完成确定插入位置               int mid = (low + high) / 2;              if(temp > a[mid])                  low = mid + 1;    //插入位置在高半區中               else                   high = mid - 1;    //插入位置在低半區中           }          for(int j = i - 1; j >= high + 1; j--)    //high + 1為插入位置               a[j + 1] = a[j];      //後移元素，留出插入空位          a[high + 1] = temp;       //将元素插入      }    } int main(){     int i, j;     int arr[] = {2, 1, 0, 9, 11, 7, 31, 5, 8, 3, 99, 8};     int len = sizeof(arr) / sizeof(arr[0]);     cout << "二分插入排序前：";     for(i = 0; i < len; i++)         cout << arr[i] << "  ";     cout << endl << endl;      BinaryInsertionSort(arr, len);     cout << "二分插入排序後：";     for(i = 0; i < len; i++)         cout << arr[i] << "  ";     cout << endl << endl;      return 0;  }