Java資料結構之插入排序與希爾排序

2023-04-04 06:01:07

一、正文

1.排序的概念及其運用

1.1排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。

穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序後的序列中，r[i]仍在r[j]之前，則稱這種排序演演算法是穩定的；否則稱為不穩定的。

內部排序：資料元素全部放在記憶體中的排序。

外部排序：資料元素太多不能同時放在記憶體中，根據排序過程的要求不能在內外存之間行動資料的排序。

1.2排序運用

看過排序的基礎概念，可能有的小夥伴會問就算我學會了排序，但是在實際生活中有什麼用嗎？其實排序在生活中無處不在，比如說對一件商品不同維度的選擇，又或者是對高校的排名，其實背後都存在著排序的思想，學好排序，能夠幫助我們以另一種維度來觀察生活中的方方面面並幫助我們更好地解決生活中的問題。

1.3常見的排序演演算法

在資料結構這一塊，我們常見的排序演演算法共有四種：

①插入排序：直接插入排序、希爾排序

②選擇排序：選擇排序、堆排序

③交換排序：氣泡排序、快速排序

④歸併排序：歸併排序

2.插入排序演演算法的實現

由於篇幅的關係，本篇我們主要介紹的是插入排序中的直接插入排序和希爾排序，而直接插入排序又常常被稱為插入排序。

2.1插入排序

2.1.1基本思想

        直接插入排序是一種簡單的插入排序法

        其基本思想是把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列

        實際中我們玩撲克牌時，就用了插入排序的思想。當你摸了一張新牌，自然而然地就會與手上已有的牌堆進行一一比較，在比較之後將其放入其應該所處的位置。所以我們可能並不知道插入排序是什麼，但我們潛意識的做法恰恰就符合了插入排序。

2.1.2直接插入排序

用比較書面的語言來描述直接插入排序：當插入第i(i>=1)個元素時，前面的 array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與 array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序後移

但這麼說可能有的小夥伴會不太理解，那麼通俗地來講吧。現在在你面前有一個亂序的陣列，我們的目的是要將這個亂序的陣列調整為升序或者降序。

以升序為例叭，由於陣列是無序的，因此我們需要從陣列的第二個元素開始排序。為什麼不是第一個呢，因為只有一個數位的的時候，你無法與其餘元素比較，自然也就沒有亂序一說，因此只有一個元素的時候我們就預設它是有序的。

在理解完為什麼要從第二個元素開始排序後，現在我們就要進行元素的依次插入和排序了。先是第二個元素的插入和排序，在下圖中我們會發現第二個元素是44，44大於第一個元素3，因此不需要挪動第二個元素。緊接著就是第三個元素的插入和排序，我們發現第三個元素38小於第二個元素44，不符合我們升序的預期，因此將44挪動到38的位置，在第二、三個元素有序後，我們發現38大於3，也就是第一、二個元素也是有序的，因此就無需再挪動第一個元素的位置，這時候我們已經確認38應該所處的是陣列中第二個元素的位置，因此我們只需將38插入到第二個元素的位置即可。相信看到這裡的小夥伴對後續元素的插入與排序應該是信手拈來了，

接下來就是程式碼的書寫了。在程式碼上，我們該如何實現上述元素的插入與排序呢？我們採取了兩個主要的變數“des”和“end”，des就是我們所要插入的元素的初識下標，而end代表的是插入之前的序列的最後一個元素的下標，隨著des的比較，end要不斷向前移動，那麼什麼時候end的移動才會停止呢，也就是比較的結束，大致分為兩種情況：①des所代表的元素大於end所代表的的元素 ②end已經來到序列的第一個元素，這時候des要麼是第一個元素，或者是第二個元素。

具體圖片和程式碼如下：

//插入排序[升序]
int* InsertSort(int* arr, int n)
{
 
	//整體排序
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int des = arr[i];
		//單趟排序
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			arr[end+1] = des;
		}
	}
}

注：直接插入排序特性總結

①元素集合越接近有序，直接插入排序演演算法的時間效率越高

②時間複雜度：O(N^2)

③ 空間複雜度：O(1)，它是一種穩定的排序演演算法

④ 穩定性：穩定

2.1.3希爾排序（縮小增量排序）

希爾排序法又稱縮小增量法。

希爾排序法的基本思想是：先選定一個整數，把待排序檔案中所有記錄分成整數個組，所有距離為的記錄分在同一組內，並對每一組內的記錄進行排序。然後重複上述分組和排序的工作，當到達整數等於1時，所有記錄在統一組內排好序。

通俗來講，希爾排序就是多次的直接插入排序，不過除了最後一次直接插入排序之外的排序又和原本的直接插入排序有所不同。那麼有的小夥伴看到這裡可能就會問了為什麼要進行多次的插入排序，單次的插入排序又和正常的插入排序不同在哪裡呢？彆著急，下面我們一個個回答。

先是為什麼要多次的插入排序，看過上面對於插入排序的特性總結我們會發現，當元素的集合越接近有序，那麼對其進行插入排序的時間效率就越高。因此希爾排序除了最後一次的排序是正常的插入排序之外的多次插入排序的目的就是不斷的調整這個元素的集合，使其不斷的接近有序。

緊接著就是希爾排序除最後一次插入排序之外的插入排序與正常插入排序的差異。通過上面對插入排序的學習，我們會發現對於一個亂序的陣列的來說，一個元素若想來到正確的位置必須要與其餘元素一一比較，也就是一步步的挪動，這種挪動在陣列元素個數少的情況下尚可，但當這個陣列的元素個數很多的時候，以升序來說，想象這個陣列內最大的元素位於陣列的第一個位置，那麼是不是就要將這個元素與陣列內其餘元素一一比較以後，才能來到陣列的最後一個位置，但當我們加大比較的步伐，也就是增大相比較的兩個元素之間的距離，那麼這個元素是不是就可以更快的來到它應該所處的位置。放置於飛行棋的情境之下，插入排序每次都擲出1，而雜湊排序除了最後一次的插入排序擲出的點數是1，其餘的插入排序所擲出的點數是都是大於1的，所以可想而知，雜湊排序能夠更快的到達排序的終點。

為了方便小夥伴們的理解，這部分程式碼共分為兩部分：①固定步伐的直接插入排序②雜湊排序。

先是固定步伐的直接插入排序，先讓我們通過圖片來直觀的看到陣列陣列內的元素通過這種操作後的變化。

//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
	int gap = 3;
	int end;
	//有兩種寫法，看你要控制end，還是des
	/*for (int i=0; i < n-gap; i++)
	{
		int end = i;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}*/
 
	for (int i = gap; i < n ; i++)
	{
		int end = i-gap;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}
}

接著就是希爾排序

上述的程式碼是gap=3的情況下的直接插入排序，那麼對於希爾排序而言，我們該對gap該如何選擇呢？對於不同gap值的插入排序來說，我們會發現：gap越大，元素跳得越快，陣列越不接近有序；而gap越小，元素跳的越慢，陣列越接近有序。由於陣列的大小不定，因此希爾排序也沒有一個合適gap值適用於所有陣列，顯然，這個gap值一定是動態變化的。

對於gap的動態變化，常見的有兩種：

①令gap等於陣列的元素個數，每次插入排序後令gap除等2

②另一種則是令gap等於陣列的元素個數，不過每次插入排序後令gap除以3再加1

無論哪種處理都能使gap動態變化並最後等於1，對陣列進行一次插入排序，達到最後想要的效果。

程式碼如下：

//希爾排序
void ShellSortPlus(int* arr, int n)
{
	int gap=n;
	int end;
	while (gap > 1)
	{
	gap = gap / 2;
		
		for (int i=0; i < n - gap;i++)//有兩種寫法，看你要控制end，還是des
		{
			int end = i;
			int des = arr[end + gap];
			while (end >= 0)
			{
				if (des >= arr[end])
					break;
				if (des < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				arr[end + gap] = des;
			}
		}
 
	}
}

二、測試程式碼

為了方便小夥伴們測試排序後的效果，為大家提供了測試的程式碼幷包含排序的具體程式碼和包含的標頭檔案。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
//插入排序[升序]
int* InsertSort(int* arr, int n)
{
 
	//整體排序
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int des = arr[i];
		//單趟排序
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			arr[end+1] = des;
		}
	}
}
 
//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
	int gap = 3;
	int end;
	//有兩種寫法，看你要控制end，還是des
	/*for (int i=0; i < n-gap; i++)
	{
		int end = i;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}*/
 
	for (int i = gap; i < n ; i++)
	{
		int end = i-gap;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}
}
 
 
//希爾排序
void ShellSortPlus(int* arr, int n)
{
	int gap=n;
	int end;
	while (gap > 1)
	{
	gap = gap / 2;
		
		for (int i=0; i < n - gap;i++)//有兩種寫法，看你要控制end，還是des
		{
			int end = i;
			int des = arr[end + gap];
			while (end >= 0)
			{
				if (des >= arr[end])
					break;
				if (des < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				arr[end + gap] = des;
			}
		}
 
	}
}
 
//列印排序好的陣列
void PrintSort(int*arr,int n)
{
	for(int i=0;i<n;i++)
	{
		printf("%d ", arr[i]);
	}
	printf("n");
}
 
//測試插入排序
void Text1()
{
	int arr[10] = { 25,14,8,7,18,24,16,57,98,105 };
	InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintSort(arr, sizeof(arr) / sizeof(arr[0]));
}
 
//測試固定步伐的插入排序
void Text2()
{
	int arr[10] = { 9,1,2,5,7,4,8,6,3,5};
	ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintSort(arr, sizeof(arr) / sizeof(arr[0]));
}
 
//測試希爾排序
void Text3()
{
	int arr[10] = { 9,1,2,5,7,4,8,6,3,5 };
	ShellSortPlus(arr, sizeof(arr) / sizeof(arr[0]));
	PrintSort(arr, sizeof(arr) / sizeof(arr[0]));
}
 
int main()
{
	//Text1();
	Text2();
	//Text3();
 
	return 0;
}