Java資料結構之插入排序與希爾排序怎麼實現

 一、文字

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]插入，原來位置上的元素順序後移        但這麼說可能有的小伙伴會不太理解，那麼通俗地來講吧。現在

在你面前有一個亂序的數組，我們的目的是要將這個亂序的數組調整為升序或是降序

。         以升序為例meth，由於陣列是無序的，因此我們需要

從陣列的第二個元素開始排序###。為什麼不是第一個呢，因為只有一個數字的時候，你無法與其餘元素比較，自然也就沒有亂序一說，因此只有一個元素的時候我們就默認它是有序的。 ###

        在理解為什麼要從第二個元素開始排序後，現在我們就要進行元素的依序插入和排序了。先是第二個元素的插入和排序，在下圖中我們會發現第二個元素是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 
#include 
#include 
 
//插入排序[升序]
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
以上是Java資料結構之插入排序與希爾排序怎麼實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！