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

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

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

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

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

前言

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

一、插入排序

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

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.排序思路

思路：總體來說是分治思想，把大問題化為小問題來解決。想讓5,4,3,2,1有序。

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

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

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

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

這樣下來，總體就都為升序了

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

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

2.單趟排序

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

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

以第三趟排序為例。因為這趟排序有畫圖意義

思路：

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

1.起始狀態(tài)。因為能走到第三趟排序，說明第一趟和第二趟已經(jīng)排好序了，以紅色線分割這時的數(shù)據(jù)為3 4 5 2 1

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

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

詳細(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此時越界。直接跳出循環(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)
		{
			//打擂臺賽
			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.時間復(fù)雜度

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

(1).最壞情況下

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

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

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

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

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

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

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

(2).最好情況下

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

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

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

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

例如：2 3 1 5 4

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

5.算法特點(diǎn)

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

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

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

二、希爾排序

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

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

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

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.希爾從哪個方面優(yōu)化的插入排序？

1.因為插入排序有2個特性：當(dāng)待排序的個數(shù)基本有序 和 數(shù)據(jù)個數(shù)較少 時 插入效率較高。

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

2.排序思路

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

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

整體思路：

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

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

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

3.預(yù)排序

以以下10個元素為例。

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

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

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

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

2.這樣分其實(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個數(shù)。那就可以達(dá)到5個間隔分一組。2個間隔分一組。還有最后的1個間隔分一組(預(yù)排序不包括gap == 1這一組)。

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

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

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

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

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

4.正式排序

此時gap == 1.直接插入排序

5.整體代碼

實(shí)質(zhì)：其實(shí)就是加了一個預(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.時間復(fù)雜度

在嚴(yán)蔚敏老師的書上沒有具體說怎么算。因為涉及一些數(shù)學(xué)上尚未解決的難題。

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

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

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

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

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

所以 x = Log2n.

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

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

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

以下說法只是估算。

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

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

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

結(jié)論：

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

希爾排序空間復(fù)雜度也是O(1)，因為還是只需要一個輔助空間tmp。

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

最新評論