本文實例為大家分享了C++插入排序算法實例的具體代碼，供大家參考，具體內容如下

基本思想

每次將一個待排序的元素，按其大小插入到已經排好序的子序列的適當位置，知道全部元素插入完成為止。

直接插入排序

1.排序思路

arr[0...i-1]為有序區（剛開始時i=1，有序區只有arr[0]一個元素），arr[i...size]為待排序區，每次將待排序區的第一個元素arr[i]插入到有序區中的適當位置，每趟操作都使有序區增加一個元素，待排序區減少一個元素。

2.排序算法

void InsertSort(int* arr, int size) {   if (arr == NULL)     return;    for (int i = 1; i < size; i++)   {     //1.保存要排序的數     int tmp = arr[i];       //2.去有序區尋找該數應該插入的位置     int j = i - 1;     while (j >= 0 && tmp < arr[j])     {       //3.把有序區的位置一個一個往后移       arr[j + 1] = arr[j];       j--;     }     arr[j + 1] = tmp;   } } 

3.算法分析

直接插入排序由兩重循環構成，外循環進行n-1次。
若初始數據序列遞增有序即為正序時，每一趟排序不進入內循環，僅進行一次大小比較。此時元素移動次數為2次（tmp = arr[i]和arr[j+1] = tmp）。所以正序時比較次數和元素移動次數均達到最小值Cmin和Mmin：

Cmin = n-1
Mmin = 2（n-1）

若初始數據序列遞減有序即為逆序時，因當前有序區的元素均大于待排序區的元素，所以需要將待插入元素與arr[0...i-1]中全部元素進行比較，這需要進行i次比較；內循環中需將arr[0...i-1]中所有元素后移（i-1）-0+1 = i次，外加tmp = arr[i]和arr[j+1] = tmp的兩次移動，一趟排序所需的元素移動次數為i+2次。所以逆序時比較次數和元素移動次數均達到最da值Cmax和Mmax：

Cmax = n(n-1) / 2
Mmax = (n-1)(n+4) / 2

正序時直接插入排序算法的時間復雜度為O(N)，逆序時直接插入排序算法的時間復雜度為O(N^2)。
故直接插入排序算法的時間復雜度為O(N^2)。由于只使用了i、j、tmp三個輔助變量，故空間復雜度為O(1)。
當i > j且arr[i] = arr[j]時，直接將arr[i]插入到arr[j]后，故直接插入排序是穩定的。

折半插入排序（二分插入排序）

1.排序思路

采用折半查找方法先在arr[0...i-1]中找到插入位置，再通過移動元素進行插入
2.排序算法

void InsertSort1(int* arr, int size) {   if (arr == NULL)     return;    int i, j, low, high;   //1.保存要插入的數   for (i = 1; i < size; i++)   {     int tmp = arr[i];     low = 0;     high = i - 1;     //2.折半查找插入位置(插入位置為high+1)     while (low <= high)     {       int mid = low + ((high - low) >> 1);       if (tmp < arr[mid])         high = mid - 1;       else         low = mid + 1;     }     //3.元素后移，插入     for (j = i - 1; j >= high + 1; j--)     {       arr[j + 1] = arr[j];     }     arr[j + 1] = tmp;   }   } 

3.算法分析

當初始數據序列為正序時，比較次數并不能減少；當為逆序時，比較次數也不會增加。元素移動次數與直接插入排序相同。
故折半插入排序的時間復雜度為O(N^2)，空間復雜度為O(1)，是穩定的。
就平均性能而言，折半查找優于順序查找，所以折半插入排序優于直接插入排序。

希爾排序

1.排序思路

希爾排序是一種分組插入排序。先取一個小于n的整數d1,作為第一個增量，序列被分為d1組，所有相互之間距離為d1的倍數的元素放在同一個組中，在各組內進行直接插入排序；然后取第二個增量d2（<d1），重復上述過程，直至增量為1。
希爾排序每趟并不產生有序區，在最后一趟排序結束之前，所有元素并不一定歸位，每趟排完之后，數據越來越接近有序。

2.排序算法

void ShellSort(int* arr, int size) {   if (arr == NULL)     return;    int i, j, gap;   //1.取gap   gap = size / 2;   while (gap > 0)   {     //2.分組比較     for (i = gap; i < size; i++)     {       int tmp = arr[i];       //3.移動元素，插入       j = i - gap;       while (j >= 0 && tmp < arr[j])       {         arr[j + gap] = arr[j];         j -= gap;       }       arr[j + gap] = tmp;     }     gap = gap / 2;   } } 

3.算法分析

希爾排序算法的性能分析是一個復雜的問題，它的時間復雜度與所取gap有關，一般認為其時間復雜度為O(N^1.3)，空間復雜度為O(1)。
希爾排序是一種不穩定的算法。

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。