C++中插入排序算法的示例分析

這篇文章主要介紹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)。
希爾排序是一種不穩定的算法。

以上是“C++中插入排序算法的示例分析”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！