快捷導(dǎo)航

C語(yǔ)言深入淺出講解直接插入排序算法的實(shí)現(xiàn)

更新時(shí)間：2022年05月18日 10:53:02 作者：安然無(wú)虞

插入排序也是最簡(jiǎn)單的一類排序方法，我今天介紹的也是插入排序里最直觀且淺顯易懂的直接插入排序。對(duì)這個(gè)很簡(jiǎn)單的排序，記得當(dāng)時(shí)也是花了近兩個(gè)晚上才搞懂它的原理的，接下來(lái)就來(lái)介紹一下

直接插入排序

1.基本思想

直接插入排序是一種簡(jiǎn)單的插入排序算法，其基本思想是：

把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列。

說(shuō)得通俗一點(diǎn)就是：

假設(shè)區(qū)間[0, end]有序，將end+1位置的值插入到[0, end]中，保持區(qū)間[0, end+1]依舊有序。

生活中我們玩撲克牌時(shí)，就用了插入排序的思想。

在這里，我們以排升序?yàn)槔?/p>

核心思想：摸牌的過(guò)程

動(dòng)圖演示：

2.算法實(shí)現(xiàn)

寫排序時(shí)，先從單趟開(kāi)始考慮

//[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++)
	//控制摸牌的過(guò)程，一開(kāi)始從僅一張開(kā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ù)，放到其后；
			//二是沒(méi)有比它小的數(shù)，直到end為-1才結(jié)束
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

完整代碼：

3.時(shí)間復(fù)雜度

直接插入排序時(shí)間復(fù)雜度是O(N^2)，注意哦，不是因?yàn)殡p重循環(huán)，需要實(shí)際計(jì)算來(lái)得出時(shí)間復(fù)雜度。

最壞情況：逆序有序，1+2+3+……+n - 1；O(N^2)

最好情況：順序有序，1+1+1+……+1。O(N)

到此這篇關(guān)于C語(yǔ)言深入淺出講解直接插入排序算法的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C語(yǔ)言直接插入排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

相關(guān)文章

C++編輯距離（動(dòng)態(tài)規(guī)劃）
這篇文章主要介紹了C++編輯距離（動(dòng)態(tài)規(guī)劃），編輯距離是指兩個(gè)字符串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)，限免詳細(xì)內(nèi)容，需要的小伙伴可以參考一下
2022-01-01
C++ 標(biāo)準(zhǔn)模板庫(kù) STL 順序容器詳解
這篇文章主要介紹了C++ 標(biāo)準(zhǔn)模板庫(kù) STL 順序容器詳解,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2021-05-05
VS2019配置BOOST的方法(v1.70.0庫(kù))
這篇文章主要介紹了VS2019配置BOOST的方法(v1.70.0庫(kù))，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2020-08-08
C++缺省參數(shù)、函數(shù)重載與引用深入解析
缺省參數(shù)函數(shù)重載以及引用的出現(xiàn)是為了補(bǔ)充C語(yǔ)言語(yǔ)法的不足以及對(duì)C語(yǔ)言設(shè)計(jì)不合理的地方進(jìn)行優(yōu)化,引用的出現(xiàn)大大降低了我們學(xué)習(xí)C語(yǔ)言時(shí)相對(duì)于指針的難度,也便于我們更好的理解和使用,感興趣的朋友一起看看吧
2024-04-04
C語(yǔ)言結(jié)構(gòu)體指針的具體使用
結(jié)構(gòu)體指針是一種非常有用的數(shù)據(jù)類型，它可以讓我們更方便地操作結(jié)構(gòu)體，本文主要介紹了C語(yǔ)言結(jié)構(gòu)體指針的具體使用，非常具有實(shí)用價(jià)值，需要的朋友可以參考下
2023-05-05
C語(yǔ)言中枚舉與指針的實(shí)例詳解
這篇文章主要介紹了 C語(yǔ)言中枚舉與指針的實(shí)例詳解的相關(guān)資料,希望通過(guò)本文大家能夠掌握枚舉與指針的知識(shí)，需要的朋友可以參考下
2017-09-09
C語(yǔ)言qsort函數(shù)使用方法詳解
qsort是一個(gè)庫(kù)函數(shù),基于快速排序算法實(shí)現(xiàn)的一個(gè)排序的函數(shù),下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言qsort()函數(shù)使用的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
2022-09-09
c語(yǔ)言中字符串函數(shù)(庫(kù)函數(shù)使用)和模擬實(shí)現(xiàn)圖文教程
C語(yǔ)言中對(duì)字符和字符串的處理很是頻繁,但是C語(yǔ)言本身并沒(méi)有字符串類型,這篇文章主要給大家介紹了關(guān)于c語(yǔ)言中字符串函數(shù)(庫(kù)函數(shù)使用)和模擬實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下
2024-01-01
C++實(shí)現(xiàn)浮點(diǎn)數(shù)精確加法
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)浮點(diǎn)數(shù)精確加法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-05-05
C 語(yǔ)言基礎(chǔ)教程(我的C之旅開(kāi)始了)[八]
C 語(yǔ)言基礎(chǔ)教程(我的C之旅開(kāi)始了)[八]...
2007-02-02