C++插入排序算法實(shí)例
插入排序
沒(méi)事喜歡看看數(shù)據(jù)結(jié)構(gòu)和算法，增加自己對(duì)數(shù)據(jù)結(jié)構(gòu)和算法的認(rèn)識(shí)，同時(shí)也增加自己的編程基本功。插入排序是排序中比較常見(jiàn)的一種，理解起來(lái)非常簡(jiǎn)單?，F(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)行對(duì)比
3 10 8 0 6 9 2 // 由于10比3大，將10向后移動(dòng)，將3放置在原來(lái)10的位置；再取8與前一個(gè)元素10進(jìn)行對(duì)比
3 8 10 0 6 9 2 // 同理移動(dòng)10；然后8再和3比，8大于3，所以不再移動(dòng)；如此重復(fù)下去
……
0 2 3 6 8 9 10
也就是說(shuō)，我們每一次取一個(gè)元素，都要將該元素與之前已經(jīng)排序好的元素進(jìn)行比較。
插入排序的最差時(shí)間復(fù)雜度為O(n^2)。同時(shí)，該算法不需要開(kāi)辟額外的空間，都是在原空間上進(jìn)行移動(dòng)操作。
代碼實(shí)現(xiàn)
#include <iostream>
using namespace std;
void InsertSort(int arr[], int length)
{
int temp;
for (int i = 1; i < length; ++i) // 從數(shù)組中的第二個(gè)元素開(kāi)始
{
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;
}
相關(guān)文章
Stack是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，常常被用來(lái)解決遞歸問(wèn)題、括號(hào)匹配問(wèn)題、函數(shù)調(diào)用棧等等。本文將介紹C++中stack的使用方法及基本操作，需要的可以參考一下2023-05-05
Opencv實(shí)現(xiàn)邊緣檢測(cè)與輪廓發(fā)現(xiàn)及繪制輪廓方法詳解
這篇文章主要介紹了Opencv實(shí)現(xiàn)邊緣檢測(cè)與輪廓發(fā)現(xiàn)及繪制輪廓方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2022-12-12
C語(yǔ)言執(zhí)行程序時(shí)遇到的常見(jiàn)問(wèn)題及解決
這篇文章主要介紹了C語(yǔ)言執(zhí)行程序時(shí)遇到的常見(jiàn)問(wèn)題及解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-03-03
C語(yǔ)言修煉之路數(shù)據(jù)類型悟正法 解析存儲(chǔ)定風(fēng)魔下篇
使用編程語(yǔ)言進(jìn)行編程時(shí)，需要用到各種變量來(lái)存儲(chǔ)各種信息。變量保留的是它所存儲(chǔ)的值的內(nèi)存位置。這意味著，當(dāng)您創(chuàng)建一個(gè)變量時(shí)，就會(huì)在內(nèi)存中保留一些空間。您可能需要存儲(chǔ)各種數(shù)據(jù)類型的信息，操作系統(tǒng)會(huì)根據(jù)變量的數(shù)據(jù)類型，來(lái)分配內(nèi)存和決定在保留內(nèi)存中存儲(chǔ)什么2022-02-02
這篇文章主要介紹了怎樣用cmd運(yùn)行C程序？今天就來(lái)和大家分享一下用cmd運(yùn)行C程序的實(shí)現(xiàn)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-10-10
歸并排序的遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn)代碼
以下是對(duì)歸并排序的遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn)代碼進(jìn)行了詳細(xì)的介紹，需要的朋友可以過(guò)來(lái)參考下2013-08-08
關(guān)于c++編譯protobuf時(shí)提示LNK2001 無(wú)法解析的外部符號(hào)的問(wèn)題
這篇文章主要介紹了關(guān)于c++編譯protobuf時(shí)提示LNK2001 無(wú)法解析的外部符號(hào)的問(wèn)題,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-12-12
C++新特性詳細(xì)分析基于范圍的for循環(huán)
C++11這次的更新帶來(lái)了令很多C++程序員期待已久的for?range循環(huán)，每次看到j(luò)avascript，?lua里的for?range，心想要是C++能有多好，心里別提多酸了。這次C++11不負(fù)眾望，再也不用羨慕別家人的for?range了。下面看下C++11的for循環(huán)的新用法2022-04-04
C++ boost 時(shí)間與日期處理詳細(xì)介紹
這篇文章主要介紹了C++ boost 時(shí)間與日期處理詳細(xì)介紹的相關(guān)資料,這里提供實(shí)例代碼，及實(shí)現(xiàn)效果，需要的朋友可以參考下2016-11-11
C語(yǔ)言讀取data.json文件并存入MySQL數(shù)據(jù)庫(kù)小案例(推薦)
本文介紹如何使用C語(yǔ)言結(jié)合cJSON庫(kù)讀取JSON文件,并將數(shù)據(jù)存儲(chǔ)到MySQL數(shù)據(jù)庫(kù)中,示例代碼包括創(chuàng)建MySQL表的SQL語(yǔ)句和C語(yǔ)言代碼,以及如何編譯和運(yùn)行程序,確保已安裝必要的庫(kù)以支持程序運(yùn)行2024-10-10