C語言希爾排序算法實現植物大戰示例

Posted on by

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

前言

學習希爾排序要先學習插入排序，希爾排序是在插入排序上的優化，可以這麼說，插入排序你隻要會瞭，希爾排序的學習也就是水到渠成。

一、插入排序

假如給你以下代碼，讓你對 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.第一趟：從下標為1的位置依次往後開始，先讓5,4為升序

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

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

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

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

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

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

2.單趟排序

萬物歸根，學習任何排序先從單趟排序開始。

可以說關鍵思想在單躺排序中。

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

思路：

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

1.起始狀態。因為能走到第三趟排序，說明第一趟和第二趟已經排好序瞭，以紅色線分割這時的數據為3 4 5 2 1

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

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

詳細圖解

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

(2). 2小於 4，繼續重復以上步驟。

(3).2小於 4，繼續重復以上步驟。

(4).end此時越界。直接跳出循環，將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.時間復雜度

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

(1).最壞情況下

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

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

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

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

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

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

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

(2).最好情況下

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

這時，假如有n個元素。隻需要對數組遍歷一遍就夠瞭，一遍也就是N-1次。

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

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

例如：2 3 1 5 4

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

5.算法特點

1.是穩定排序

2.代碼簡單，易實現

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

二、希爾排序

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

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

假如給你以下數據和代碼，讓你寫希爾法排 升序，你會怎麼寫？你會怎麼排？

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

1.因為插入排序有2個特性：當待排序的個數基本有序 和 數據個數較少 時 插入效率較高。

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

2.排序思路

排序實質：實質是采用分組插入的方法。

其實還是插入排序的思路。隻是把數據分割為好幾組。然後對每組進行插入排序。

整體思路：

1.算法先將要排序的一組數按某個增量gap分成若幹組，每組中記錄的下標相差gap.

2.對每組中全部元素進行預排序，然後再用一個較小的增量對它進行分組，在每組中再進行預排序。

3.當增量 等於1 時，整個要排序的數被分成一組，排序完成。(這時候相當於 普通的插入排序 瞭)

3.預排序

以以下10個元素為例。

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

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

關於多少間隔分一組這個問題，怎麼分？不要想那麼多，按照以下規則分，你就自然懂瞭。分組規則：

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

2.這樣分其實每次都是折半的，常識來說：折半的時間復雜度都為O(LogN).

#include <stdio.h>
//希爾排序
void ShellSort(int* a, int n)
{
	//預排序
	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個數。那就可以達到5個間隔分一組。2個間隔分一組。還有最後的1個間隔分一組(預排序不包括gap == 1這一組)。

1.gap == 5的分一組進行間隔為5的插入排序。

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

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

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

這時預排序已經完成。數據基本接近有序開始進行gap為1的插入排序。

4.正式排序

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

5.整體代碼

實質：其實就是加瞭一個預排序，然後把 插入排序任何為1的地方替換為 gap。

#include <stdio.h>
//希爾排序
void ShellSort(int* a, int n)
{
	//預排序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 2;
		//進行間隔為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.時間復雜度

在嚴蔚敏老師的書上沒有具體說怎麼算。因為涉及一些數學上尚未解決的難題。

隻給瞭個結論，時間復雜度為O(N3/2)

在網上有一個很巧計算方法。隻是估算。僅供參考

(1).while循環的復雜度

1.假如有n個數據。n一直初以2.最後要等於1.所以公式為n / 2 / 2 / 2 / 2 / 2… = 1.

2.所以設需要初以 x 個2。也就是要執行 x 次。所以n = 2x.

所以 x = Log2n.

3.每次gap減半的 ，也就是while循環的 時間復雜度就是Log2N

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

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

以下說法隻是估算。

在預排序階段。gap很大

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

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

結論：

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

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

以上就是C語言希爾排序算法實現植物大戰示例的詳細內容，更多關於C語言希爾排序的資料請關註LevelAH其它相關文章！

推薦閱讀：