?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???? ?? ??
??個人主頁 ：阿然成長日記 ??點擊可跳轉(zhuǎn)
?? 個人專欄： ??數(shù)據(jù)結(jié)構(gòu)與算法??C語言進階
?? 不能則學，不知則問，恥于問人，決無長進
?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??

前言：

本篇將開始希爾排序的講解。本篇文章適合剛開始學習希爾排序的同學，總結(jié)的很全面，整理的很清楚，希望能幫到你，加油！

一、希爾定義：

希爾排序是希爾(Donald Shell)于1959年提出的一種排序算法，其也是一種特殊的插入排序，即將簡單的插入排序進行改進后的一個更加高效的版本，也稱 縮小增量排序

二、希爾排序原理

希爾排序的思路是，它通過將待排序的數(shù)組分割成多個子序列來進行排序。然后逐步縮小子序列的規(guī)模，最終進行一次插入排序，從而實現(xiàn)將整個數(shù)組排序的目的，當被排序的對象越接近有序時，插入排序的效率越高。希爾排序利用這一特點，通過將數(shù)組變得接近有序，從而提高插入排序的效率。

三、希爾排序原理圖

gap值的計算公式：gap=n/3+1;

1.gap為3：

三組分別進行排序，將較小值換到左邊。

是不是看起來就有序多了。繼續(xù)縮小gap的值。

2.gap為2：

第一組：1，8，7
第二組：4，5，9
對兩組進行排序：

看起來更加有序了。繼續(xù)縮小gap的值。

3.gap為1：

當gap=1時，就相當于插入排序；

排序后：就是一個有序數(shù)組了。

插入排序

四、細節(jié)剖析

我們分析一下gap=2時的具體排序過程：

注：圖中的 tmp>end 指的是 a[tmp] 和 a[end]

第1步：i=0; a[tmp] > a[end]不做交換

i++；

第2步：i=1; a[tmp] > a[end]不做交換

i++；

第3步：i=2; a[tmp] < a[end]交換

在這里就會有一些變化了，end在比較交換完后會執(zhí)行語句 end -= gap ; 所以，end會繼續(xù)向前移動gap個位置，再次進行比較交換。從而看起來像是0，2，4位置為一組。

第3步：</fonti=2; a[tmp] > a[end] 不交換

i++；

第5步：i=3; a[tmp] > a[end]不交換

第6步：i=3; a[tmp] > a[end]不交換

停止

i++；這里i的值為4，不滿足執(zhí)行條件 n - gap；退到外層循環(huán)，gap的值縮小為1；

五、代碼展示：

//希爾排序
//從下標0開始，從0+gap步開始，進行插入排序，
//每次選擇一個使用遍歷向前尋找是否有比他小的記下位置，最后交換
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				//不符合就向后移動，已經(jīng)保存到tmp中，不用擔心被覆蓋
				if (tmp < a[end])
				{
					a[end+gap] = a[end];
					end -=gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

六、測試結(jié)果

七、 時間復(fù)雜度

文章來源地址http://www.zghlxwxcb.cn/news/detail-721048.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)--八大排序】之希爾排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！