總體是按照·數(shù)組下標(biāo)由小到大進(jìn)行排序

對一個(gè)數(shù)組arr進(jìn)行排序從第一個(gè)位置下標(biāo)為0開始，與下標(biāo)為1進(jìn)行比較：

如果arr[0]>arr[1]，將arr[0]后移至arr[1]的位置，再將arr[1]插入arr[0]的位置就完成了排序，再繼續(xù)向后讀取排序即可。
如果arr[0]<arr[1]，即為升序，繼續(xù)向后讀取排序即可。

當(dāng)插入到第i（i>=0）個(gè)元素時(shí)，前面的arr[0],arr[1]…arr[i-1]都已經(jīng)排好序，此時(shí)將arr[i]對應(yīng)數(shù)值與arr[i-1],arr[i-2]…對應(yīng)的數(shù)值依次進(jìn)行排序比較，大于arr[i]的數(shù)值依次向后移動(dòng)一個(gè)數(shù)據(jù)位置大小(假設(shè)arr[i-1]大于arr[i],就將arr[i-1]后移止arr[i]的位置)，arr[i]繼續(xù)向前進(jìn)行比較，直到遇到比arr[i]小的數(shù)時(shí)，將arr[i]插入到其前面位置即可

按照數(shù)組下標(biāo)順序，以此執(zhí)行上面操作，直到將數(shù)組中最后一個(gè)數(shù)據(jù)排完為止，即可實(shí)現(xiàn)升序。

動(dòng)態(tài)圖解:

1.3 代碼實(shí)現(xiàn)

//時(shí)間復(fù)雜度
//最壞情況O(N^2),逆序
//最好情況O（N）
void InsertSort(int* a, int n)
{
	assert(a);

	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];

		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

1.4 直接插入排序的特性總結(jié)

1. 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高

2. 時(shí)間復(fù)雜度：O(N^2)

4. 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法

5. 穩(wěn)定性：穩(wěn)定

2.希爾排序 ShellSort

2.1 基本思想

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：

先選定一個(gè)gap整數(shù)，把待排序文件中所有記錄分成gap個(gè)組，所有距離為gap的整數(shù)記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進(jìn)行排序。然后減小gap，重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)gap=1時(shí)，所有記錄在統(tǒng)一組內(nèi)排好序。

2.2 實(shí)現(xiàn)原理

希爾排序相當(dāng)于是對直接插入排序進(jìn)行了優(yōu)化
直接插入排序就相當(dāng)于把gap直接當(dāng)作1進(jìn)行插入排序，而希爾排序不同

希爾排序分為預(yù)排序和最終排序兩部進(jìn)行且開始gap等于數(shù)組數(shù)據(jù)個(gè)數(shù)n，gap減小到1之前所進(jìn)行的排序都為預(yù)排序，只有最后gap=1時(shí)的排序?yàn)樽罱K排序

希爾排序之所以快是預(yù)排序在起作用，預(yù)排序的目標(biāo)是讓整體數(shù)組接近有序，而總體預(yù)排序消耗的時(shí)間又很少，其對最終排序的使用時(shí)間有很大增益效果

注意：這里以gap /= 2為例，進(jìn)行動(dòng)態(tài)圖解
動(dòng)態(tài)圖解：

2.3 代碼實(shí)現(xiàn)

注意：這里代碼是以gap = gap/3+1為例，時(shí)間復(fù)雜度為O(N^1.3)。（具體說明在特性里面）

//希爾排序 時(shí)間復(fù)雜度O（N^1.3）
//欲排序 目標(biāo)接近有序
void ShellSort(int* a, int n)
{
	assert(a);

	int gap = n;
	while (gap > 1)
	{
		gap  = gap/3 + 1;
		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
					a[end + gap] = tmp;
				}
			}
		}
	}
}

2.4希爾排序的特性總結(jié)

1. 希爾排序是對直接插入排序的優(yōu)化。

2. 當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。

3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，因此在一些樹中給出的希爾排序的時(shí)間復(fù)雜度都不固定：

《數(shù)據(jù)結(jié)構(gòu)-用面相對象方法與C++描述》— 殷人昆

因?yàn)樵蹅兊膅ap是按照Knuth提出的方式取值的，而且Knuth進(jìn)行了大量的試驗(yàn)統(tǒng)計(jì)，我們暫時(shí)就按照：O（N^1.3）來算。

4.穩(wěn)定性：不穩(wěn)定。

二、完結(jié)撒?

如果以上內(nèi)容對你有幫助不妨點(diǎn)贊支持一下，以后還會(huì)分享更多編程知識(shí)，我們一起進(jìn)步。
最后我想講的是，據(jù)說點(diǎn)贊的都能找到漂亮女朋友?
文章來源地址http://www.zghlxwxcb.cn/news/detail-848609.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)進(jìn)階篇 之 【插入排序】詳細(xì)講解（直接插入排序，希爾排序）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！