🌟hello，各位讀者大大們你們好呀🌟

專業(yè)成都網(wǎng)站建設公司，做排名好的好網(wǎng)站，排在同行前面，為您帶來客戶和效益!創(chuàng)新互聯(lián)為您提供成都網(wǎng)站建設，五站合一網(wǎng)站設計制作，服務好的網(wǎng)站設計公司，做網(wǎng)站、網(wǎng)站制作負責任的成都網(wǎng)站制作公司!

🍭🍭系列專欄：【數(shù)據(jù)結構初階】

????本篇內容：深入剖析希爾排序

🚢🚢作者簡介：計算機海洋的新進船長一枚，請多多指教( ????? ) ??-

📡📡同期數(shù)據(jù)結構文章：【數(shù)據(jù)結構初階】C語言從0到1帶你了解直接插入排序

需要直接插入排序的基礎，才能更好的理解文章，詳情可見上欄同期數(shù)據(jù)結構文章

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

1.先進行預排序，將一組數(shù)分為 gap 組，對間隔為 gap 的數(shù)進行直接插入排序

void ShellSort(int* a, int n)
{
    int gap；
	int end;
	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;
}

至此，我們已經完成了一次插入排序，也就是可以將紅色組的9、5變得有序。接下來就是加入循環(huán)，完成多次插入排序，使間隔為 gap 的數(shù)組成的數(shù)組有序，以下圖紅色組為例，就是將 9，5，8，5 變得有序

2.加入循環(huán)，完成多次插入排序，使間隔為 gap 的數(shù)組成的數(shù)組有序

• 增加一個for循環(huán)，對紅色組進行排序
• n為數(shù)組長度，i< n - gap 避免越界（若 i

int gap = 3;
        for (int i = 0; i< n - gap; i += gap)
		{
			// [0,end] 插入 end+gap [0, end+gap]有序  -- 間隔為gap的數(shù)據(jù)
			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;
		}

至此，我們第一組（紅色組）就排完了，數(shù)組將會變成 5，1，2，5，7，4，8，6，3，9

3.再加一組循環(huán)，循環(huán) gap 次，使 gap 組的數(shù)都變得有序（以下數(shù)組為例，就是讓紅、藍、綠組都變得有序）

• 創(chuàng)建一個for循環(huán)，對不同顏色組排序
• 在這里，j = 0，排紅色組；j = 1，排藍色組；j = 2，排綠色組

void ShellSort(int* a, int n)
{
	int gap = 3;
	for (int j = 0; j< gap; ++j)
	{
		for (int i = j; i< n - gap; i += gap)
		{
			// [0,end] 插入 end+gap [0, end+gap]有序  -- 間隔為gap的數(shù)據(jù)
			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;
		}
	}	

4.算法優(yōu)化，三層循環(huán)變兩層循環(huán)（時間復雜度相同，所以寫上面的這種也行）

• 只需要將第二層循環(huán)?i += gap 變?yōu)??++i 即可，可以理解紅組，然后紅組9，5拍完，藍組1，7排，藍組排完綠組2，4排，以此類推。
• 不同于上面先給紅組排完，再給藍組排，藍組排完，再給綠組排

void ShellSort(int* a, int n)
{
	int gap = 3;
	for (int i = j; i< n - gap; ++i)
	{
		// [0,end] 插入 end+gap [0, end+gap]有序  -- 間隔為gap的數(shù)據(jù)
		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;
	}
}	

至此，我們已經完成了預排序， 完成了數(shù)組接近有序的目標，大大降低了對每個數(shù)直接排序的時間復雜度

5.對每個數(shù)進行直接插入排序，我們可以通過控制 gap 的值，來區(qū)分預排序和直接插入排序

• 當 gap == 1 時，這個算法就是直接插入排序
• 我們可以設 gap = n，再通過循環(huán)，不斷縮小gap的值，不斷預排序，使其最后變?yōu)橹苯硬迦肱判?/li>
• 通過大量實驗我們可以得出，gap / 2，或者 gap /?3+1 時，預排序的效果最好
• gap /?3+1 是為了保證除到最后的數(shù)=1，如3/3+1=1，4/3+1=2，2/3+1=1

// gap >1  預排序
	// gap == 1 直接插入排序

// O(N^1.3)
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap >1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;    //+1是為了保證除到最后的數(shù)=1

		// [0,end] 插入 end+gap [0, end+gap]有序  -- 間隔為gap的數(shù)據(jù)
		for (int i = 0; i< n - gap; ++i)
		{
			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;
		}
	}
}

6.我們將上述代碼補充完整，進行一次實驗

sort.h

#include#includevoid ShellSort(int* a, int n);

sort.c

void PrintArray(int* a, int n)
{
	for (int i = 0; i< n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

	// gap >1  預排序
	// gap == 1 直接插入排序

// O(N^1.3)
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap >1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;    //+1是為了保證除到最后的數(shù)=1

		// [0,end] 插入 end+gap [0, end+gap]有序  -- 間隔為gap的數(shù)據(jù)
		for (int i = 0; i< n - gap; ++i)
		{
			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;
		}
	}
}

test.c

void TestShellSort()
{
	//int a[] = { 9,8,7,6,5,4,3,2,1,0 };
	int a[] = { 34, 56, 25, 65, 86, 99, 72, 66 };
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}


int main()
{
    TestShellSort();
	return 0;
}

結果如下??

1. 希爾排序是對直接插入排序的優(yōu)化。
2. 當gap >1時都是預排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。
3. 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些樹中給出的希爾排序的時間復雜度都不固定，我們可以使用Knuth的取值或者大概平均值O(n^1.3)，對比下略差于O(n*logn)的算法
4. 穩(wěn)定性：不穩(wěn)定

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

🌹🌹希爾排序排序大概就講到這里啦，博主后續(xù)會繼續(xù)更新更多數(shù)據(jù)結構的相關知識，干貨滿滿，如果覺得博主寫的還不錯的話，希望各位小伙伴不要吝嗇手中的三連哦！你們的支持是博主堅持創(chuàng)作的動力！💪💪?

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧