單趟插入動(dòng)圖：

全過(guò)程動(dòng)圖:

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
				a[end + 1] = a[end];
			else
				break;
			end--;
		}
		a[end + 1] = tmp;
	}
}

復(fù)雜度/穩(wěn)定性分析
復(fù)雜度:

根據(jù)上面的動(dòng)圖我們可以發(fā)現(xiàn)，當(dāng)元素集合越接近有序，直接插入的時(shí)間效率越高，當(dāng)元素集合已經(jīng)有序時(shí)，時(shí)間復(fù)雜度便是O(N)，即遍歷一遍數(shù)組（最優(yōu)情況）。

而時(shí)間復(fù)雜度我們看的是最壞情況，即數(shù)組元素逆序的情況。此時(shí)每次插入相當(dāng)于頭插，而頭插的時(shí)間復(fù)雜度為O(N)，因此總時(shí)間復(fù)雜度為O( 插入次數(shù) * 單次插入時(shí)間復(fù)雜度 ) = O(N^2)。

而除了待排序數(shù)組之外只有常數(shù)級(jí)的輔助空間，空間復(fù)雜度為O(1)。

穩(wěn)定性:

由于我們是大于tmp才進(jìn)行元素挪動(dòng)，當(dāng)?shù)扔趖mp時(shí)直接將tmp放到后方，不會(huì)對(duì)相同元素的順序進(jìn)行改變，因此直接插入排序是穩(wěn)定的排序

四、希爾排序

• 基本思想
  希爾排序又稱縮小增量法，其基本思想是：選出一個(gè)整數(shù)gap表示增量，根據(jù)gap將待排序的記錄分為gap組，所有距離為gap的記錄分在同一組，然后對(duì)每一組進(jìn)行直接插入排序。隨著排序次數(shù)的增多，增量gap逐漸減少，當(dāng)gap=1時(shí)，即所有記錄分在同一組進(jìn)行直接插入排序，排序完成后序列便有序了，算法結(jié)束。分組方法如下：

過(guò)程分析:

1. 首先，我們需要對(duì)gap的初始值進(jìn)行確定，這并沒(méi)有一個(gè)確定的答案，一般是按照數(shù)據(jù)量來(lái)進(jìn)行選取。一般我們選取gap = n/3 + 1或者gap = n/2作為gap的初始值。
2. 根據(jù)算法的思想，我們觀察到gap是在不斷地進(jìn)行縮小，最后縮小到1進(jìn)行直接插入排序。因此我們gap的縮小增量可以繼續(xù)使用gap = gap/3 + 1或gap = n/2來(lái)表示。
3. 對(duì)1、2點(diǎn)進(jìn)行合并后，我們可以這樣用來(lái)表示gap的迭代更新：

int gap = n; //n為序列元素個(gè)數(shù)
while(gap > 1)
{
    //gap = gap/2;
    gap = gap/3 + 1;
 
    //每組進(jìn)行直接插入排序
    //...
}

上面的循環(huán)在以下兩種情況下會(huì)結(jié)束：

• n == 1：即序列只有一個(gè)元素，此時(shí)無(wú)需進(jìn)行排序，不會(huì)進(jìn)入循環(huán)
• n != 1 ，gap == 1：由于gap的更新是在插入排序之前，因此當(dāng)循環(huán)判斷到gap == 1時(shí)，上一次進(jìn)行的就是以1為gap增量的直接插入排序，此時(shí)序列已經(jīng)有序，退出循環(huán)。

---

為什么要取gap = gap/3 + 1而不是gap = gap/3？

由于最后gap要縮小到1進(jìn)行直接插入排序，而如果我們選取gap = gap/3時(shí)，假設(shè)gap初始為6，第一次更新后gap=2，第二次更新后gap=0(向下取整)，循環(huán)便結(jié)束了，并不會(huì)進(jìn)行g(shù)ap=1時(shí)的插入排序。因此，為了避免這種情況的發(fā)生，我們讓gap = gap/3 + 1保證最后一次gap一定為1。

---

那為什么取gap = gap/2而不是gap = gap/2 + 1？

這種情況不需要處理的原因是gap不可能等于0，因?yàn)檫M(jìn)入循環(huán)的條件是gap>1,而gap只有等于0或1時(shí)gap/2才會(huì)為0。因此，無(wú)論gap初始為多少，最后一定都會(huì)在gap=1處停下。并且，當(dāng)gap=2時(shí)，使用gap = gap/2 + 1會(huì)出現(xiàn)死循環(huán)/font>噢

4. 每組之間進(jìn)行的就是我們上面介紹的直接插入排序，不一樣的是相鄰元素的距離是gap而不是1。以下是gap = 3時(shí)的單趟希爾排序的動(dòng)圖過(guò)程：

5. 下面是希爾排序的全過(guò)程（以gap = gap/3 + 1為例）：

6. 通過(guò)觀察，我們可以發(fā)現(xiàn)實(shí)際上希爾排序就是直接插入排序的優(yōu)化版。隨著每一趟的分組排序，序列越來(lái)越接近有序。前面我們說(shuō)過(guò)，直接插入排序在序列越接近有序的情況下效率越高，希爾排序就是通過(guò)每趟的預(yù)排序來(lái)使得序列越來(lái)越接近有序，從而提高直接插入排序的整體效率。
7. 要點(diǎn)提煉：當(dāng)gap > 1時(shí)，對(duì)序列進(jìn)行分組預(yù)排序，目的是使得序列越來(lái)越接近有序；當(dāng)gap == 1時(shí)，數(shù)組接近有序，此時(shí)進(jìn)行直接插入排序效率大幅提高。

//寫(xiě)法1：一組一組排
void ShellSort1(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//1：gap > 1,預(yù)排序
		//2：gap == 1，直接插入排序
		gap = gap / 3 + 1; //縮小增量
		for (int j = 0; j < gap; j++) //一組一組進(jìn)行插入排序，共gap組
		{
			//對(duì)當(dāng)前組進(jìn)行直接插入排序,組內(nèi)相鄰元素相距gap。
			//(其實(shí)就相當(dāng)于把上面介紹的直接插入排序代碼中的-1改成-gap即可)
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (tmp < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
 
		}
 
	}
}

但是，上面的代碼實(shí)際上還可以寫(xiě)得更加簡(jiǎn)潔

我們知道每個(gè)組的元素都相距gap，而組與組之間距離都為1。那么，我們實(shí)際上不用一組一組分開(kāi)排，而是采用多組并排的方式，這樣就可以少寫(xiě)一個(gè)for循環(huán)，代碼如下

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

復(fù)雜度/穩(wěn)定性分析

? 復(fù)雜度:

? 盡管上面的代碼有多個(gè)循環(huán)嵌套，但這并不意味著希爾排序的效率低下。我們根據(jù)代碼來(lái)分析一下希爾排序的時(shí)間復(fù)雜度，過(guò)程如下圖所示：

我們可以看到，在gap很大或者gap很小的情況下，每趟排序的時(shí)間復(fù)雜度為O(N)，共進(jìn)行l(wèi)og3n趟，那我們是不是可以認(rèn)為希爾排序的時(shí)間復(fù)雜度為O(NlogN)？實(shí)際上并不行，因?yàn)楫?dāng)gap處于中間的過(guò)程時(shí)，時(shí)間復(fù)雜度的分析實(shí)際上是個(gè)很復(fù)雜的數(shù)學(xué)問(wèn)題。每一趟預(yù)排序之后都對(duì)下一趟排序造成影響，這就好比疊buff的過(guò)程。

以下分別是兩本書(shū)中對(duì)希爾排序時(shí)間復(fù)雜度的說(shuō)法：

1、《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》— 嚴(yán)蔚敏

2、《數(shù)據(jù)結(jié)構(gòu)-用面相對(duì)象方法與C++描述》— 殷人昆

因?yàn)槲覀兩厦娴膅ap是按照Knuth提出的方式取值的，并且Knuth進(jìn)行了大量的試驗(yàn)統(tǒng)計(jì)，時(shí)間復(fù)雜度我們就按照：O(n^1.25)到O(1.6n^1.25)來(lái)進(jìn)行取值。

然后就是空間復(fù)雜度，由于我們依舊只用到了常數(shù)級(jí)的輔助變量，因此空間復(fù)雜度為O(1)。

穩(wěn)定性:

由于希爾排序是分組進(jìn)行排序，當(dāng)相同的數(shù)被分到不同組時(shí)，很可能就會(huì)改變相同的數(shù)的順序，因此，希爾排序是不穩(wěn)定的排序。

五、 選擇排序

• 思想 : 每一次從待排序的數(shù)據(jù)元素中選出最小(升序)或最大(降序)的一個(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。
• 選擇過(guò)程：以下是對(duì)某個(gè)序列進(jìn)行選擇排序的過(guò)程：

• 動(dòng)圖演示：我們一樣通過(guò)動(dòng)圖感受一下選擇排序的過(guò)程：

• 循環(huán)控制：類似的，我們需要兩層循環(huán)來(lái)控制選擇排序的過(guò)程。內(nèi)層循環(huán)遍歷序列找出最大/最小值，外層循環(huán)控制選擇的次數(shù)。
• 外層循環(huán)結(jié)束條件：每一次遍歷完都可以選出一個(gè)數(shù)換到起始位置，一共N個(gè)數(shù)，故要選N-1次(最后一個(gè)數(shù)不需要選擇)

for (int i = 0; i < n-1; i++) //外層循環(huán)，共要選擇n-1次
{
      ;
}

• 內(nèi)層循環(huán)結(jié)束條件：內(nèi)層循環(huán)通過(guò)比較進(jìn)行選數(shù)，一開(kāi)始N個(gè)數(shù)需要比較N-1次，然后每趟結(jié)束后下一次選擇的起始位置就往后移動(dòng)一位，比較次數(shù)減1

for (int i = 0; i < n-1; i++) //外層循環(huán)，共選擇n-1次
{
	for (int j = i + 1; j < n; j++) //內(nèi)層循環(huán)，起始位置開(kāi)始向后進(jìn)行比較，選最小值
	{
           ;
	}
}

• 完整代碼：

void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}


void SelectSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++) //外層循環(huán)，共選擇n-1次
	{
		int mini = i; //記錄最小值的下標(biāo)，初始為第一個(gè)數(shù)下標(biāo)
		for (int j = i + 1; j < n; j++) //內(nèi)層循環(huán)，起始位置開(kāi)始向后進(jìn)行比較，選最小值
		{
			if (a[mini] > a[j]) //比最小值小，交換下標(biāo)
			{
				mini = j;
			}
		}
		swap(&a[mini], &a[i]); //將最小值與起始位置的數(shù)據(jù)互換
	}
}

• 時(shí)間/空間復(fù)雜度：一共選了N-1次，每次選擇需要比較N-1，N-2，N-3…次，加起來(lái)和冒泡一樣時(shí)間復(fù)雜度為O(N)；沒(méi)有用到輔助空間，空間復(fù)雜度為O(1)
• 穩(wěn)定性分析：由于是選數(shù)交換，在交換的過(guò)程中很可能會(huì)打亂相同元素的順序，例如下面這個(gè)例子：

我們發(fā)現(xiàn)，在第一趟交換中，黑5被交換到了紅5后面，在整個(gè)排序結(jié)束后，黑5依然在紅5的后方，與最開(kāi)始的順序不一致。由此我們可以得出，選擇排序是不穩(wěn)定的排序。

六、各大排序算法的復(fù)雜度和穩(wěn)定性

本次的內(nèi)容到這里就結(jié)束啦。希望大家閱讀完可以有所收獲，同時(shí)也感謝各位鐵汁們的支持。文章有任何問(wèn)題可以在評(píng)論區(qū)留言，小羊一定認(rèn)真修改，寫(xiě)出更好的文章~~

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-752918.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】手撕排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！