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

這篇文章主要介紹C++中插入排序算法的示例分析，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

具體內(nèi)容如下

基本思想

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

直接插入排序

1.排序思路

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

2.排序算法

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

3.算法分析

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

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

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

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

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

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

1.排序思路

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

void InsertSort1(int* arr, int size) 
{ 
  if (arr == NULL) 
    return; 
 
  int i, j, low, high; 
  //1.保存要插入的數(shù) 
  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.算法分析

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

希爾排序

1.排序思路

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

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.移動(dòng)元素，插入 
      j = i - gap; 
      while (j >= 0 && tmp < arr[j]) 
      { 
        arr[j + gap] = arr[j]; 
        j -= gap; 
      } 
      arr[j + gap] = tmp; 
    } 
    gap = gap / 2; 
  } 
}

3.算法分析

希爾排序算法的性能分析是一個(gè)復(fù)雜的問(wèn)題，它的時(shí)間復(fù)雜度與所取gap有關(guān)，一般認(rèn)為其時(shí)間復(fù)雜度為O(N^1.3)，空間復(fù)雜度為O(1)。
希爾排序是一種不穩(wěn)定的算法。

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