C語言深入淺出講解直接插入排序算法的實(shí)現(xiàn)
插入排序分為兩種：直接插入排序&希爾排序
直接插入排序
1.基本思想
直接插入排序是一種簡(jiǎn)單的插入排序算法，其基本思想是：
把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列 。
說得通俗一點(diǎn)就是：
假設(shè)區(qū)間[0, end]有序，將end+1位置的值插入到[0, end]中，保持區(qū)間[0, end+1]依舊有序。
生活中我們玩撲克牌時(shí)，就用了插入排序的思想。
在這里，我們以排升序?yàn)槔?/p>
核心思想：摸牌的過程
動(dòng)圖演示：
2.算法實(shí)現(xiàn)
寫排序時(shí)，先從單趟開始考慮
//[0, end]已經(jīng)有序，將end+1位置的值插入到[0,end]中，使得[0,end+1]依舊保持有序
//有一個(gè)有序區(qū)間，插入一個(gè)數(shù)據(jù)，依舊保持有序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
//控制摸牌的過程，一開始從僅一張開始
//注意循環(huán)結(jié)束條件，只需要到n-2的位置，若將其改成i<n，則會(huì)出現(xiàn)越界的情況
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)//保證牌是有序的
{
if (a[end] > tmp)
{
a[end + 1] = a[end];//往后挪，注意畫圖感受哦
end--;
}
else
//有兩種可能：（現(xiàn)想常規(guī)的，再考慮特殊情況）
//一是找到了比它小的數(shù)，放到其后；
//二是沒有比它小的數(shù)，直到end為-1才結(jié)束
{
break;
}
}
a[end + 1] = tmp;
}
}
完整代碼：
3.時(shí)間復(fù)雜度
直接插入排序時(shí)間復(fù)雜度是O(N^2)，注意哦，不是因?yàn)殡p重循環(huán)，需要實(shí)際計(jì)算來得出時(shí)間復(fù)雜度。
最壞情況：逆序有序，1+2+3+……+n - 1；O(N^2)
最好情況：順序有序，1+1+1+……+1。O(N)
到此這篇關(guān)于C語言深入淺出講解直接插入排序算法的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C語言直接插入排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本篇文章是對(duì)使用C++實(shí)現(xiàn)DBSCAN聚類算法的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C語言break和continue的語句用法,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-04-04
這篇文章主要為大家介紹了C語言編程中使用MATLAB繪制橢圓及圓角矩形的實(shí)現(xiàn)源碼，有需要的朋友可以借鑒參考下，希望能夠有所幫助2022-02-02
淺析結(jié)束程序函數(shù)exit, _exit,atexit的區(qū)別
在一個(gè)程序中最多可以用atexit()注冊(cè)32個(gè)處理函數(shù)，這些處理函數(shù)的調(diào)用順序與其注冊(cè)的順序相反，也即最先注冊(cè)的最后調(diào)用，最后注冊(cè)的最先調(diào)用2013-09-09
這篇文章主要為大家詳細(xì)介紹了C/C++編程語言中的指針，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
C++數(shù)據(jù)結(jié)構(gòu)深入探究棧與隊(duì)列
棧和隊(duì)列，嚴(yán)格意義上來說，也屬于線性表，因?yàn)樗鼈円捕加糜诖鎯?chǔ)邏輯關(guān)系為 "一對(duì)一" 的數(shù)據(jù)，但由于它們比較特殊，本章講解分別用隊(duì)列實(shí)現(xiàn)棧與用棧實(shí)現(xiàn)隊(duì)列2022-05-05
關(guān)于C++中cout的使用，相信大家再熟悉不過了，然而對(duì)于cout是如何輸出的？輸出的機(jī)制是啥，需要進(jìn)一步的了解。本章娓娓道來。前幾天在網(wǎng)上看到這么一個(gè)題目2013-10-10
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)二叉樹基本操作，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能給你帶來幫助2021-08-08
C++實(shí)現(xiàn)LeetCode(104.二叉樹的最大深度)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(104.二叉樹的最大深度),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C++實(shí)現(xiàn)LeetCode(2.兩個(gè)數(shù)字相加)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(兩個(gè)數(shù)字相加),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07