???內(nèi)容專欄：《數(shù)據(jù)結(jié)構(gòu)與算法篇》
??本文概括： 講述排序的概念、直接插入排序、希爾排序、插入排序和希爾排序的區(qū)別。
??本文作者：花 碟
??發(fā)布時間：2023.6.13

一、排序的概念及其運用

1.1 排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。
穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關(guā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 排序的運用

生活中的運用排序有很多例子，比如在我們拿起手機打開美團app點外賣時，手機頂欄有綜合排序/配送費/好評率等選項，用戶點擊之后，系統(tǒng)就會進行從高到低，或者從低到高進行排序；在全國上千所高校中，在百度中進行搜索排名，系統(tǒng)會按綜合排序?qū)Ω咝＿M行排序……

二、直接插入排序

2.1 基本思想

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

??實際中我們玩撲克牌時，就用到了插入排序的思想：

2.2 直接插入排序

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

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

1. 元素集合越接近有序，直接插入排序算法的時間效率越高
2. 時間復雜度：O(N^2)
3. 空間復雜度：O(1)，它是一種穩(wěn)定的排序算法
4. 穩(wěn)定性：穩(wěn)定

2.3 代碼實現(xiàn)

插入一個數(shù)的前提必須是保證前面區(qū)間的數(shù)據(jù)是有序的(注意當只有一個數(shù)時，本來就可以看作是有序的)，插入完之后，使新序列仍然有序。假設(shè)把下面圖中亂序的數(shù)組排成升序來說，[0，end]的區(qū)間數(shù)據(jù)是有序的 ，end默認為下標0開始，end + 1為下標的元素即為即將被插入的數(shù)據(jù)，為了避免后面被覆蓋，我們需要提前保存到tmp變量當中。如果a[end]大于tmp，就將a[end] 放入到tmp的位置，然后end–，去找前一個有序中的元素，如果前一個元素不存在，也就是end走到了-1，此時tmp就直接插入到下標為0的位置，這是第一種插入的情況（end在有序序列中已經(jīng)走完了，tmp插入序列中第一個位置）。第二種插入的情況是（tmp在序列中找到了合適的位置插入），即a[end] 小于tmp，tmp插入到a[end + 1]的位置。

而這兩種情況可以進行合并，因為都是將tmp放入到end后面的位置，具體請看以下代碼??

//直接插入排序
void InsertSort(int* a, int n)
{
	//確定區(qū)間 一共需要排的數(shù)據(jù),注意：end要小于等于n - 2,否則tmp會出現(xiàn)越界訪問
	for (int i = 0; i < n - 1;i++)
	{
		int end = i;
		//[0, end] 有序，插入一個tmp 使[0,end + 1]的數(shù)據(jù)仍然有序
		int tmp = a[end + 1];//要插入的數(shù)據(jù)需要提前存儲，否則會被覆蓋
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				//當a[end] < tmp 跳出循環(huán)
				break;
			}
		}
		//1.end走到了-1
		//2.a[end] < tmp
		a[end + 1] = tmp;
	}
}

2.4 插入排序時間復雜度

??時間復雜度：序列想要排列成升序，如果原序列是逆序，時間復雜度最壞，時間復雜度為O(N2)
如果原序列是升序，那么此時時間復雜度情況是最好的，時間復雜度為O(N)

三、希爾排序

插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位。
??插入排序是一種簡單實用的排序算法，適用于小規(guī)模數(shù)據(jù)或基本有序的數(shù)據(jù)集。但對于大規(guī)模亂序的數(shù)據(jù)集，性能較差，其時間復雜度為O(N2)，為了彌補插入排序的效率缺陷，下面讓我們就來學習希爾排序的具體實現(xiàn)過程吧??

3.1 希爾排序(縮小增量排序)

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠?。r，再對全體元素進行一次直接插入排序。

3.2 基本思想

????簡單來說，其核心思想分為兩步：??

1. 分割為若干組，進行多組預排序
2. 最后進行一次插入排序

假設(shè)我們把原始序列分為gap組，（gap與數(shù)組的大小有關(guān)，并沒有一個合適的值，后面會具體談?wù)揼ap如何給值）。這里拿圖中的原始序列來看，為了是方便大家更容易理解，把gap暫定為3.
間隔為gap，也就是3的為同一組，分別由紅色線、藍色線、綠色線三部分組成，對這三個組進行預排序，此時需要注意的是被插入的數(shù)據(jù)不是end后面緊跟的數(shù)據(jù)，而是 end + gap 為下標的數(shù)據(jù)，每一組都是如此，那么控制end的結(jié)束條件是什么呢？答案是一定要小于 n - gap ，如果一旦等于 n - gap ，插入的數(shù)據(jù)就會訪問到下標為n的位置，此時就出現(xiàn)越界訪問了！

????下面我們就根據(jù)這個思路，把預排序的代碼給寫下來??：

//gap組數(shù)據(jù)排序
// j == 0 排紅色組
// j == 1 排藍色組
// j == 2 排綠色組
for (int j = 0; j < gap; j++)
{
	//預排序 注意條件，end的區(qū)間范圍一定小于n - gap
	for (int i = 0; i < n - gap; i += gap)
	{
		int end = i;
		int tmp = a[end + gap];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		a[end + gap] = tmp;
	}
}

????我們可以換一種方式寫，這種代碼是將gap組數(shù)據(jù)并排??：

注??：1.這種方式與上一種方式效率是一樣的，并不存在循環(huán)少一個效率就更高效了。
2.上一種是排完一組接著排下一組，以下這種是gap組進行合并一起排序。

//gap組并排
	for (int i = 0; i < n - gap; i++)
	{
		int end = i;
		int tmp = a[end + gap];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		a[end + gap] = tmp;
	}

觀察以下圖中，gap的變化：

??我們發(fā)現(xiàn)：

1. gap越大，越大的數(shù)能夠較快的挪動到最后面的位置，越小的數(shù)能夠較快的挪動到最前面的位置。由于較大的間隔可以跳躍式地比較和交換元素，可以在較少的比較和交換操作下完成一輪排序，從而提高排序速度。
2. gap越小，較小的間隔能夠處理部分有序的數(shù)據(jù)集和改善最后一輪排序，但總體比較和交換的次數(shù)會越多。

這里大家是不是更容易理解了很多。

現(xiàn)在，我們回到剛開始的問題，gap(間隔)該如何確定呢？

• 最早提出的希爾排序使用的是希爾原始增量序列，即使用 N/2 作為初始間隔，然后每次將間隔折半，直到間隔為1。例如，對于一個長度為10的序列，初始間隔為5，然后依次為5/2=2、2/2=1。除了gap / 2 ，Knuth增量序列提出的gap = gap / 3 + 1 也是挺厲害的。還有更多的增量序列，像Hibbard增量序列、Sedgewick增量序列等都是根據(jù)經(jīng)驗和實驗得出的，目的是讓希爾排序在不同情況下都能夠有較好的性能表現(xiàn)。具體選擇哪種間隔序列取決于具體的應(yīng)用場景和數(shù)據(jù)特點。
  一般來說，較大的間隔能夠快速減小序列的規(guī)模，而較小的間隔能夠更好地處理部分有序的數(shù)據(jù)集。因此，一種常見的做法是結(jié)合多種間隔序列，先使用較大的間隔進行排序，然后逐漸縮小間隔直到最后一次使用間隔為1進行最后的排序。
• 雖然不同的間隔序列會對排序的效率產(chǎn)生影響，但希爾排序的時間復雜度仍然是一個開放問題，至今沒有找到一個確定的最優(yōu)間隔序列。因此，選擇合適的間隔序列是一個經(jīng)驗性的問題，需要根據(jù)具體情況進行嘗試和調(diào)整。

所以，我們當今學習，只需要站在巨人的肩膀上往前走，不必自己再去深造輪子??，ok，下面將希爾排序的代碼放置下面。

3.3 代碼實現(xiàn)

//希爾排序
void ShellSort(int* a, int n)
{

	int gap = n;
	while (gap > 1)
	{
		//進行多次預排序，加上最后一組直接插入排序。
		gap = gap / 3 + 1;
		//gap = gap / 2;
		
		 //gap組并排
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

3.4 希爾排序時間復雜度

希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，
這里借用《數(shù)據(jù)結(jié)構(gòu)-用面相對象方法與C++描述》書中的一段描述：

目前對于gap的取值，咱們都是站在巨人的肩膀上學習，Knuth進行了大量的試驗統(tǒng)計，以我們的數(shù)學知識證明還是挺困難的，如果數(shù)學功底好的小伙伴可以自己試著證明一下，所以這里我們暫時就按照：O(N^1.25)到O(1.6 * N^1.25)來算。

四、總結(jié)

總結(jié)一下，插入排序和希爾排序的區(qū)別主要在以下幾個方面：

思想：插入排序?qū)⒋判蛐蛄锌醋魇且雅判蚝臀磁判騼刹糠郑饌€插入元素；而希爾排序通過分組的方式，對整個序列進行多次插入排序。
效率：希爾排序相對于插入排序來說，可以在某些情況下更快地完成排序，尤其是對于大規(guī)模數(shù)據(jù)集。直接插入排序呢，如果待排序的數(shù)據(jù)集基本有序或者小規(guī)模，插入排序的性能較好。
穩(wěn)定性：插入排序是穩(wěn)定的排序算法，相等元素的相對位置在排序后不會改變。然而，當希爾排序涉及到跳躍式移動元素時，改變了元素的相對位置，是不穩(wěn)定的。

????本章節(jié)完，后續(xù)會補充二叉樹進階內(nèi)容知識，小伙伴們可以持續(xù)關(guān)注，若本篇文章對你有幫助的話，可以三連支持博主哦~，另外本篇內(nèi)容有編寫有誤的話，可以私聊博主進行糾正！文章來源地址http://www.zghlxwxcb.cn/news/detail-484662.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法篇】手撕排序算法之插入排序與希爾排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！