前言

??在我們生活的這個世界中到處都是被排序過的東東，可以說排序是無處不在，
常見的莫過于點外賣，按照「銷量最高」「好評最多」等選擇你今日的午餐；考試按照「分數高低」排名次，

值得注意的是：排序有很多種，它們適合的情況不同，需根據不同場景運用，這些排序演算法中對應一些基本思想，了解實作原理比光看代碼更重要！

提示：以下排序均以升序實作，代碼僅供參考

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

一、插入排序

??插入排序的原理應該是最容易理解的了，因為只要你打過撲克牌，應該能夠秒懂，插入排序是一種最簡單直觀的排序演算法，它的原理是通過構建有序序列，對于未排序資料，在已排序序列中從后向前掃描，找到相應位置并插入，如下圖：

🌱演算法思想

通過不斷將當前元素 「插入」到 「有序」 序列中，直到所有元素都執行過 「插入」 操作，則排序結束，

??動圖演示

🎯演算法分析

單趟分析：

1.假定 「前n-1個」數已經有序，「第n個」數從「第 n-1個」開始，自后向前逐一比較，
2.當前一個數 大于「第n個」數時，將該「元素」往后移.
3.當遇到一個 小于等于「第n個」數的「元素」或來到「第一個元素位置」時，先將「該元素」往后移，以空出該位置，并將「第n個」數移動到此處，至此，單趟結束

多趟分析：

如何做到前n個元素有序呢？即從第一個元素開始，依次往后進行插入操作，直至最后一個元素為止

例：前5個元素已經有序

??我們看到，首先需要將 「第六個元素」 和 「第五個元素」 進行 「比較」 ，如果 前者 大于 后者 ，則進行 「交換」 ，然后再比較 「第六個元素」 和 「第四個元素」 ，以此類推，直到 「第六個元素」 被移動到 「合適位置」 ，
??然后，進行第二輪 「比較」，直到 「第七個元素」 被移動到 「合適位置」 ，
??最后，經過一定輪次的 「比較」 和 「交換」 之后，一定可以保證所有元素都是 「升序」 排列的，

🔑參考代碼
??值得注意的是:當第 i 個元素向后移時，即第 i+1 個元素的值被覆寫為第 i 個元素的值，但第 i 個元素值仍未變.因此，跳出回圈后，第 i 個元素位置即為待插入位置
代碼如下：

void InsertSort(int* a, int n)
{
	assert(a);
	//所有趟
	for (int i = 0; i < n - 1; i++)
	{
		// 單趟排序
		// end 表示有序序列最后元素的下表
		int end =  i;
		// 待插入的元素
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				//后一個元素被前一個元素覆寫
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		// 待插入位置，值為 tmp 
		a[end + 1] = tmp;
	}
}

🕘時間復雜度
??由圖可以看出，當待排序列越接近有序，其時間復雜度越低，越接近無序，時間復雜度越高，例如：當整體序列為「升序序列」時為O(N) ,最壞情況下，即整體序列為「降序序列」時為O( N 2 N^2 N2)

二、希爾排序

??希爾排序，也稱遞減增量排序演算法，按其設計者希爾（Donald Shell）的名字命名，該演算法由希爾 1959 年公布，是插入排序的一種更高效的改進版本，但希爾排序是非穩定排序演算法，

希爾排序是基于插入排序的以下兩點性質而提出改進方法的：

1.插入排序在對幾乎已經排好序的資料操作時，效率高，即可以達到線性排序的效率；
2.但插入排序一般來說是低效的，因為插入排序每次只能將資料移動一位；

🌱演算法思想

??希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序，
??即，先進行預排序，使之接近有序，再進行插入排序，
??動圖演示

注:每一趟排序中，相同顏色為一組

🎯演算法分析

??由圖可以看出，希爾排序一個特點是：子序列的構成不是簡單的 「逐段分割」,而是將相隔某個增量 「gap」 的資料組成一個子序列，如上圖：

第一趟排序時: gap = 5 ， 9 和 4 為一組， 1 和 8 為一組， 2 和 6 為一組， 3 和 5 為一組， 5 和 7 為一組，
第二趟排序時: gap = 2 ， 4，2，5，5，8為一組， 1，3，6，7，9為一組.
第三趟排序時: gap = 1 ，整體為一組

??因為是相隔 gap 的元素為一組，每組各自進行排序，因此在整體來看，每個元素的移動是「跳躍式」的
??不斷減小 gap，整體愈加接近「有序」
??當 gap = 1 時，即為 「插入排序」,只需要對以上數列進行簡單的微調，不需要大量的移動操作即可完成整個陣列的排序，

??這里有個問題： gap 取多少合適？

gap 越大，資料挪動快，但越不接近有序
gap 越小，挪動越慢，但越接近有序

??事實上，gap 的取法有多種，最初Shell提出取gap = 「n / 2」，gap=「gap / 2」，直到 gap = 1,后來Knuth提出取gap=「gap / 3」+1，還有人提出都取奇數為好，也有人提出各gap互質為好，無論哪一種主張都沒有得到證明，

🔑參考代碼

void ShellSort(int* a, int n)
{
	// gap > 1  預排序
	// gap == 1 直接插入排序
	int gap = n;
	while (gap > 1)
	{
		// 保證最后一次為 1
		gap = gap / 3 + 1;
		// 間隔為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;
		}
	}
}

🕘時間復雜度
??時間復雜度:O(N log N)
??其中，《資料結構(C語言版)》— 嚴蔚敏 有以下說明

三、選擇排序

🌱演算法思想
??每一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在待排序列的起始位置，直到全部待排序的資料元素排完 ，

??動圖演示

🎯演算法分析

??首先，找到待排序列中「最小/大」的元素，拎出來，將它和序列的「第一個元素」交換位置，第二步，在剩下的元素中繼續尋找「最小/大」的元素，拎出來，和序列的「第二個元素」交換位置，如此回圈，直到整個序列排序完成，
??實際上，我們可以一次選出「最小」和「最大」的元素，分別置于待排序列的「起始」和「末尾」，以提高演算法效率，這就要求，我們必須考慮待排序列的「末端位置」，以及「最大/小」元素的「下標」，

🔑參考代碼
錯誤范例：

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	// 當begin 和 end 相遇，即只有一個元素
	while (begin < end)
	{
		// 分別用以記錄最大/小值下標
		int maxi = begin;
		int mini = begin;
		for (int i = begin; i <= end; i++)
		{
			//大于最大值，重新賦值
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			//小于最小值，重新賦值
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		//將最小值與起始位置交換
		Swap(&a[mini], &a[begin]);
		//最大值與末尾交換
		Swap(&a[maxi], &a[end]);
		//對應新的首尾位置
		end--;
		begin++;
	}
	//跳出回圈，則排序完成
}

??事實上，運行結果并不正確，示例如圖

??分析第二次運行，第一趟交換，可以發現，當「maxi 」與 「begin 」重合時，進行第一次「交換」后，「maxi 」對應值來到了 「mini」的位置，故須考慮「maxi 」是否與「begin 」重合的情況，如圖：

正確代碼如下：

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	// 當begin 和 end 相遇，即只有一個元素
	while (begin < end)
	{
		// 分別用以記錄最大/小值下標
		int maxi = begin;
		int mini = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		Swap(&a[mini], &a[begin]);
		//考慮maxi 與 begin關系，相同，則maxi對應位置變化為 mini
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&a[maxi], &a[end]);
		//對應新的首尾位置
		end--;
		begin++;
	}
	//跳出回圈，則排序完成
}

🕘時間復雜度
??時間復雜度:O( N 2 N^2 N2)
??直接選擇排序思想非常好理解，但是效率不是很好，實際中很少使用，且其穩定性：不穩定

四、堆排序

??堆排序(Heapsort)是指利用堆積樹（堆）這種資料結構所設計的一種排序演算法，它是選擇排序的一種，它是通過堆來進行選擇資料，需要注意的是排升序要建大堆，排降序建小堆，
💭 準備知識
大根堆和小根堆
性質：每個結點的值都大于其左孩子和右孩子結點的值，稱之為大根堆；每個結點的值都小于其左孩子和右孩子結點的值，稱之為小根堆，如圖：

基本概念
查找陣列中某個數的父結點和左右孩子結點，比如已知索引為i的數，那么
父結點索引：(i - 1) / 2（取整）
左孩子索引：2 * i + 1
右孩子索引：2 * i + 2

🌱演算法思想

1.首先將待排序的陣列構造成一個大根堆，此時，整個陣列的最大值就是堆結構的頂端
2.將頂端的數與末尾的數交換，此時，末尾的數為最大值，剩余待排序陣列個數為 n - 1
3.將剩余的 n - 1 個數再構造成大根堆，再將頂端數與 n - 1 位置的數交換，如此反復執行，便能得到有序陣列

??動圖演示
建大堆：

堆排序：

🎯演算法分析
建大堆：

建堆有一個方法，叫做「向下調整法」 ，那么如何實作呢？
如圖：左右子樹均為大堆

1.選出左右孩子中較大元素，若大于根節點，與之交換
2.原來的大孩子變為父親節點，與其孩子比較，重復步驟一，直至調整到葉子節點為止，
若孩子均小于父親節點，則無需再處理，已經是大根堆了，如圖所示：

那么，如何保證左右子樹均為大根堆呢？即從最后一個根節點往前進行「向下調整法」 ，即可保證左右子樹均為大堆，

🔑參考代碼
向下調整法：

void AdjustDown(int* a, int n, int root)
{
	//創建孩子節點
	int child = root * 2 + 1;
	while (child < n)
	{
		// 若child == n - 1，不可加
		//找到最大的孩子
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		// 與最大的孩子進行交換
		if (a[root] < a[child])
		{
			Swap(&a[root], &a[child]);
			root = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

堆排序：

void HeapSort(int* a, int n)
{
	assert(a);
	//建大堆
	int root = (n - 1 - 1) / 2;
	while (root >= 0)
	{
		AdjustDown(a, n, root);
		root--;
	}
	//堆排序
	while (n)
	{
		//首位交換，保證最大的來到最后
		Swap(&a[0], &a[n - 1]);
		// 參與排序的元素個數減 1
		n--;
		// 向下調整
		AdjustDown(a, n, 0);
	}
}

🕘時間復雜度

??時間復雜度:O(N log N)

五、冒泡排序

??冒泡排序（Bubble Sort）也是一種簡單直觀的排序演算法，它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來，走訪數列的作業是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成，這個演算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端

🌱演算法思想
??通過不斷比較相鄰的元素，如果「左邊的元素」 大于 「右邊的元素」，則進行「交換」，直到所有相鄰元素都保持升序，則排序結束，

??動圖演示

🎯演算法分析

1.比較相鄰的元素，如果第一個比第二個大，就交換他們兩個，
2.對每一對相鄰元素作同樣的作業，從開始第一對到結尾的最后一對，這步做完后，最后的元素會是最大的數，
3.針對所有的元素重復以上的步驟，除了最后一個，
4.持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，
單趟分析：

假設從第一趟開始，將「第一個」元素與「第二個」元素進行「比較」，若「前者」大于「后者」，進行「交換」，隨后，將「第二個」元素與「第三個」元素進行上述操作，直至將「倒數第二個」元素與「最后一個」元素進行「比較」，至此，「最大」元素來到了最后，

多趟分析：

假設共有 n 個數，則須進行 n - 1 趟上述操作，每一趟比較 前 n - i + 1 個數，最大元素來到第 n - i -1 的位置（ i = 1,2,3~~n)

因此冒泡的代碼還是相當簡單的，兩層回圈，外層冒泡趟數，里層依次比較，江湖中人人盡皆知，

🔑參考代碼
??冒泡有一個最大的問題就是這種演算法不管你有序還是無序，閉著眼睛把你回圈比較了再說，針對這個問題，我們可以設定一個臨時遍歷來標記該陣列是否已經有序，如果有序了就不用遍歷了，
代碼如下：

void BubbleSort(int* a, int n)
{
	// 該回圈用于控制趟數
	for (int end = n - 1; end > 0; end--)
	{
		//設定臨時變數exchange，記錄資料是否交換
		int exchange = 0;
		for (int i = 0; i < end - 1; i++)
		{
			if (a[i] > a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
				//exchange 變為1，表示該趟有資料交換
				exchange = 1;
			}
		}
		//若exchange == 0，表示該趟無資料交換，已經有序，跳出回圈
		if (exchange == 0)
			break;
	}
}

🕘時間復雜度
??我們看到嵌套回圈，應該立馬就可以得出這個演算法的時間復雜度:O( N 2 N^2 N2)

六、快速排序

??快速排序(QuickSort)是對冒泡排序的一種改進，
🌱演算法思想
??它的基本思想是，通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序，

遞回版

hoare版

🌱演算法思想
??快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該程序，直到所有元素都排列在相應位置上為止，

🎯演算法圖解
單趟：

??選擇最左邊的元素作為關鍵值key,
??首先哨兵「 j 」 開始出動，因為此處設定的基準數是最左邊的數，所以需要讓哨兵 「 j 」 先出動，這一點非常重要（請自己想一想為什么），哨兵「 j 」 一步一步地向左挪動（即 j – ），直到找到一個小于 「 key」 的數停下來，接下來哨兵 「 i 」 再一步一步向右挪動（即 i++ ），直到找到一個大于 「 key」的數停下來，最后哨兵 j 停在了數字 5 面前，哨兵 「 i 」 停在了數字 7 面前，交換資料…

??接下來哨兵 「 j 」 繼續向左挪動（注：每次必須是哨兵「 j 」 先出發），他發現了4 （比基準數「 key」要小，滿足要求）之后停了下來，哨兵「 i 」 也繼續向右挪動，他發現了 9（比基準數 「 key」 要大，滿足要求）之后停了下來，此時再次進行交換…

??第二次交換結束，“探測”繼續，哨兵 「 j 」 繼續向左挪動，他發現了 3之后又停了下來，哨兵「 i 」 繼續向右移動，糟啦！此時哨兵「 i 」 和哨兵「 j 」相遇了，說明此時“探測”結束，我們將「 key」 和哨兵「 i 」 所處地址的值進行交換，單趟探測結束，并回傳基準值的下標

多趟：

??每一趟回傳一個基準值下標，表示該基準值已來到正確位置，通過回傳值，將待排序列分割左右兩組，重復上述步驟，

🔑參考代碼

單趟代碼如下：

int PartSort1(int* a, int left, int right)
{
	//選擇一個基準值
	int keyi = left;
	while (left < right)
	{
		//注意：left < right 這一判斷條件必不可少
		//遇到小于基準值則停下
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//遇到大于基準值則停下
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		//交換
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	return left;
}

🕘時間復雜度
??時間復雜度:O(N log N)

挖坑法

🎯演算法圖解
單趟動圖如下：

如圖可以看出:

1.先選出一個值存放在key中，通常為最左或最右邊的值
2.定義L，R，(若key選自最左邊，則R先走）
3.當R遇到小于key的值，將該值移動到坑(hole)中，并將該處變為新的坑(hole)
4.當L遇到大于key的值，將該值移動到坑(hole)中，并將該處變為新的坑(hole)
5.重復上述步驟3、4，當L和R相遇，停止移動，并將key移動到 坑(hole) 中，至此，單趟結束，

🔑參考代碼
單趟代碼如下：

int PartSort2(int* a, int left, int right)
{
	// 所需正確移動的關鍵數
	int key = a[left];
	// 初始坑位
	int hole = left;
	while (left < right)
	{
		// 右邊，遇到小的則停止
		while (left < right && a[right] >= key)
		{
			right--;
		}
		// 填坑，更換新的坑位置
		a[hole] = a[right];
		hole = right;
		// 左邊，遇到大的則停止
		while (left < right && a[left] <= key)
		{
			left++;
		}
		// 填坑，更換新的坑位置
		a[hole] = a[left];
		hole = left;
	}
	// 當左右相遇，即 key 的正確位置
	a[hole] = key;
	return left;
}

🕘時間復雜度
??時間復雜度:O(N log N)

前后指標法

🎯演算法圖解
單趟動圖如下：

由圖可知其步驟如下:
1.先選出一個值存放在key中，通常為最左或最右邊的值
2.定義prev和cur, prev 指向待排序列起始位置，且cur= prev + 1
3.當cur指向的值小于key，先 ++prev ，再將prev所指向的值與cur所指向的值進行交換，如此重復至cur越界
4.此時，將key與prev所指向的值交換，可以得到，key左邊值均比其小，key右邊值均比其大，

🔑參考代碼
單趟代碼如下：

int PartSort3(int* a, int left, int right)
{
	
	int keyi = left;
	int cur = left + 1;
	int prev = left;

	while (cur <= right)
	{
		if (a[cur] <= a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[keyi], &a[prev]);

	return prev;
}

🕘時間復雜度
??時間復雜度:O(N log N)

📖代碼優化
??實際上，上述圖片僅僅是理想狀態下所實作，舉個例子，倘若每次選擇的key均是最大/小值，則上述區間被劃分為分別包含 n - 1 個和 0 個元素的區間，故而時間復雜度O( N 2 N^2 N2).因此選擇一個適中的key是必要的，在此給出三數取中法，如下：

??選擇給定區間的左值，右值，以及中間元素的值，將次大的元素與區間首元素交換，再將key選定為新的首元素，從而保證key左右均有元素，

代碼如下：

int GetMidIndex(int* a, int left, int right)
{
	//防止溢位
	int mid = left + (right - left) / 2;

	if (a[left] > a[right])
	{
		if (a[mid] > a[left])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] > a[right])
		{
			return right;
		}
		else if (a[mid] > a[left])
		{
			return mid;
		}
		else
		{
			return left;
		}
	}
}

優化后代碼如下：

int PartSort1(int* a, int left, int right)
{
	//得到中間值元素下標
	int keyi = GetMidIndex(a, left, right);
	//與首元素交換
	Swap(&a[left], &a[keyi]);
	keyi = left;

	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);

	}
	Swap(&a[left], &a[keyi]);
	return left;
}

其他兩種方法優化方式同上，

🌳多趟代碼

void QuickSort(int* a, int left, int right)
{
	//遞回條件
	if (left >= right)
	{
		return;
	}
	// 中間值下標
	//int key = PartSort1(a, left, right);
	//int key = PartSort2(a, left, right);
	int key = PartSort3(a, left, right);
	//遞回左區間
	QuickSort(a, left, key - 1);
	//遞回右區間
	QuickSort(a, key + 1, right);
}

非遞回

??我們都知道，遞回會開辟新的函式堆疊幀，因此將遞回版轉化為非遞回版，需借用一個資料結構–堆疊 不熟悉的可以參看一下我的這篇文章👉【資料結構】堆疊
??通過上述文章，我們可以發現，三種遞回版本不過是單趟排序有些許差異，多趟排序仍一致且遞回實作，因此我們可以將單趟函式封裝起來，將遞回轉化為非遞回，可以發現，遞回實際上是將大區間分成許多小區間，將小區間有序化，則大區間亦有序，

🎯演算法思路

??

1.將待排區間的第一個和最后一個元素下標入堆疊，
2.進行一趟排序，得到回傳的key的下標，則得到新的兩段區間，將舊區間出堆疊，新區間入堆疊，
3.重復步驟2，直到堆疊為空，

🔑參考代碼

void QuickSortNonR(int* a, int left, int right)
{
	assert(a);
	//借助堆疊來實作
	//創建堆疊
	Stack st;
	//初始化堆疊
	StackInint(&st);
	//先入堆疊，否則無法進入回圈
	StackPush(&st, right);
	StackPush(&st, left);
	//當堆疊為空，則已排好序
	while (!StachEmpty(&st))
	{
		//獲取堆疊頂元素，需注意順序
		int begin = StackTop(&st);
		StackPop(&st);
		int end = StackTop(&st);
		StackPop(&st);
		//取中間值
		int mid = PartSort3(a, begin, end);
		//如果左區間范圍大于1，進行入堆疊
		if (begin < mid - 1)
		{
			StackPush(&st, mid - 1);
			StackPush(&st, begin);
		}
		//右區間同理
		if (end > mid + 1)
		{
			StackPush(&st, mid + 1);
			StackPush(&st, end);
		}

	}
	StackDestroy(&st);
	//free()
}

七、歸并排序

遞回版

🌱演算法思想
?? 歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序演算法,該演算法是采用分治法（Divide and Conquer）的一個非常典型的應用，將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序，若將兩個有序表合并成一個有序表，稱為二路歸并，

??動圖演示
圖一：

圖二：

🎯演算法分析

1.由圖可以發現，我們需先將待排序列分成許多子序列，直至每個序列僅有1個元素，并開辟 新的相同大小的陣列
2.將子序列元素進行排序，因為每個序列分為新的1~2 個子序列，排完子序列后賦值給原陣列，回傳上一層，再進行新一輪排序，再回傳上一輪，直至排序完成，
3.基于上述分析，可以發現，我們需先遞回，再排序，且需要一個子函式來實作遞回功能，

🔑參考代碼

void _MergeSort(int* a, int left, int right,int* tmp)
{
	if (left >= right)
		return;
	//防止left + right溢位
	int mid = left + (right - left) / 2;
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);

	//記錄left初始位置
	int index = left;
	//左區間
	int begin1 = left;
	int end1 = mid;
	//右區間
	int begin2 = mid + 1;
	int end2 = right;
	//將兩組元素進行排序至臨時陣列中
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[left++] = a[begin1++];
		else
			tmp[left++] = a[begin2++];
	}
	while (begin1 <= end1)
	{
		tmp[left++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[left++] = a[begin2++];
	}
	//歸并后，拷貝至原陣列
	for (int i = index; i <= right; i++)
	{
		a[i] = tmp[i];
	}
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(n * sizeof(int));
	//避免malloc失敗
	if (tmp == NULL)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
	tmp = NULL;
}

🕘時間復雜度
??時間復雜度:O( N 2 N^2 N2) ，歸并的缺點在于需要O(N) 的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題，

非遞回

🎯演算法分析

??通過上述內容，我們可以發現，每次遞回先將待排序列分為多組，每組有左右兩個區間，直至每個區間僅有一個元素后，再排序，由此我們可以先將待排序列分為多組，每個區間僅一個元素，每一趟將兩個區間進行一次歸并，再歸并下一組，下一趟排序時，新區間又是由上一趟兩個區間元素構成，基于此，我們有以下思路:

1.每一趟進行多組排序
2.每進行一趟排序，重新分組

如圖:

??不過，有以下三種情況值得注意：
情況一:右區間不存在

情況二:左區間不完整

情況三:右區間不完整

🔑參考代碼

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(n * sizeof(int));
	//避免malloc失敗
	if (tmp == NULL)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	//初始組內元素個數為1
	int GroupNum = 1;
	while (GroupNum < n)
	{
		for (int i = 0; i < n; i += 2 * GroupNum)
		{
			//左右區間
			int begin1 = i;
			int end1 = i + GroupNum - 1;
			int begin2 = i + GroupNum;
			int end2 = i + 2 * GroupNum - 1;
			//記錄區間初始位置
			int index = begin1;
			//end2越界，需要修正后歸并
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			//[begin2,end2] 不存在, 修正為一個不存在的區間
			if (begin2 >= n)
			{
				begin2 = n + 1;
				end2 = n;
			}
			//end1越界,修正一下
			if (end1 >= n)
			{
				end1 = n - 1;
			}
			
			//將兩組元素進行排序至臨時陣列中
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
					tmp[index++] = a[begin1++];
				else
					tmp[index++] = a[begin2++];
			}
			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
		}	
		//歸并后，拷貝至原陣列
		for (int i = 0; i < n - 1; i++)
		{
			a[i] = tmp[i];
		}
		GroupNum *= 2;
	}
	free(tmp);
}

八、計數排序

??計數排序是一種非基于比較的排序演算法，我們之前介紹的各種排序演算法幾乎都是基于元素之間的比較來進行排序的，
🌱 演算法思想
??計數排序又稱為鴿巢原理，是對哈希直接定址法的變形應用，
??動圖演示

🎯演算法分析

??計數排序，顧名思義，該演算法不是通過比較資料的大小來進行排序的，而是通過統計待排序列中元素出現的次數，然后通過統計的結果將序列回收到原來的序列中，步驟如下：

1.首先，準備一個「 計數器陣列 」 ，通過一次 「 遍歷 」 ，找出最大值「 max」，
2.開辟出一個大小為「 max + 1」的陣列，
3.再次 「 遍歷 」 原陣列，統計元素每個元素出現次數，每個元素值與新陣列下標「 一 一對應」，例如，數字 「5」對應新陣列下標為 5 的地址，每出現一次 「5」，則新陣列下標為 5 處的值++.
4. 「 遍歷 」 新陣列，嵌套兩層回圈，外層新陣列從頭到尾 「 遍歷 」 ，內層進行「 原陣列賦值 」，如果新陣列遍歷處值為 0 ，則無需賦值，直至遍歷完，

??有個問題值得思考：假設原陣列為{1000,1002,1005,1003,1008,1004}.那么開辟 1008 + 1個元素大小的陣列，勢必造成前1000個空間浪費，此外,倘若陣列為 {-1,-2,-3},還會出現陣列越界的情況，因此，我們必須考慮上述兩種情況，

??在此，我們再來優化一下，通過一次 「 遍歷 」 ，找出最大值「 max」和最小值「 min」.則須開辟新陣列大小為「 max - min + 1」.則對應關系相應變化，值為 i 的元素，對應新陣列下標為「 i - min」，下標為 j 的新陣列下標，對應值為「 j + min」.

🔑參考代碼
??基于上述分析，有如下代碼：

void CountSort(int* a, int n)
{
	// 定義最大/小值
	int max = a[0];
	int min = a[0];
	//找出最大/小值
	for (int i = 1; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	//開辟新陣列，同時賦值為 0
	int* tmp = (int*)calloc(max - min + 1, sizeof(int));
	if (tmp == NULL)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	// 遍歷原陣列，統計個數
	for (int j = 0; j < n; j++)
	{
		tmp[a[j] - min]++;
	}
	// 遍歷新陣列
	for (int i = 0,j = 0; j < max - min + 1; j++)
	{
		//進行原陣列重新賦值
		while (tmp[j]--)
		{
			a[i++] = j + min;
		}
	}
}

🕘時間復雜度
??我們看到嵌套回圈，第一反應就是這個演算法的時間復雜度:O( N 2 N^2 N2) ?但事實上并非如此，細想一下，兩層回圈，加起來不過是原陣列重新賦值，故正確的時間復雜度:O(N + range)??
??此外，計數排序也有它的局限性，計數排序只適合「 資料較為集中」，且資料均為「整形」的序列，若資料分散，則會造成資料浪費的情況，

總結

??完整代碼鏈接👉八大排序

對一千萬個資料進行排序，用時如下:

??以上就是本文全部內容了，如有幫助，一鍵三連支持一下吧