C++插入排序算法實(shí)例

2020-01-26 15:16:03

字體：大中小

供稿：網(wǎng)友

插入排序

沒事喜歡看看數(shù)據(jù)結(jié)構(gòu)和算法，增加自己對數(shù)據(jù)結(jié)構(gòu)和算法的認(rèn)識(shí)，同時(shí)也增加自己的編程基本功。插入排序是排序中比較常見的一種，理解起來非常簡單。現(xiàn)在比如有以下數(shù)據(jù)需要進(jìn)行排序：

10 3 8 0 6 9 2

當(dāng)使用插入排序進(jìn)行升序排序時(shí)，排序的步驟是這樣的：

10 3 8 0 6 9 2 // 取元素3，去和10進(jìn)行對比

3 10 8 0 6 9 2 // 由于10比3大，將10向后移動(dòng)，將3放置在原來10的位置；再取8與前一個(gè)元素10進(jìn)行對比

3 8 10 0 6 9 2 // 同理移動(dòng)10；然后8再和3比，8大于3，所以不再移動(dòng)；如此重復(fù)下去

……

0 2 3 6 8 9 10

也就是說，我們每一次取一個(gè)元素，都要將該元素與之前已經(jīng)排序好的元素進(jìn)行比較。

插入排序的最差時(shí)間復(fù)雜度為O(n^2)。同時(shí)，該算法不需要開辟額外的空間，都是在原空間上進(jìn)行移動(dòng)操作。

代碼實(shí)現(xiàn)

復(fù)制代碼代碼如下:

#include <iostream>
using namespace std;
 
void InsertSort(int arr[], int length)
{
     int temp;
     for (int i = 1; i < length; ++i) // 從數(shù)組中的第二個(gè)元素開始
     {
          temp = arr[i]; // 記錄當(dāng)前的元素
          int j = i - 1;
          while (j >= 0 && temp < arr[j]) // 將當(dāng)前元素與之前的已經(jīng)排序好的序列元素進(jìn)行挨個(gè)比較
          {
               arr[j + 1] = arr[j]; // 已經(jīng)排序好的序列整體向后移動(dòng)
               --j;
          }
          arr[j + 1] = temp; // 插入當(dāng)前的元素
     }
}
 
int main()
{
     int arr[10] = {9, 2, 8, 2, 3, 2, 4, 10, 34, 5};
 
     InsertSort(arr, 10);
 
     for (int i = 0; i < 10; ++i)
     {
          cout<<arr[i]<<" ";
     }
     cout<<endl;
 
     return 0;
}