目錄

1、常見(jiàn)排序算法

1.1 插入排序基本思想

2、希爾排序

2.1 希爾排序( 縮小增量排序 )

2.1.1 預(yù)排序階段

2.1.2 插入排序階段

2.2 單趟希爾排序

2.2.1 思路分析

2.2.2 代碼實(shí)現(xiàn)

3、希爾排序代碼實(shí)現(xiàn)

4、希爾排序時(shí)間復(fù)雜度

5、希爾排序與插入排序效率對(duì)比

6、希爾排序特性總結(jié)

1、常見(jiàn)排序算法

1.1 插入排序基本思想

直接插入排序是一種簡(jiǎn)單的插入排序法，其基本思想是 ：
把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為
止，得到一個(gè)新的有序序列 。
實(shí)際中我們玩撲克牌時(shí)，就用了插入排序的思想

2、希爾排序

2.1 希爾排序( 縮小增量排序 )

希爾排序法又稱(chēng)縮小增量法。希爾排序法的基本思想是：先選定一個(gè)整數(shù)gap，把待排序文件中所有記錄分成多個(gè)組，所有距離相差為gap的記錄分在同一組內(nèi)，并對(duì)每一組內(nèi)的記錄進(jìn)行排序。然后，取gap=gap/3+1重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)gap=1時(shí)，所有記錄在統(tǒng)一組內(nèi)排好序。

我們畫(huà)圖來(lái)分析一下：我們這里是排升序

由圖我們其實(shí)可以看出來(lái)，當(dāng)最后一次gap=1時(shí)，本質(zhì)是插入排序，而希爾排序就是先預(yù)排序，最后再插入排序一次就實(shí)現(xiàn)了排序。

我們將上面的圖來(lái)分析一下：

2.1.1 預(yù)排序階段

1、第一趟，當(dāng)gap=5時(shí)，意思是每間隔5個(gè)數(shù)為一組，9與4，1與8，2與6，5與3，7與5分為一組，當(dāng)后面的數(shù)字小于前面的數(shù)字我們就交換，這樣我們就將這幾組中小的數(shù)字排到了前面，大的數(shù)字就排到了后面；

2、第二趟，我們就讓gap = gap/3+1（這里gap/3+1是為了最后能得到gap=1，當(dāng)gap<3時(shí)，如果只是除以3，得到的就是0，這樣就實(shí)現(xiàn)不了完全排序），gap=2，每間隔2個(gè)數(shù)為一組，4與2，5，8，5一組，1與3，9，6，7一組，比較大小，然后交換；

2.1.2 插入排序階段

3、當(dāng)調(diào)整gap=1時(shí)，本質(zhì)就是插入排序了，這時(shí)經(jīng)過(guò)了之前的預(yù)排序階段，我們的數(shù)字已經(jīng)接近有序了，但是不完全有序，此時(shí)上插入排序，效率提升會(huì)很大。

2.2 單趟希爾排序

2.2.1 思路分析

單趟的希爾排序其實(shí)就是將相隔為gap的數(shù)字分為一組，先進(jìn)行排序。

畫(huà)圖分析：

將單趟的每個(gè)間隔為gap的數(shù)字分為一組先進(jìn)行排序。

2.2.2 代碼實(shí)現(xiàn)

for (int i = 0; i < n - gap; i++)//多組一起排序（沒(méi)有提升效率，只是少寫(xiě)一組循環(huán)）
{
    int end = i;
    int tmp = a[i + gap];
    while (end >= 0)
    {
        if (a[end] > tmp)
        {
            a[end + gap] = a[end];
            end -= gap;
        }
        else
        {
            break;
        }
    }
    a[end + gap] = tmp;
}

3、希爾排序代碼實(shí)現(xiàn)

給單趟排序外面加一層循環(huán)，讓gap不斷縮小，直到為 1，就實(shí)現(xiàn)了希爾排序。

void ShellSort(int* a, int n)
{
	//1. 當(dāng) gap > 1 時(shí)先進(jìn)性預(yù)排序
	//2. 當(dāng) gap == 1 時(shí)直接插入排序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;// +1可以保證最后一次一定是1
		for (int i = 0; i < n - gap; i++)//多組一塊進(jìn)行
		{
			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、希爾排序時(shí)間復(fù)雜度

希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些書(shū)中給出的希爾排序的時(shí)間復(fù)雜度都不固定 。

以下是兩本書(shū)對(duì)希爾排序時(shí)間復(fù)雜度的描述：

我們這里的gap是按照Knuth提出的方式取值的，而且Knuth進(jìn)行了大量的試驗(yàn)統(tǒng)計(jì)，我們暫時(shí)就按照：O(n^1.25)到O(1.6*n^1.25)來(lái)算。

5、希爾排序與插入排序效率對(duì)比

我們分別開(kāi)辟兩個(gè)數(shù)組，都是100000大小，使用希爾排序與插入排序，對(duì)比所消耗的時(shí)間。

//時(shí)間對(duì)比
void TestOp()
{
	srand((unsigned int)time(NULL));
	const int n = 100000;
	int* a1 = (int*)malloc(sizeof(int) * n);
	int* a2 = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}

	int begin1 = clock();
	InsertSort(a1, n);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, n);
	int end2 = clock();


	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);

	free(a1);
	free(a2);
}

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

我們可以看出希爾排序要比插入排序的效率高出很多，當(dāng)數(shù)據(jù)量越大的時(shí)候，希爾排序的更占優(yōu)勢(shì)。

但是，當(dāng)數(shù)組本身就是有序的，希爾排序就比不過(guò)插入排序，因?yàn)橄柵判虼嬖陬A(yù)排序，執(zhí)行了就要花費(fèi)時(shí)間。

6、希爾排序特性總結(jié)

1. 希爾排序是對(duì)直接插入排序的優(yōu)化。
2. 當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測(cè)試的對(duì)比。
3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些書(shū)中給出的希爾排序的時(shí)間復(fù)雜度都不固定 。

4。穩(wěn)定性：不穩(wěn)定。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-543428.html

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