八大排序算法之插入排序+希爾排序

這篇具有很好參考價值的文章主要介紹了八大排序算法之插入排序+希爾排序。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

一.前言(總體簡介)

關(guān)于插入排序

?關(guān)于希爾排序:

二.插入排序

函數(shù)首部:

算法思路:

算法分析

插入排序代碼實現(xiàn):

插入排序算法的優(yōu)化前奏:?

三.希爾排序(縮小增量排序)

1.算法思想:?

2.算法拆分解析?

序列分組

分組預(yù)排序:

分組預(yù)排序的另一種實現(xiàn)方式:

希爾排序的實現(xiàn)思路(這里采用Knuth實現(xiàn)法)

關(guān)于gap指數(shù)式遞減的分析:

四.希爾排序的時間復(fù)雜度分析

分組預(yù)排序的時間復(fù)雜度

gap指數(shù)式遞減過程中,多次分組預(yù)排序的總復(fù)雜度分析:

經(jīng)典數(shù)據(jù)結(jié)構(gòu)書目中對希爾排序復(fù)雜度的說明:?

五.實測對比希爾排序與普通插入排序的時間效率

一.前言(總體簡介)

關(guān)于插入排序

插入排序的思想:將各元素逐個插入到已經(jīng)有序的序列中的指定位置

插入排序的思想很類似于我們玩撲克牌時逐張摸牌并整理牌序的方式:

還有一個更貼近算法實現(xiàn)的gif:

將上面的方條看成數(shù)組中的元素

橙色的方條代表已經(jīng)排好序的元素序列,藍(lán)色的方條代表待插入的各元素

在算法實現(xiàn)中,橙色的方條構(gòu)成的序列用一個下標(biāo)變量來維護(hù)(每次循壞該下標(biāo)變量加1)?

?關(guān)于希爾排序:

希爾排序是插入排序的優(yōu)化版本,優(yōu)化算法由希爾本人給出

基本思想是先對數(shù)組的子數(shù)組(按照一定規(guī)則劃分而成)進(jìn)行預(yù)排序,使待排序數(shù)組變得相對有序,最后再對整個數(shù)組進(jìn)行一次插入排序完成整體的排序

二.插入排序

函數(shù)首部:
void InsertSort(DataType* arr, int size);
arr是待排序數(shù)組首地址指針;

size是待排序的元素個數(shù);

算法思路:

用一個數(shù)組下標(biāo)變量end來維護(hù)前end個有序元素(end初始化為0)

每個循環(huán)過程中,將end下標(biāo)變量指向的元素插入到前end個元素中的某個指定位置上構(gòu)成一個end+1個元素的有序序列,然后end加一,接著執(zhí)行下一次循環(huán)直到end遍歷完整個數(shù)組后循環(huán)結(jié)束;

每次循環(huán)過程中,x元素插入的位置是通過元素比較來確定的:

end為0時,有序序列元素個數(shù)為0;end為1時,有序序列的元素個數(shù)為1........;當(dāng)end為size時,有序序列的元素個數(shù)便為size(即數(shù)組中size個元素按序排列)此時排序完成

插入排序便是以這種遞推的方式將數(shù)組arr調(diào)整成有序序列的?

算法分析

從算法思路中可以看到,完成一個元素x插入到前end個元素構(gòu)成的有序序列的過程中,會發(fā)生數(shù)據(jù)的比較和挪動

在最壞的情況下,每完成一個元素x插入到前end個元素的構(gòu)成的有序序列的過程中,有序序列的每個元素都要被往后挪動一個位置(即元素比較和挪動的次數(shù)為end次)

因此整個排序的過程中發(fā)生元素的比較和挪動的總次數(shù)為:

所以插入排序的時間復(fù)雜度為:O(N^2)? (N為待排序的元素個數(shù));

插入排序代碼實現(xiàn):

兩層循環(huán)實現(xiàn):
外層循環(huán)用end控制(有size個元素要插入,循環(huán)size次)(每次要插入前綴序列的元素x=arr[end])(end下標(biāo)遍歷了整個數(shù)組)
for(int end =0;end<size;++end)
內(nèi)層循環(huán)用insert控制,用于比較和挪動數(shù)據(jù),確定x要插入的位置并完成插入(insert每次從end開始遞減直到等于0或者剛好找到x要插入的位置)

以排升序為例:
//以排升序為例
void InsertSort(DataType* arr, int size)
{
	assert(arr);
	for (int end = 0; end < size; end++)    //用end來維護(hù)數(shù)組前end個元素構(gòu)成的有序序列
	{
		int x = arr[end];					//x為待插入有序序列的數(shù)據(jù)
		int insert = end;					//用變量insert來確定x要插入的位置
		while (insert>0)					//通過元素比較確定x要插入的位置
		{
			if (x < arr[insert-1])			   //說明insert不是x要插入的位置
			{
				arr[insert] = arr[insert-1];   //往后挪動數(shù)據(jù)為x留出空位
				insert--;                      //令insert指向序列前一個元素
			}
			else
			{
				break;	    //有序序列中x>=arr[insert-1]說明insert是x要插入的位置
			}
		}					//最壞的情況下x會被插入到數(shù)組的首地址處(此時數(shù)據(jù)比較和挪動了end次)
		arr[insert] = x;    //完成元素x的插入(繼續(xù)插入下一個元素)
	}
}
注意算法的邊界條件:

外層循環(huán)end增加到size時結(jié)束循環(huán)(數(shù)組各元素下標(biāo)為0到size-1)

內(nèi)層循環(huán)insert等于0時說明x比前end個元素的有序序列中的所有元素都小,x將被插入到數(shù)組下標(biāo)為insert=0的位置

插入排序算法的優(yōu)化前奏:?

插入排序算法利用了逐個元素遞推插入前綴有序數(shù)列的方法完成整個待排序序列的調(diào)整(元素插入的過程中,前綴序列有序的性質(zhì)有時可以大大減少元素的比較和挪動次數(shù)).

因此插入排序算法有一個特點:當(dāng)待排序數(shù)組arr整體相對有序時,排序過程的時間復(fù)雜度接近O(N),舉個例子:

插入排序在處理上圖的序列過程中元素總的比較次數(shù)為size+2次,元素總的挪動次數(shù)為3次(總體上可以認(rèn)為:在處理整體上大致有序的序列時,插入排序的時間復(fù)雜度與size是線性相關(guān)的);

插入排序的上述特點為算法的優(yōu)化提供了可能,如果我們能夠在對序列正式進(jìn)行插入排序之前,讓序列整體上變得相對有序,那么就可以降低排序時間復(fù)雜度的數(shù)量級,這就是希爾排序誕生的思想起點

三.希爾排序(縮小增量排序)

希爾排序算法由大神D.L.Shell于1959年提出而得名,其本質(zhì)上是在插入排序的基礎(chǔ)上進(jìn)行優(yōu)化而產(chǎn)生的

先給出排序接口的首部:
void ShellSort(DataType* arr, int size);
DataType為typedef定義的元素類型

size是待排序數(shù)組arr中的元素個數(shù)

1.算法思想:?

經(jīng)過對插入排序的分析我們已經(jīng)知道:在處理整體上大致有序的序列時,插入排序的時間復(fù)雜度與待排序元素個數(shù)是線性相關(guān)的

因此在正式進(jìn)行插入排序之前,我們考慮先將序列進(jìn)行多次分組預(yù)排序

多次分組預(yù)排序完成后,整體序列將變得相對有序,最后再進(jìn)行一次插入排序完成整體序列的排序

2.算法拆分解析?

序列分組

序列分組方式圖文解析:先確定一個gap值(gap<=size)(將序列劃分為gap組),從數(shù)組第一個元素開始以gap為間隔構(gòu)成子序列,如圖所示:

根據(jù)上述分組方式,我們簡單地進(jìn)行數(shù)學(xué)上的分析:由于gap<=size,因此我們一定可以將數(shù)組arr分為gap個子序列(每個子序列的元素個數(shù)至少為(size/gap)個;當(dāng)size為gap整數(shù)倍時,每個子序列的元素個數(shù)為(size/gap)個,當(dāng)size不為gap整數(shù)倍時,每個子序列元素個數(shù)最大為(size/gap)+1個);(以上數(shù)學(xué)表達(dá)式中的除法皆為向下取整除法)

我給這種序列分組模式取個名字:序列固定間隔分組法

序列固定間隔分組法的另外一種圖示形式:

可見每個子序列的首元素分別為下標(biāo)為0到gap-1的元素

完成了序列的固定間隔分組后,接下來就要對這些子序列分別進(jìn)行插入排序,即分組預(yù)排序

分組預(yù)排序:

確定了gap值后,對各個子序列分別進(jìn)行插入排序:(圖示中以gap=3為例子)

分組預(yù)排序的代碼實現(xiàn)思路:(最基礎(chǔ)的思路是三層循環(huán)實現(xiàn))

數(shù)組arr被分為gap組, 所以要對gap個子序列進(jìn)行插入排序即最外層循環(huán)gap次,最外層循環(huán)用start變量來控制(初始化為0),邊界條件為start<gap;

內(nèi)兩層循環(huán)的代碼架構(gòu)與插入排序完全一致
分組預(yù)排序的代碼實現(xiàn)(建立在插入排序代碼的框架上):
void ShellSort(DataType* arr, int size)
{
	assert(arr);

	int gap;									//將數(shù)組劃分為gap組(gap待定)
	for (int start = 0; start < gap; ++start)   //start為每個子序列的首元素下標(biāo)(gap個子序列循環(huán)gap次)
	{
		for (int end = start; end < size; end += gap)	//用end來維護(hù)子序列中的前綴有序序列(end不能大于或等于size)(end下標(biāo)遍歷了子序列)
		{
			int x = arr[end];							//x為待插入前綴有序序列的元素
			int insert = end;							//用insert確定x要插入的位置
			while (insert>start)						//insert=start時說明x要插入到子序列首元素的位置
			{
				if (x < arr[insert - gap])				//說明insert不是x要插入的位置
				{
					arr[insert] = arr[insert - gap];    //挪動數(shù)據(jù),為x空出位置
					insert -= gap;						//指向子序列的前一個元素
				}
				else                                    //x >= arr[insert - gap]說明insert就是x要插入的位置
				{ 
					break;
				}
			}
			arr[insert] = x;							//完成x元素的插入
		}	
	}
}
代碼段完成了一次分組預(yù)排序(分組間隔為gap)

代碼段中如果gap等于1,分組預(yù)排序則變?yōu)槠胀ǖ牟迦肱判?

分組預(yù)排序的另一種實現(xiàn)方式:
分組預(yù)排序可以用兩層循壞來實現(xiàn):

注:兩層循環(huán)的分組預(yù)排序和三層循環(huán)的分組預(yù)排序其實本質(zhì)上沒有區(qū)別,只是元素調(diào)整順序不一樣(三層循環(huán)是一組接一組子序列完成插入排序,兩層循環(huán)是逐個元素完成調(diào)整)
void ShellSort(DataType* arr, int size)
{
	assert(arr);
	int gap;										//gap值待定		
	for (int end = 0; end < size; ++end)		    //用end來遍歷數(shù)組每一個元素
	{
		int x = arr[end];							//x為待插入子序列前綴的元素
		int insert = end;							//用insert確定x要插入的位置
		while (insert >= gap)						//insert<gap的時,insert為下標(biāo)的元素不需要調(diào)整
		{
			if (x < arr[insert - gap])				//說明insert不是x要插入的位置
			{
				arr[insert] = arr[insert - gap];    //挪動數(shù)據(jù),為x空出位置
				insert -= gap;						//指向子序列的前一個元素
			}
			else                                    //x >= arr[insert - gap]說明insert就是x要插入的位置
			{
				break;
			}
		}
		arr[insert] = x;							//完成x元素的插入
	}
}
三層循環(huán)改為兩層循環(huán),其具體代碼思路圖解如下:
三層循環(huán)的寫法和兩層循環(huán)的寫法本質(zhì)都是完成了gap為某確定值時的一次分組預(yù)排序

同樣地,代碼段中如果gap等于1,分組預(yù)排序則變?yōu)槠胀ǖ牟迦肱判?

后續(xù)為了簡潔起見,我們采用兩層循環(huán)的分組預(yù)排序?qū)崿F(xiàn)法來完成希爾排序

希爾排序的實現(xiàn)思路(這里采用Knuth實現(xiàn)法)
由之前的分析我們可以知道:gap的值確定了序列的一個劃分(序列被劃分為gap個子序列),對這些子序列分別進(jìn)行插入排序便完成了一次序列的分組預(yù)排序

我們置gap的初始值為size,gap每次循環(huán)按照gap = (gap/3)+1的方式遞減(由簡單的數(shù)學(xué)分析可知gap一定會減小到1)(加1就是為了保證gap最終一定會減小到1)

對于每一個gap值我們都對待排序數(shù)組進(jìn)行一次分組預(yù)排序

當(dāng)gap減小到1時,數(shù)組已經(jīng)經(jīng)過了一次或多次分組預(yù)排序,最后再完成一次gap為1的分組預(yù)排序(gap為1時的分組預(yù)排序等價于普通的插入排序)從而完成數(shù)組整體的排序(gap為1的排序必須進(jìn)行,否則不能保證整體序列一定有序)
我們只需在分組預(yù)排序的實現(xiàn)代碼外層再套一層由gap控制的循環(huán)即可實現(xiàn)上述過程:
void ShellSort(DataType* arr, int size)
{
	assert(arr);
	int gap = size;										
	while (gap>1)                  //gap為1時序列已經(jīng)完成了普通插入排序,排序完成
	{
        gap = gap/3 + 1;           //縮小gap的值
		for (int end = 0; end < size; ++end)		    //用end來遍歷數(shù)組每一個元素
		{
			int x = arr[end];							//x為待插入子序列前綴的元素
			int insert = end;							//用insert確定x要插入的位置
			while (insert >= gap)						//insert<gap的時,insert為下標(biāo)的元素不需要調(diào)整
			{
				if (x < arr[insert - gap])				//說明insert不是x要插入的位置
				{
					arr[insert] = arr[insert - gap];    //挪動數(shù)據(jù),為x空出位置
					insert -= gap;						//指向子序列的前一個元素
				}
				else                                    //x >= arr[insert - gap]說明insert就是x要插入的位置
				{
					break;
				}
			}
			arr[insert] = x;							//完成x元素的插入
		}
	}												
}

關(guān)于gap指數(shù)式遞減的分析:

希爾排序算法中,gap從size開始呈指數(shù)式遞減. (這也是縮小增量排序這個名字的來源)

因此,算法中分組預(yù)排序的執(zhí)行次數(shù)的數(shù)量級為(logN) (N=size)

gap設(shè)計成指數(shù)式遞減這一思想非常重要,這樣既保證了在進(jìn)行gap=1的插入排序之前,完成了一定次數(shù)的分組預(yù)排序,又保證了分組預(yù)排序的次數(shù)不會太多(分組預(yù)排序的次數(shù)如果太多反倒會降低算法整體的效率)

四.希爾排序的時間復(fù)雜度分析

希爾排序接口首部:
void ShellSort(DataType* arr, int size)

分組預(yù)排序的時間復(fù)雜度

序列分組圖示:

為了方便分析,我們假設(shè)每次分組預(yù)排序,size都為gap的整數(shù)倍:根據(jù)序列固定間隔分組法,待排序數(shù)組被劃分為gap個子序列,每個子序列元素個數(shù)為(size/gap)個

根據(jù)插入排序的時間復(fù)雜度計算公式:完成每組子序列的插入排序算法循環(huán)中元素比較和挪動的總次數(shù)的數(shù)量級為:

即完成一次分組預(yù)排序的時間復(fù)雜度計算表達(dá)式為:

gap指數(shù)式遞減過程中,多次分組預(yù)排序的總復(fù)雜度分析:

可以發(fā)現(xiàn)一個規(guī)律:gap值越大(gap<=size)的分組預(yù)排序元素比較和挪動次數(shù)的上限就越低(復(fù)雜度越接近線性),因此利用較大的gap值進(jìn)行分組預(yù)排序將總體序列調(diào)整為相對有序序列的設(shè)計非常巧妙！??！

將size寫成N,則希爾排序的時間復(fù)雜度總體的數(shù)量級大致為NlogN

該證明并不嚴(yán)格,但是總體上反映出了希爾排序通過多次分組預(yù)排序的方法嘗試降低整體排序的時間復(fù)雜度數(shù)量級的思想。

希爾大神設(shè)計該算法時,gap的遞減方式是:gap=gap/2；

gap = (gap/3)+1這種縮小增量的公式是由kunth大神給出的,希爾排序的最優(yōu)gap遞減公式目前尚未求得(這牽涉到一些尚未得到完全解決的數(shù)學(xué)難題)

經(jīng)典數(shù)據(jù)結(jié)構(gòu)書目中對希爾排序復(fù)雜度的說明:?

以下文段摘自《數(shù)據(jù)結(jié)構(gòu)-用面相對象方法與C++描述》--- 殷人昆

gap的取法有多種.最初Shell提出取gap=gap/2,直到gap=1,后來Kunth提出取gap=(gap/3) +1.還有人提出都取奇數(shù)為好,也有人提出各gap互質(zhì)為好.無論哪一種主張都沒有得到證明。

對希爾排序的時間復(fù)雜度的分析很困難,在特定情況下可以準(zhǔn)確地估算關(guān)鍵碼的比較次數(shù)和對象移動次數(shù),但想要弄清關(guān)鍵碼比較次數(shù)和對象移動次數(shù)與增量選擇之間的依賴關(guān)系,并給出完全的數(shù)學(xué)分析,還沒有人能夠做到。在Kunth所著的《計算機(jī)程序設(shè)計技巧》第三卷中,利用大量的實驗數(shù)據(jù)統(tǒng)計資料得出,當(dāng)n很大時,關(guān)鍵碼平均比較次數(shù)和對象平均移動次數(shù)大約在n^1.25 到1.6n^1.25范圍內(nèi),這是在利用直接插入排序作為子序列排序方法的情況下得到的

從上述文段中我們可以得知,受當(dāng)前數(shù)學(xué)分析的限制,我們可以暫且根據(jù)Kunth大神的實驗結(jié)果,將希爾排序的時間復(fù)雜度看成是: O(N^1.25)

五.實測對比希爾排序與普通插入排序的時間效率

利用隨機(jī)數(shù)生成器創(chuàng)建兩個十萬個元素的相同整形數(shù)組,一個用直接插入排序進(jìn)行排序,另外一個用希爾排序進(jìn)行排序,打印出兩者所消耗的時間(單位為毫秒)
int main()
{
	srand(time(0));
	const int N = 100000;
	int* arr1 = (int*)malloc(sizeof(int) * N);
	int* arr2 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		arr1[i] = rand();
		arr2[i] = arr1[i];
	}
	int begin1 = clock();
	InsertSort(arr1, N);
	int end1 = clock();
	printf("IsertSort:%d\n", end1-begin1);


	int begin2 = clock();
	ShellSort(arr2, N);
	int end2 = clock();
	printf("ShellSort:%d\n", end2-begin2);
	return 0;
}
可見希爾排序的算法優(yōu)化思路雖然新奇復(fù)雜,但毫無疑問的是,希爾大神對插入排序所進(jìn)行的優(yōu)化是非常成功的！?。?！(而且數(shù)據(jù)量越大希爾排序的優(yōu)化效果就越明顯)