C++排序算法之插入排序怎么實(shí)現(xiàn)-創(chuàng)新互聯(lián)

這篇“C++排序算法之插入排序怎么實(shí)現(xiàn)”文章的知識點(diǎn)大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價(jià)值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“C++排序算法之插入排序怎么實(shí)現(xiàn)”文章吧。

創(chuàng)新互聯(lián)公司長期為超過千家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為新寧企業(yè)提供專業(yè)的網(wǎng)站設(shè)計(jì)、做網(wǎng)站，新寧網(wǎng)站改版等技術(shù)服務(wù)。擁有十載豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

1.基本思想：將未排序的數(shù)據(jù)元素按大小順序插入到已排好序數(shù)據(jù)序列中，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

例如：對2, 4, 3, 1, 6, 5進(jìn)行插入排序。進(jìn)行排序前，默認(rèn)2是有序的，為有序區(qū)，而4, 3, 1, 6, 5是無序的，為無序區(qū)。將這五個(gè)無序的數(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)無序區(qū)的第一個(gè)數(shù)據(jù)元素是有序的；
2.從以上例子可以看出，若對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--) // 無序區(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）次。平均來說插入排序算法的時(shí)間復(fù)雜度為O(n^2）。

注：插入排序不適合對于數(shù)據(jù)量比較大的排序應(yīng)用

以上就是關(guān)于“C++排序算法之插入排序怎么實(shí)現(xiàn)”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對大家有幫助，若想了解更多相關(guān)的知識內(nèi)容，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

新聞標(biāo)題：C++排序算法之插入排序怎么實(shí)現(xiàn)-創(chuàng)新互聯(lián)
標(biāo)題來源：http://www.bm7419.com/article30/dcohpo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)公司、關(guān)鍵詞優(yōu)化、云服務(wù)器、網(wǎng)站收錄、外貿(mào)建站、網(wǎng)站建設(shè)

廣告

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