“至若春和景明，波瀾不驚，上下天光，一碧萬(wàn)頃，沙鷗翔集，錦鱗游泳，岸芷汀蘭，郁郁青青。”

C語(yǔ)言朱武大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)專欄

C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)快速排序圖文示例

C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)堆排序圖文示例

C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹遞歸

前言

學(xué)習(xí)希爾排序要先學(xué)習(xí)插入排序，希爾排序是在插入排序上的優(yōu)化，可以這么說(shuō)，插入排序你只要會(huì)了，希爾排序的學(xué)習(xí)也就是水到渠成。

一、插入排序

假如給你以下代碼，讓你對(duì) 5 4 3 2 1 排升序，你會(huì)怎么排？會(huì)怎么寫？

5 4 3 2 1

void InsertSort(int* a, int n)
{
	//排序代碼
}
int main()
{
	int arr[] = { 5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	InsertSort(arr, sz);
	return 0;
}

1.排序思路

思路：總體來(lái)說(shuō)是分治思想，把大問(wèn)題化為小問(wèn)題來(lái)解決。想讓5,4,3,2,1有序。

1.第一趟：從下標(biāo)為1的位置依次往后開始，先讓5,4為升序

2.第二趟：來(lái)到下標(biāo)為2的位置，讓5,4,3為升序

3.第三趟：來(lái)到下標(biāo)為3的位置，讓5,4,3,2為升序

4.第四趟：來(lái)到下標(biāo)為3的位置，讓5,4,3,2,1為升序

這樣下來(lái)，總體就都為升序了

所以總體來(lái)說(shuō)，在最壞情況下。5個(gè)數(shù)排了(5-1)躺就有序了.

所以最壞情況下n個(gè)數(shù)排n-1躺才能有序。

2.單趟排序

萬(wàn)物歸根，學(xué)習(xí)任何排序先從單趟排序開始。

可以說(shuō)關(guān)鍵思想在單躺排序中。

以第三趟排序?yàn)槔?。因?yàn)檫@趟排序有畫圖意義

思路：

第三趟：來(lái)到下標(biāo)為3的位置，讓5,4,3,2為升序

1.起始狀態(tài)。因?yàn)槟茏叩降谌伺判颍f(shuō)明第一趟和第二趟已經(jīng)排好序了，以紅色線分割這時(shí)的數(shù)據(jù)為3 4 5 2 1

2.定義指針end指向有序序列的最后一個(gè)數(shù)，讓tmp保存end+1位置的值。(這樣可以防止end+1指向的值被覆蓋后找不到)

3.開始打擂臺(tái)賽。比較tmp的值和end的值的大小，然后end–。把比tmp大的值依次往后挪動(dòng)。直到 end < 0越界 或者 tmp比end指向的值大時(shí)，單趟排序才完成。

詳細(xì)圖解

(1). tmp為 2 小于 5, 執(zhí)行a[end+ 1] = a[end];把end+1上的值覆蓋。end = end - 1。

(2). 2小于 4，繼續(xù)重復(fù)以上步驟。

(3).2小于 4，繼續(xù)重復(fù)以上步驟。

(4).end此時(shí)越界。直接跳出循環(huán)，將tmp賦值給a[end + 1];

這樣就完成了單趟排序的解釋。

3.整體代碼

#include <stdio.h>
void InsertSort(int* a, int n)
{
	int i = 0;
	//總共n-1躺排序
	for (i = 0; i < n - 1; i++)
	{
		//單趟排序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			//打擂臺(tái)賽
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end = end - 1;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
int main()
{
	int arr[] = { 5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	InsertSort(arr, sz);
	return 0;
}

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

為了更好的展開對(duì)希爾排序敘述，不得不說(shuō)一下插入排序的時(shí)間復(fù)雜度。

(1).最壞情況下

最壞情況下：對(duì)降序排降序。比如對(duì)5 4 3 2 1排升序。1.假如有n個(gè)降序的數(shù)。需要排n-1躺。

2.第1趟比較1次，第2趟比較2次，第3躺比較3次。第n-1躺排n-1次。

3.由 等差數(shù)列 前n項(xiàng)和公式 (首項(xiàng) + 末項(xiàng)) * 項(xiàng)數(shù) / 2 得。

T(n) = (n-1)*(1 + n - 1)/2

T(n) = (n-1)*n / 2

所以最壞情況下時(shí)間復(fù)雜度為(N-1)*N / 2。

4.由大O漸進(jìn)法表示為O(N2)。

(2).最好情況下

最好情況下：對(duì)升序排升序。比如對(duì)1 2 3 4 5排升序。

這時(shí)，假如有n個(gè)元素。只需要對(duì)數(shù)組遍歷一遍就夠了，一遍也就是N-1次。

所以時(shí)間復(fù)雜度為O(N)

(3).基本有序情況下(重點(diǎn))

例如：2 3 1 5 4

這個(gè)時(shí)候排升序，大概時(shí)間復(fù)雜度在 N ~ N2 之間接近 O(N).

5.算法特點(diǎn)

1.是穩(wěn)定排序

2.代碼簡(jiǎn)單，易實(shí)現(xiàn)

3.在數(shù)據(jù)接近有序 或者 已經(jīng)有序的情況下，時(shí)間復(fù)雜度為O(N)

二、希爾排序

因 D.L.Shell 大佬于 1959 年提出而得名。

希爾排序(Shell’s Sort)是插入排序的一種又稱“縮小增量排序”，是直接插入排序算法的一種更高效的改進(jìn)版本。——百度百科

假如給你以下數(shù)據(jù)和代碼，讓你寫希爾法排 升序，你會(huì)怎么寫？你會(huì)怎么排？

9,8,7,6,5,4,3,2,1

void ShellSort(int* a, int n)
{
	//排序代碼
}
int main()
{
	int arr[] = { 9,1,2,5,7,4,1,6,3,5 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	ShellSort(arr, sz);
	return 0;
}

1.希爾從哪個(gè)方面優(yōu)化的插入排序？

1.因?yàn)椴迦肱判蛴?個(gè)特性：當(dāng)待排序的個(gè)數(shù)基本有序 和 數(shù)據(jù)個(gè)數(shù)較少 時(shí) 插入效率較高。

2.所以希爾排序基于這2個(gè)特性，先依據(jù)間隔(gap)對(duì)數(shù)據(jù)分成各個(gè)小組，然后對(duì)各組進(jìn)行預(yù)排序，使得數(shù)據(jù)基本有序，最后再進(jìn)行一次普通的插入排序使數(shù)據(jù)整體有序。

2.排序思路

排序?qū)嵸|(zhì)：實(shí)質(zhì)是采用分組插入的方法。

其實(shí)還是插入排序的思路。只是把數(shù)據(jù)分割為好幾組。然后對(duì)每組進(jìn)行插入排序。

整體思路：

1.算法先將要排序的一組數(shù)按某個(gè)增量gap分成若干組，每組中記錄的下標(biāo)相差gap.

2.對(duì)每組中全部元素進(jìn)行預(yù)排序，然后再用一個(gè)較小的增量對(duì)它進(jìn)行分組，在每組中再進(jìn)行預(yù)排序。

3.當(dāng)增量 等于1 時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。(這時(shí)候相當(dāng)于 普通的插入排序 了)

3.預(yù)排序

以以下10個(gè)元素為例。

9,1,2,5,7,4,1,6,3,5

預(yù)排序：是對(duì)各個(gè)間隔(gap) 不為1 的小組 進(jìn)行直接插入排序。要理解這句話請(qǐng)繼續(xù)往下看。

關(guān)于多少間隔分一組這個(gè)問(wèn)題，怎么分？不要想那么多，按照以下規(guī)則分，你就自然懂了。分組規(guī)則：

1.間隔(gap)每次一半一半的分。直到最后gap == 1.

2.這樣分其實(shí)每次都是折半的，常識(shí)來(lái)說(shuō)：折半的時(shí)間復(fù)雜度都為O(LogN).

#include <stdio.h>
//希爾排序
void ShellSort(int* a, int n)
{
	//預(yù)排序
	int gap = n;
	while (gap > 1)
	{
		//每次gap折半
		gap = gap / 2;
	}
}
int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	ShellSort(arr, sz);
	return 0;
}

以上例子有10個(gè)數(shù)。那就可以達(dá)到5個(gè)間隔分一組。2個(gè)間隔分一組。還有最后的1個(gè)間隔分一組(預(yù)排序不包括gap == 1這一組)。

1.gap == 5的分一組進(jìn)行間隔為5的插入排序。

此時(shí)排完序結(jié)果為 4 1 2 3 5 9 8 6 5 7

2.gap == 2的分一組，進(jìn)行間隔(gap)為2的插入排序

此時(shí)排完序結(jié)果為 2 1 4 3 5 6 5 7 8 9

這時(shí)預(yù)排序已經(jīng)完成。數(shù)據(jù)基本接近有序開始進(jìn)行g(shù)ap為1的插入排序。

4.正式排序

此時(shí)gap == 1.直接插入排序

5.整體代碼

實(shí)質(zhì)：其實(shí)就是加了一個(gè)預(yù)排序，然后把 插入排序任何為1的地方替換為 gap。

#include <stdio.h>
//希爾排序
void ShellSort(int* a, int n)
{
	//預(yù)排序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 2;
		//進(jìn)行間隔為gap的插入排序
		int i = 0;
		for (i = 0; i < n - gap; i++)
		{
			//單趟排序
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end = end - gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	ShellSort(arr, sz);
	return 0;
}

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

在嚴(yán)蔚敏老師的書上沒(méi)有具體說(shuō)怎么算。因?yàn)樯婕耙恍?shù)學(xué)上尚未解決的難題。

只給了個(gè)結(jié)論，時(shí)間復(fù)雜度為O(N3/2)

在網(wǎng)上有一個(gè)很巧計(jì)算方法。只是估算。僅供參考

(1).while循環(huán)的復(fù)雜度

1.假如有n個(gè)數(shù)據(jù)。n一直初以2.最后要等于1.所以公式為n / 2 / 2 / 2 / 2 / 2… = 1.

2.所以設(shè)需要初以 x 個(gè)2。也就是要執(zhí)行 x 次。所以n = 2x.

所以 x = Log2n.

3.每次gap減半的 ，也就是while循環(huán)的 時(shí)間復(fù)雜度就是Log2N

	int gap = n;
	while (gap > 1)
	{
		//每次gap折半
		gap = gap / 2;
	}

(2).每組gap的時(shí)間復(fù)雜度

以下說(shuō)法只是估算。

在預(yù)排序階段。gap很大

1.gap很大很大時(shí)，數(shù)據(jù)跳的很快，差不多時(shí)間復(fù)雜度為O(N).正式排序時(shí)，gap == 1.

2.gap很小，因?yàn)閿?shù)據(jù)接近有序，所以時(shí)間復(fù)雜度也差不多是O(N)

結(jié)論：

所以整個(gè)代碼的時(shí)間復(fù)雜度為O(N*LogN).

希爾排序空間復(fù)雜度也是O(1)，因?yàn)檫€是只需要一個(gè)輔助空間tmp。

以上就是C語(yǔ)言希爾排序算法實(shí)現(xiàn)植物大戰(zhàn)示例的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言希爾排序的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論