一、正文

1.排序的概念及其運(yùn)用

1.1排序的概念

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

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

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

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

1.2排序運(yùn)用

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

1.3常見的排序算法

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

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

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

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

④歸并排序：歸并排序

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

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

2.1插入排序

2.1.1基本思想

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

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

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

 2.1.2直接插入排序

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

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

        以升序?yàn)槔?，由于?shù)組是無序的，因此我們需要從數(shù)組的第二個(gè)元素開始排序。為什么不是第一個(gè)呢，因?yàn)橹挥幸粋€(gè)數(shù)字的的時(shí)候，你無法與其余元素比較，自然也就沒有亂序一說，因此只有一個(gè)元素的時(shí)候我們就默認(rèn)它是有序的。

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

        接下來就是代碼的書寫了。在代碼上，我們?cè)撊绾螌?shí)現(xiàn)上述元素的插入與排序呢？我們采取了兩個(gè)主要的變量“des”和“end”，des就是我們所要插入的元素的初識(shí)下標(biāo)，而end代表的是插入之前的序列的最后一個(gè)元素的下標(biāo)，隨著des的比較，end要不斷向前移動(dòng)，那么什么時(shí)候end的移動(dòng)才會(huì)停止呢，也就是比較的結(jié)束，大致分為兩種情況：①des所代表的元素大于end所代表的的元素 ②end已經(jīng)來到序列的第一個(gè)元素，這時(shí)候des要么是第一個(gè)元素，或者是第二個(gè)元素。

        具體圖片和代碼如下：

//插入排序[升序]
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;
		}
	}
}

 注：直接插入排序特性總結(jié)

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

②時(shí)間復(fù)雜度：O(N^2)

③ 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法

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

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

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

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

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

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

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

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

        先是固定步伐的直接插入排序，先讓我們通過圖片來直觀的看到數(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的情況下的直接插入排序，那么對(duì)于希爾排序而言，我們?cè)搶?duì)gap該如何選擇呢？對(duì)于不同gap值的插入排序來說，我們會(huì)發(fā)現(xiàn)：gap越大，元素跳得越快，數(shù)組越不接近有序；而gap越小，元素跳的越慢，數(shù)組越接近有序。由于數(shù)組的大小不定，因此希爾排序也沒有一個(gè)合適gap值適用于所有數(shù)組，顯然，這個(gè)gap值一定是動(dòng)態(tài)變化的。

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

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

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

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

        代碼如下：

//希爾排序
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;
}

三、結(jié)語

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

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

最新評(píng)論