一、 直接插入排序

1.1 插入排序原理

直接插入排序是一種簡(jiǎn)單的插入排序法，其基本原理是：
把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列 。
?

而實(shí)際中我們玩撲克牌時(shí)，就用了插入排序的思想

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

【代碼思路】：直接插入排序還是比較簡(jiǎn)單的。我們將第一個(gè)元素當(dāng)作一個(gè)有序序列，然后從第二個(gè)元素開始，將其作為當(dāng)前插入的元素，并與已排序部分的元素進(jìn)行比較，找到合適的插入位置。然后不斷重復(fù)上述操作，直到所有元素都被插入到已排序部分。
?
當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的a[0], a[1], …, a[i-1]已經(jīng)排好序，此時(shí)用a[i]的排序碼與a[i-1],a[i-2],…的排序碼順序進(jìn)行比較，找到插入位置即將a[i]插入，原來位置上的元素順序后移。

void InsertSort(int* a, int n)//排升序
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		//tmp記錄待插入元素，因?yàn)椴迦霐?shù)據(jù)時(shí)需要挪動(dòng)數(shù)據(jù)，會(huì)被覆蓋
		int tmp = a[end+1];
		//[0,end]有序，將tmp插入到合適位置
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

1.3 直接插入排序特點(diǎn)總結(jié)

1. 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高。
2. 時(shí)間復(fù)雜度：O(N^2)。并且是時(shí)間復(fù)雜度為 N^2的所有算法中最快的排序。
3. 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法。

二、希爾排序 ( 縮小增量排序 )

逆序有序的數(shù)組進(jìn)行插入排序時(shí)，時(shí)間復(fù)雜度為O ( n^2 )，此時(shí)效率最低。

? 順序有序的數(shù)組進(jìn)行插入排序時(shí)，時(shí)間復(fù)雜度為O ( n )，此時(shí)效率最高。

?我們發(fā)現(xiàn)，當(dāng)被排序的對(duì)象越接近有序時(shí)，插入排序的效率越高，那我們是否有辦法將數(shù)組變成接近有序后再用插入排序，此時(shí)希爾大佬就發(fā)現(xiàn)了這個(gè)排序算法，并命名為希爾排序

2.1 希爾排序原理

希爾排序法又稱縮小增量法。為了提高插入排序效率，希爾給出了這樣一個(gè)辦法：
將原有大量數(shù)據(jù)進(jìn)行分組，分割成若干個(gè)子序列，此時(shí)每個(gè)子序列待排序的個(gè)數(shù)就減少了。然后對(duì)這些子序列分別進(jìn)行插入排序（目的在于使較小的數(shù)據(jù)基本在前面，較大的數(shù)據(jù)基本在后面，而不大不小的數(shù)據(jù)則位于中間，從而達(dá)到排序基本有序的目的）。當(dāng)整個(gè)序列基本有序時(shí)，最后在全體進(jìn)行一次插入排序即可。

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

【代碼思路】：首先確定希爾排序的間距（gap），可以根據(jù)不同的方法選擇不同的間距。根據(jù)選擇的間距，將待排序的數(shù)組分割成若干個(gè)子序列，使用插入排序?qū)γ總€(gè)子序列進(jìn)行排序。逐步減小間距，重復(fù)第二步，直到間距為1。此時(shí)，整個(gè)數(shù)組被分割成了一個(gè)子序列，即原始的待排序序列。最后對(duì)原始的待排序序列進(jìn)行插入排序，最終得到有序數(shù)組。（這里博主建議gap=n(數(shù)據(jù)個(gè)數(shù)）/ 3,在不斷更新gap)

void ShellSort(int* a, int n)
{
	//1. gap>1 預(yù)排序
	//2. gap=1 插入排序

	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		//多組并排
		for (int j = 0; j < n - gap; j++)
		{
			int end = j;
			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;
		}
	}
}

2.3 希爾排序特點(diǎn)總結(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)化的效果。
3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些樹中給出的希爾排序的時(shí)間復(fù)雜度都不固定：
   《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》— 嚴(yán)蔚敏
   
   《數(shù)據(jù)結(jié)構(gòu)-用面相對(duì)象方法與C++描述》— 殷人昆
   
   因?yàn)榇颂幍膅ap是按照Knuth提出的方式取值的，而且Knuth進(jìn)行了大量的試驗(yàn)統(tǒng)計(jì)，我們暫時(shí)就按照：O(n^1.25) ~ O(1.6 * n^1.25)。

三、直接插入排序和希爾排序性能大比拼 !!!

希爾排序雖然看起來比較普通，但實(shí)際性能可以和快排以及堆排序達(dá)到一個(gè)量級(jí)?。?！

3.1 如何對(duì)比性能？準(zhǔn)備工作

要對(duì)比兩算法性能，首先創(chuàng)建一個(gè)包含大量元素的隨機(jī)數(shù)組，這個(gè)數(shù)組將用于測(cè)試兩個(gè)排序算法的效率。并且要確保測(cè)試數(shù)據(jù)集的大小足夠大，以便能夠準(zhǔn)確測(cè)量算法的效率。在分別對(duì)兩個(gè)排序算法在相同的測(cè)試數(shù)據(jù)集上進(jìn)行排序，并記錄每個(gè)算法排序所花費(fèi)的時(shí)間。最后將兩個(gè)排序算法的排序時(shí)間進(jìn)行比較即可。
?
Tips：
①：在對(duì)比兩個(gè)排序算法的效率時(shí)，需要確保使用相同的編程語(yǔ)言和相同的測(cè)試數(shù)據(jù)集。
②：：編譯器切換到Release模式。

至于原因就得提到Release的特點(diǎn)了。
Release模式可以優(yōu)化代碼的性能和執(zhí)行速度，減少調(diào)試信息的冗余，并提高程序的運(yùn)行效率。在對(duì)比兩個(gè)算法時(shí)，這些優(yōu)化和調(diào)試信息并不是必需的。

3.2 如何實(shí)現(xiàn)？

創(chuàng)建數(shù)據(jù)

首先為兩個(gè)為兩個(gè)待排序數(shù)組創(chuàng)建足夠大的存儲(chǔ)空間，然后調(diào)用rand()隨機(jī)生成數(shù)據(jù)。為保證兩待排數(shù)組中的數(shù)據(jù)一樣，將隨機(jī)生成的數(shù)據(jù)依次賦值給兩數(shù)組。

比較快慢

要比較兩則運(yùn)行時(shí)間，可以調(diào)用clock()函數(shù)，就可以輕松得到算法執(zhí)行時(shí)間了??！
?
CPlusPlus:clock()
（clock()計(jì)算的是程序運(yùn)行開始到執(zhí)行此函數(shù)的運(yùn)行時(shí)間，單位ms）

代碼、結(jié)果分析

void TestOP()
{
	srand((unsigned int)time(NULL));
	//博主受限電腦配置，數(shù)據(jù)只能建10000個(gè)。
	//各位可適當(dāng)擴(kuò)大數(shù)據(jù)，兩則差距更明顯
	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);
}

運(yùn)行結(jié)構(gòu)：

上述結(jié)果我們直觀發(fā)現(xiàn)，希爾排序性能遠(yuǎn)遠(yuǎn)大于直接插入排序。
可能有部分學(xué)者還是感受不出來，你可以將數(shù)據(jù)個(gè)數(shù)擴(kuò)大到百萬(wàn)看看就知道了。

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

到了這里，關(guān)于直接插入排序、希爾排序詳解。及性能比較的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！