C++排序算法之插入排序
本文實(shí)例為大家分享了C++排序算法之插入排序的具體代碼，供大家參考，具體內(nèi)容如下
1.基本思想：將未排序的數(shù)據(jù)元素按大小順序插入到已排好序數(shù)據(jù)序列中，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
例如：對(duì)2, 4, 3, 1, 6, 5進(jìn)行插入排序。進(jìn)行排序前，默認(rèn)2是有序的，為有序區(qū)，而4, 3, 1, 6, 5是無(wú)序的，為無(wú)序區(qū)。將這五個(gè)無(wú)序的數(shù)按從小到大的順序插入到有序區(qū)。
第一趟排序：將4與有序區(qū)的2比較，若小于2則插到2前面，大于2插到2后面。操作后有序區(qū)為：{2,4}；
第二趟排序：將3與有序區(qū)的每個(gè)數(shù)比較（與有序區(qū)的數(shù)按從右到左的順序比較，即依次與4,2比較），尋找合適的位置插入，操作后有序區(qū)為：{2,3,4}。這里將3插入到2和4之間。
……
第五趟排序：將數(shù)據(jù)元素5與有序區(qū)的數(shù)據(jù)進(jìn)行比較，并插入到有序區(qū)，則排序后的數(shù)據(jù)序列為：{1,2,3,4,5,6}。
總結(jié)：
1.第一趟排序時(shí)默認(rèn)無(wú)序區(qū)的第一個(gè)數(shù)據(jù)元素是有序的；
2.從以上例子可以看出，若對(duì)n個(gè)數(shù)進(jìn)行排序，需要進(jìn)行（n-1）趟。
2.代碼：
#include<iostream>
using namespace std;
void insertion_sort(int a[], int len)
{
int i, j, temp;
for (i = 1; i < len; i++) //控制趟數(shù)
{
temp = a[i];
for(j = i; j > 0 && temp < a[j-1]; j--) // 無(wú)序區(qū)的數(shù)據(jù)與有序區(qū)的數(shù)據(jù)元素比較
{
a[j] = a[j-1]; //將有序區(qū)的元素后移
}
a[j] = temp;
}
}
int main()
{
int a[] = {2, 4, 3, 1, 6, 5};
insertion_sort(a, 6);
for (int i = 0; i < 6; i++)
{
cout << a[i] << " ";
}
return 0;
}
3.時(shí)間復(fù)雜度分析： 若將待排序的數(shù)據(jù)元素按從小到大的順序排序，可分為最好情況和最壞情況討論。
(1).最好的情況：最好的情況就是待排序的數(shù)據(jù)已經(jīng)排好序了，這時(shí)只需要進(jìn)行（n-1)次比較操作。
(2).最壞的情況：最壞的情況就是待排序的數(shù)據(jù)序列是逆序的。此時(shí)需要進(jìn)行的比較次數(shù)為n(n-1)/2次，賦值操作是比較操作的次數(shù)n(n-1)/2+(n-1）次。平均來(lái)說(shuō)插入排序算法的時(shí)間復(fù)雜度為O(n^2）。
注：插入排序不適合對(duì)于數(shù)據(jù)量比較大的排序應(yīng)用
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
C語(yǔ)言使用openSSL庫(kù)DES模塊實(shí)現(xiàn)加密功能詳解
這篇文章主要介紹了C語(yǔ)言使用openSSL庫(kù)DES模塊實(shí)現(xiàn)加密功能,簡(jiǎn)單講解了DES加密的相關(guān)概念,并結(jié)合實(shí)例形式分析了DES加密的具體實(shí)現(xiàn)技巧,需要的朋友可以參考下2017-05-05
詳解C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之棧
這篇文章主要為大家介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之棧，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-01-01
VC運(yùn)用OPENGL加載BMP紋理圖的實(shí)現(xiàn)方法匯總
這篇文章主要介紹了VC運(yùn)用OPENGL加載BMP紋理圖的實(shí)現(xiàn)方法,對(duì)于更好的了解OpenGL很有幫助,需要的朋友可以參考下2014-07-07
詳解利用C語(yǔ)言如何實(shí)現(xiàn)簡(jiǎn)單的內(nèi)存池
這篇文章主要給大家介紹了關(guān)于C語(yǔ)言如何實(shí)現(xiàn)簡(jiǎn)單的內(nèi)存池的相關(guān)資料,設(shè)計(jì)內(nèi)存池的目標(biāo)是為了保證服務(wù)器長(zhǎng)時(shí)間高效的運(yùn)行,通過(guò)對(duì)申請(qǐng)空間小而申請(qǐng)頻繁的對(duì)象進(jìn)行有效管理,減少內(nèi)存碎片的產(chǎn)生,合理分配管理用戶內(nèi)存,需要的朋友可以參考下2021-08-08
Dev-C++是一個(gè)Windows環(huán)境下C/C++的集成開(kāi)發(fā)環(huán)境(IDE),它是一款自由軟件,遵守GPL,下面這篇文章主要給大家介紹了關(guān)于適合新手小白DEV?C++的使用方法,文中通過(guò)圖文介紹的非常詳細(xì),需要的朋友可以參考下2023-02-02
今天小編就為大家分享一篇關(guān)于關(guān)于C語(yǔ)言中E-R圖的詳解，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2018-12-12
這篇文章主要為大家介紹了C++ LeetCode1781題解所有子字符串美麗值之和，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-12-12
這篇博客，我們?cè)敿?xì)講述如何利用tinyxml操縱xml。以及在操作的過(guò)程中，我們應(yīng)該注意的問(wèn)題2013-01-01
模板類(lèi)vector是一個(gè)動(dòng)態(tài)數(shù)組，類(lèi)似于string類(lèi)，可存放任意類(lèi)型，能夠末尾、中間增加數(shù)據(jù)，基本上是是new創(chuàng)建動(dòng)態(tài)數(shù)組的替代品，vector可以自動(dòng)完成new和delete2022-08-08
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言版五子棋游戲的實(shí)現(xiàn)代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-07-07