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

成都一家集口碑和實(shí)力的網(wǎng)站建設(shè)服務(wù)商，擁有專業(yè)的企業(yè)建站團(tuán)隊(duì)和靠譜的建站技術(shù)，十余年企業(yè)及個(gè)人網(wǎng)站建設(shè)經(jīng)驗(yàn) ,為成都上千余家客戶提供網(wǎng)頁(yè)設(shè)計(jì)制作,網(wǎng)站開(kāi)發(fā),企業(yè)網(wǎng)站制作建設(shè)等服務(wù),包括成都營(yíng)銷型網(wǎng)站建設(shè)，品牌網(wǎng)站建設(shè)，同時(shí)也為不同行業(yè)的客戶提供成都做網(wǎng)站、成都網(wǎng)站制作的服務(wù),包括成都電商型網(wǎng)站制作建設(shè),裝修行業(yè)網(wǎng)站制作建設(shè)，傳統(tǒng)機(jī)械行業(yè)網(wǎng)站建設(shè),傳統(tǒng)農(nóng)業(yè)行業(yè)網(wǎng)站制作建設(shè)。在成都做網(wǎng)站,選網(wǎng)站制作建設(shè)服務(wù)商就選成都創(chuàng)新互聯(lián)。

具體內(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)注創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司行業(yè)資訊頻道！

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站aaarwkj.com，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

本文題目：C++中插入排序算法的示例分析-創(chuàng)新互聯(lián)
網(wǎng)站地址：http://aaarwkj.com/article8/gojop.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、標(biāo)簽優(yōu)化、靜態(tài)網(wǎng)站、用戶體驗(yàn)、品牌網(wǎng)站設(shè)計(jì)、云服務(wù)器

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)