活動(dòng)地址：CSDN21天學(xué)習(xí)挑戰(zhàn)賽

??作者簡介：大家好我是小唐同學(xué)(?>?<?），為夢想而奮斗的小唐，讓我們一起加油?。?！

個(gè)人主頁：小唐同學(xué)(?>?<?）的博客主頁

系列專欄：數(shù)據(jù)結(jié)構(gòu)

博友們?nèi)绻彩切率秩腴T數(shù)據(jù)結(jié)構(gòu)我希望大家可以多加練習(xí) 數(shù)據(jù)結(jié)構(gòu)題庫在?？途W(wǎng)就有已經(jīng)給大家附上鏈接，可以直接點(diǎn)擊跳轉(zhuǎn)：刷題點(diǎn)這里

?？途W(wǎng)支持ACM模式哦，刷算法題也很推薦哦?。?！

下面上文章------》

目錄

希爾排序介紹：

?希爾排序分組：

算法步驟：

輸入：

輸出：

算法理解：

實(shí)例代碼：

?復(fù)雜度分析：

? ?時(shí)間復(fù)雜度：

? ?空間復(fù)雜度：

希爾排序介紹：

希爾排序?qū)嶋H上就是將一組數(shù)據(jù)進(jìn)行分組排序（等距元素為一組進(jìn)行排序），在每一組內(nèi)進(jìn)行直接插入排序，讓后每一次減少間距，進(jìn)行排序，到距離為1結(jié)束。

希爾排序也可以認(rèn)為直接插入排序的優(yōu)化版，優(yōu)化肯定要從直接插入排序的優(yōu)點(diǎn)來想

（1）在待排序序列基本有序時(shí)，直接插入排序效率會(huì)大大提高。

（2）在待排元素?cái)?shù)量較小時(shí)，直接插入排序效率也會(huì)大大提高。

希爾排序就是把這兩個(gè)優(yōu)點(diǎn)給放大、利用起來。??

?希爾排序分組：

希爾排序是如何進(jìn)行分組那？

對于這個(gè)d應(yīng)該會(huì)產(chǎn)生疑惑的，

d1=n/2(n為元素的數(shù)量---第一次距離)

d2=d1/2;(向后遞推)

dn+1=dn/2

當(dāng)d=1時(shí)結(jié)束。

算法步驟：

輸入：

一個(gè)數(shù)組（可以任一序列）

數(shù)據(jù)存儲(chǔ)時(shí)要從數(shù)組的1開始存儲(chǔ)? ?下標(biāo)為0的位置是用來做中間臨時(shí)量，用來進(jìn)行比較

輸出：

輸出一個(gè)有序序列

算法理解：

希爾排序我們理解起來可以與直接插入排序進(jìn)行比較，畢竟希爾排序也是在直接插入排序基礎(chǔ)上進(jìn)行的，無非就是多了分組的步驟，那我們可以理解為在組內(nèi)進(jìn)行直接插入排序，但是組之間距離為d,所以我們理解的希爾可以根據(jù)直接插入排序進(jìn)行理解，需要把直接插入排序中+1的地方換成+d

實(shí)例代碼：

#include <stdio.h>
int main()
{
	int n;
	scanf("%d",&n);
	int a[n+1];
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int j;

	int d;
	for(d=n/2;d>=1;d=d/2)
	{
		for(int i=d+1;i<=n;i++) //j是用來比較前方元素 i是向后循環(huán) 
		{
			a[0]=a[i];
			j=i-d;
			while(j>0&&a[0]<a[j])
			{
				a[j+d]=a[j]; 
				j=j-d;
			}
			a[j+d]=a[0];
//因?yàn)樘鲅h(huán)時(shí)j-d了，然而a[0]比-d后的a[j]大所以它在后邊  所以j+d要+回來 
		}
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	}
	
	
 } 

?復(fù)雜度分析：

? ?時(shí)間復(fù)雜度：

時(shí)間復(fù)雜度是不確定的，根據(jù)d的取值不同是沒辦法確定的

? ?空間復(fù)雜度：

在希爾排序中只是借用了幾個(gè)臨時(shí)變量；

則空間復(fù)雜度為：O(1)。文章來源地址http://www.zghlxwxcb.cn/news/detail-561110.html

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