C++中插入排序算法的示例分析-創(chuàng)新互聯(lián)

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

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

具體內容如下

基本思想

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

直接插入排序

1.排序思路

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

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ù)應該插入的位置 
    int j = i - 1; 
    while (j >= 0 && tmp < arr[j]) 
    { 
      //3.把有序區(qū)的位置一個一個往后移 
      arr[j + 1] = arr[j]; 
      j--; 
    } 
    arr[j + 1] = tmp; 
  } 
}

3.算法分析

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

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

若初始數(shù)據(jù)序列遞減有序即為逆序時，因當前有序區(qū)的元素均大于待排序區(qū)的元素，所以需要將待插入元素與arr[0...i-1]中全部元素進行比較，這需要進行i次比較；內循環(huán)中需將arr[0...i-1]中所有元素后移（i-1）-0+1 = i次，外加tmp = arr[i]和arr[j+1] = tmp的兩次移動，一趟排序所需的元素移動次數(shù)為i+2次。所以逆序時比較次數(shù)和元素移動次數(shù)均達到最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]后，故直接插入排序是穩(wěn)定的。

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

1.排序思路

采用折半查找方法先在arr[0...i-1]中找到插入位置，再通過移動元素進行插入
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.算法分析

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

希爾排序

1.排序思路

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

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)。
希爾排序是一種不穩(wěn)定的算法。

以上是“C++中插入排序算法的示例分析”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注創(chuàng)新互聯(lián)網(wǎng)站建設公司行業(yè)資訊頻道！

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

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

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

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

猜你還喜歡下面的內容