一、正文

1.排序的概念及其運用

1.1排序的概念

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

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

內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。

外部排序：數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。

1.2排序運用

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

1.3常見的排序算法

在數(shù)據(jù)結構這一塊，我們常見的排序算法共有四種：

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

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

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

④歸并排序：歸并排序

2.插入排序算法的實現(xiàn)

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

2.1插入排序

2.1.1基本思想

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

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

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

 2.1.2直接插入排序

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

        但這么說可能有的小伙伴會不太理解，那么通俗地來講吧。現(xiàn)在在你面前有一個亂序的數(shù)組，我們的目的是要將這個亂序的數(shù)組調(diào)整為升序或者降序。

        以升序為例叭，由于數(shù)組是無序的，因此我們需要從數(shù)組的第二個元素開始排序。為什么不是第一個呢，因為只有一個數(shù)字的的時候，你無法與其余元素比較，自然也就沒有亂序一說，因此只有一個元素的時候我們就默認它是有序的。

        在理解完為什么要從第二個元素開始排序后，現(xiàn)在我們就要進行元素的依次插入和排序了。先是第二個元素的插入和排序，在下圖中我們會發(fā)現(xiàn)第二個元素是44，44大于第一個元素3，因此不需要挪動第二個元素。緊接著就是第三個元素的插入和排序，我們發(fā)現(xiàn)第三個元素38小于第二個元素44，不符合我們升序的預期，因此將44挪動到38的位置，在第二、三個元素有序后，我們發(fā)現(xiàn)38大于3，也就是第一、二個元素也是有序的，因此就無需再挪動第一個元素的位置，這時候我們已經(jīng)確認38應該所處的是數(shù)組中第二個元素的位置，因此我們只需將38插入到第二個元素的位置即可。相信看到這里的小伙伴對后續(xù)元素的插入與排序應該是信手拈來了，

        接下來就是代碼的書寫了。在代碼上，我們該如何實現(xiàn)上述元素的插入與排序呢？我們采取了兩個主要的變量“des”和“end”，des就是我們所要插入的元素的初識下標，而end代表的是插入之前的序列的最后一個元素的下標，隨著des的比較，end要不斷向前移動，那么什么時候end的移動才會停止呢，也就是比較的結束，大致分為兩種情況：①des所代表的元素大于end所代表的的元素 ②end已經(jīng)來到序列的第一個元素，這時候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)，它是一種穩(wěn)定的排序算法

④ 穩(wěn)定性：穩(wěn)定

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

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

        希爾排序法的基本思想是：先選定一個整數(shù)，把待排序文件中所有記錄分成整數(shù)個組，所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進行排序。然后重復上述分組和排序的工作，當?shù)竭_整數(shù)等于1時，所有記錄在統(tǒng)一組內(nèi)排好序。

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

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

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

        為了方便小伙伴們的理解，這部分代碼共分為兩部分：①固定步伐的直接插入排序②哈希排序。

        先是固定步伐的直接插入排序，先讓我們通過圖片來直觀的看到數(shù)組數(shù)組內(nèi)的元素通過這種操作后的變化。 

//固定步伐的直接插入排序[升序]
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值的插入排序來說，我們會發(fā)現(xiàn)：gap越大，元素跳得越快，數(shù)組越不接近有序；而gap越小，元素跳的越慢，數(shù)組越接近有序。由于數(shù)組的大小不定，因此希爾排序也沒有一個合適gap值適用于所有數(shù)組，顯然，這個gap值一定是動態(tài)變化的。

        對于gap的動態(tài)變化，常見的有兩種：

①令gap等于數(shù)組的元素個數(shù)，每次插入排序后令gap除等2

②另一種則是令gap等于數(shù)組的元素個數(shù)，不過每次插入排序后令gap除以3再加1

        無論哪種處理都能使gap動態(tài)變化并最后等于1，對數(shù)組進行一次插入排序，達到最后想要的效果。

        代碼如下：

//希爾排序
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;
			}
		}
 
	}
}
 
//打印排序好的數(shù)組
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;
}

三、結語

      到此為止，本期關于插入排序和希爾排序的講解就告一段落了，在后續(xù)的文章里還有繼續(xù)介紹其他的排序及其實現(xiàn)

 以上就是Java數(shù)據(jù)結構之插入排序與希爾排序的詳細內(nèi)容，更多關于Java 插入與希爾排序的資料請關注腳本之家其它相關文章！

最新評論