八排 八奇跡

排序

排序的概念及其運用

排序的概念

==排序：==所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作，
==穩定性：==假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序演算法是穩定的；否則稱為不穩定的，
==內部排序：==資料元素全部放在記憶體中的排序，
==外部排序：==資料元素太多不能同時放在記憶體中，根據排序程序的要求不能在內外存之間移動資料的排序，

排序運用

來上京東

大學排名

常見的排序演算法

常見排序演算法的實作

插入排序

基本思想

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

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

但是陣列肯定不是有序的，所以我們得先讓陣列有序

先把列印陣列給剝離出來

// 列印陣列
void PrintArray(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}

插入排序

// 插入排序
void InsertSort(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n - 1; i++)	{
		int end = i;
		int x = a[end+1];
		while (end >= 0) {
			//要插入的數比順序中的數小就準備挪位置
			if (a[end] > x) {
				a[end + 1] = a[end];
				end--;
			}
			else {
				//插入的數比順序中的要大就跳出
				break;
			}
		}
		//跳出來兩種情況
		//1.end == -1 的時候
		//2.break 的時候
		//把x給end前面一位
		a[end + 1] = x;
	}
}

插入排序的時間復雜度：O(N²)

最好：O(N) — 順序有序 （接近有序）

最壞：O(N²) — 逆序

插入排序的空間復雜度：O(1)

希爾排序( 縮小增量排序 ) (反正希爾牛逼)

希爾排序是在優化直接插入排序，而且效果超級明顯，為什么是優化呢，因為我們知道直接插入排序接近有序了就會非常快，那我就創造這樣的有序，讓他時間復雜度接近O(N)，我們知道排序的時間復雜度最好情況就是O(N)，而我們接近O(N)也是相當了不起了，基本是接近天花板了

希爾排序法又稱縮小增量法，希爾排序法的基本思想是：先選定一個整數，把待排序檔案中所有記錄分成個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序，然后，取，重復上述分組和排序的作業，當到達=1時，所有記錄在統一組內排好序，

希爾排序步驟

1.分組預排序 ---- 陣列接近有序

按gap分組，對分組值進行插入排序 分成gap組

2.直接插入排序 陣列接近有序，直接插入的時間復雜度就是O(N)

單組多躺

多組插入

間距為gap多組預排實作的時間復雜度O(gap*(1+…+N/gap))

最好：O(N)

最好：O(N)

最壞：O(gap*(1+…+N/gap))

gap越大，預排越快，預排后越不接近有序

gap越小，預排越慢，預排后越接近有序

多組一鍋燉（要是分組插麻煩我們也可以一鍋燉）

多次預排序(gap > 1)+直接插入（gap == 1）

gap/2

gap/3

時間復雜度O(N^1.3)記住就行，反正記住希爾很牛逼就行，希爾排序很快

測直接插入排序和希爾排序的性能（讓你看看什么才叫希爾排序）

堆

資料結構中的堆不同于作業系統中的堆（作業系統中的堆是用來存盤動態記憶體的），資料結構中的堆是資料的存盤方式，資料結構中的堆是完全二叉樹

既然堆是完全二叉樹的形式存盤的那么就非常適合用陣列的方式來表示

堆的概念及結構

如果有一個關鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹的順序存盤方式存盤在一個一維陣列中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，則稱為小堆(或大堆)，將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，

大堆：樹中一個樹及子樹中，任何一個父親都大于等于孩子

小堆：樹中一個樹及子樹中，任何一個父親都小于等于孩子

堆的性質

堆中某個節點的值總是不大于或不小于其父節點的值；
堆總是一棵完全二叉樹，**

堆的結構（這里實作大堆）

既然還是陣列的結構的話就還是順序表的處理方式，陣列指標，size，capacity，雖然物理上我們是用順序表的方式來表示，但是他實際上表示的資料是完全二叉樹，

堆的結構體

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

堆初始化函式HeapInit

就是一個指向NULL的陣列，size 和 capacity都為零

//堆初始化函式
void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

堆銷毀函式HeapDestroy

由于陣列是動態開辟的，所以用完后需要銷毀的，不然會記憶體泄漏

//堆銷毀函式
void HeapDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->size = hp->capacity = 0;
}

堆列印函式HeapPrint

可以想象成一種快速除錯，類似于單片機中的串口列印看資料收發情況

//堆列印函式
void HeapPrint(HP* hp)
{
	int i = 0;
	for (i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

向上調整函式AdjustUp

為了不影響資料的存盤形式（大堆還得是大堆），插入資料就不能破壞大堆的形式，我們需要把堆插入函式中的資料調整給剝離出來

我們可以看到插入的這個資料對其他的節點并沒有什么影響，有影響的只是這個節點到根這條路徑上的節點，如何解決對這條路徑的影響呢，我們可以形象的看到僅僅是在這條路徑上進行向上調整

通過parent = （child-1）/2 找到父親節點，與之進行比較，然后父親小就交換位置（大堆），然后交換后就在找上面的父親節點，直到找到父親大于孩子，就不交換了

//向上調整函式
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[parent] < a[child])//父親小于孩子就交換（大堆）
		{
			a[parent] = a[parent] ^ a[child];
			a[child] = a[parent] ^ a[child];
			a[parent] = a[parent] ^ a[child];
			//交換好后重新稱呼一下孩子與父親
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}

	}
}

堆插入函式HeapPush

//堆插入函式（要保持原來形式，大堆還是大堆，小堆就還是小堆）
void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	//判斷擴容
	if (hp->size == hp->capacity)
	{
		//容量給新的容量
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		//擴容
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		//增容失敗
		if (!tmp)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		//增容成功
		hp->a = tmp;
		hp->capacity = newcapacity;		
	}
	//放資料
	hp->a[hp->size] = x;
	hp->size++;
	//實作大堆
	//這個部分的向上調整其他地方也用的到就把他剝離出來
	AdjustUp(hp->a, hp->size - 1);//child下標
}

判斷堆是否為空函式HeapErmpy

//判斷堆是否為空函式
bool HeapErmpy(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}

回傳堆大小函式HeapSize

//回傳堆大小函式
int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

下面還會用到交換函式，上面也有那么我們不妨把他剝離出來封裝一下，就不需要重復寫了

交換函式Swap

//交換函式void Swap(HPDataType* px, HPDataType* py){	*px = *px ^ *py;	*py = *px ^ *py;	*px = *px ^ *py;}

向下調整函式AdjustDown

//向下調整函式void AdjustDown(HPDataType* a, int size, int parent){	assert(a);	//創建一個孩子變數，有兩個孩子就在這個上加1就行	int child = parent * 2 + 1;	while (child< size)	{		//選大孩子		if (child + 1 < size && a[child] < a[child + 1])		{			child++;		}		//大的孩子還大于父親就交換		if (a[child] > a[parent])		{			Swap(&a[child], &a[parent]);			parent = child;			child = parent * 2 + 1;		}	}}

堆洗掉函式HeapPop

我們可以認為假想根和堆的最后一個元素交換后，把最后一個洗掉，然后再對堆進行操作，你會發現，我們沒有破壞原來的整體結構

//堆洗掉函式（洗掉的是堆頂資料也就是取最值）
//還有不可能一直刪的所以我們需要一個判空函式
void HeapPop(HP* hp)
{
	assert(hp);
	assert(!HeapErmpy(hp));
	//根和堆最后一個元素交換
	Swap(&hp->a[0],&hp->a[hp->size-1]);
	//把最后一個洗掉，就是我們想要洗掉的元素
	hp->size--;
	//向下調整
	AdjustDown(hp->a,hp->size,0);
}

排序

常見的排序演算法

常見排序演算法的實作

選擇排序 最慢排序（最好理解）所以搬血

基本思想：

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

直接選擇排序

在元素集合array[i]–array[n-1]中選擇關鍵碼最大(小)的資料元素
若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素

上面那個就是選擇排序的本質，但是一次就選一個最大或者最小是不是有點浪費，我們一次同時選到最大最小，就是會比傳統的選擇排序快一倍

我們基本看到上面代碼的缺陷就是我們第一個就是最大是時候，最大的就被換走了，而最小的就被換過來了，但是最大的下標還是標記首位置，把最小的換到后面，也就出現了最小的1在后面的現象

解決方法：既然你最大數的下標和begin重合，那最大數被換走的時候，maxi這個下標也要連帶著走

實際上下面 才是我第一次寫的代碼，直接說下次我再也不寫裝逼的交換了

我來道bug惡心之處 看好了跳跳 5 ^ 5 == 0 這就是惡心之處，下次再也不裝逼了

資料交換 剝離出來其他函式也會用到 我明明是簡潔之人為了一時的高級而忘記了樸素罪過罪過

//資料交換
void Swap(int* pa, int* pb) {
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

選擇排序

// 選擇排序
void SelectSort(int* a, int n) {
	int begin = 0;
	int end = n - 1;
	while (begin < end){
		//單趟
		//最大數，最小數的下標
		int mini = begin;//這邊假設是剛開始的下標
		int maxi = end;  //這邊假設是末尾的下標
		int i = 0;
		for (i = begin; i <= end; i++) {
			if (a[i] < a[mini])
				mini = i;
			if (a[i] > a[maxi])
				maxi = i;
		}
		//最小的放前面
		Swap(&a[begin], &a[mini]);
		
		if (begin == maxi)
			//如果最大數就是begin位置的，那么交換的時候最大數連帶著下標一起動
			maxi = mini;
		//最大的放后面
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}

時間復雜度是O(N²) 我們的優化不是質的優化，而是量的優化

最好：O(N²)

最壞：O(N²)

堆排序

堆排序(Heapsort)是指利用堆積樹（堆）這種資料結構所設計的一種排序演算法，它是選擇排序的一種，它是
通過堆來進行選擇資料，需要注意的是排升序要建大堆，排降序建小堆，

向下調整函式

//向下調整函式
void AdjustDown(int* a, int n, int parent)
{
	assert(a);
	//創建一個孩子變數，有兩個孩子就在這個上加1就行
	int child = parent * 2 + 1;
#if HEAP
	while (child < n)
	{
		//選大孩子
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		//大的孩子還大于父親就交換
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
#elif !HEAP
	while (child < n)
	{
		//選小孩子
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}
		//小的孩子還小于父親就交換
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
#endif // HEAP	
}

堆排序代碼

// 堆排序   我們之前講過升序建大堆
void HeapSort(int* a, int n) {
	//建堆時間復雜度O(N)
	//建大堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	//堆排序時間復雜度O(N*logN)
	while (end>0){
		//交換 把最大的放到后面
		Swap(&a[0], &a[end]);
		//在向下調整
		AdjustDown(a,end,0);
		end--;
	}
}

堆排序時間復雜度O(N*logN)

測性能 讓你看看什么叫堆

這里我們測性能就用release版本測吧 因為release版本是程式最優狀態，每個排序都是最好狀態，巔峰打巔峰

1000大小陣列 一千

10000大小陣列 一萬

100000大小陣列 十萬

1000000大小陣列 一百萬

10000000大小陣列 一千萬 我們不帶選擇，插入玩太拉跨了，我們看看希爾，堆在超大資料面前誰性能更優

性能函式圖

排序

常見的排序演算法

常見排序演算法的實作

歸并排序

基本思想

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

實際上歸并我們不是第一次接觸，之前我們也是接觸過的，比如合并兩個有序陣列這個就是歸并思想

但是我們上面的題目是左區間有序，右區間也有序，我們正常題目肯定不會直接給你有序，這時候再深一點，你不是沒有序嗎，那我們再分，分到你無法再分，也就是只有一個了，你能說一個沒有序嗎，肯定不行，所以我們繼續分治，

遞回寫法

看上面的GIF也知道第一反應是遞回

通過除錯看一下現象

歸并順序

歸并排序遞回子函式

// 歸并排序遞回子函式
void _MergeSort(int* a, int left, int right, int* tmp){
	//左大于右說明是空陣列，空陣列就跳
	//左等于右就是我們要的單體有序
	if (left >= right)
		return;
	//防溢位寫法
	int mid = left + (right - left) / 2;
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1,right, tmp);
	//
	int begin1 = left;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = right;
	int i = left;
	//跑空一組就直接跳
	while (begin1<=end1 && begin2<=end2){
		if (a[begin1] < a[begin2]) {
			tmp[i++] = a[begin1++];
		}			
		else {
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1) {
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2) {
		tmp[i++] = a[begin2++];
	}
	//把tmp陣列拷貝回到原來的陣列中
	i = left;
	while (i<=right)
	{
		a[i] = tmp[i];
		i++;
	}
}

歸并排序遞回實作

// 歸并排序遞回實作
void MergeSort(int* a, int n) {
	assert(a);
	//首先創建一個臨時陣列
	int* tmp = (int*)malloc(sizeof(int) * n);
	//空就直接錯
	assert(tmp);
	//子函式
	_MergeSort(a, 0, n - 1, tmp);
	//不用了就free掉
	free(tmp);
	//然后置空
	tmp = NULL;
}

非遞回寫法

2ⁿ個元素的陣列

我們看到上面好像沒啥問題，那是用為陣列元素個數真的太有好了，一直沒有落單的元素，好的不真實

隨便幾個元素的陣列

修正下標

越界情況討論

但是出現另一種惡心情況 重復拷貝

所以接下來我們需要解決index問題

我們修正到n-1，同樣也可以把陣列修不存在，讓他不進下面的回圈也就可以不會進行歸并

歸并排序非遞回實作 修正下標

// 歸并排序非遞回實作
void MergeSortNonR(int* a, int n) {
	assert(a);
	//首先創建一個臨時陣列
	int* tmp = (int*)malloc(sizeof(int) * n);
	//空就直接錯
	assert(tmp);
	int gap = 1;
	int i = 0;
	while (gap<n){
		for (i = 0; i < n; i += 2 * gap){
			//單組需要排序的區間
			//[i,i+gap-1]  [i+gap,i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i+gap, end2 = i + 2*gap - 1;
			//適用任何元素個數的核心部分
			//end1出界，[begin2,end2]不存在
			if (end1 >= n) {
				end1 = n - 1;
			}
			//[begin2,end2]不存在
			if (begin2 >= n) {
				begin2 = n ;
				end2 = n - 1;
			}
			//end2出界
			if (end2 >= n) {
				end2 = n - 1;
			}
			//printf("[%d,%d],[%d,%d]",begin1,end1,begin2,end2);
			重復拷貝基本是我們修正到同一個位置的原因
			我們條件斷點一下
			//if (begin1 == end1 && end1 == begin2 && begin2 == end2 && end2 == n-1)
			//{
			//	//隨便一個代碼來承接斷點，一句費代碼
			//	int a = 0;
			//}
			
			//tmp需要一個索引
			int index = i;
			while (begin1 <= end1 && begin2 <= end2){
				if (a[begin1] > a[begin2]) {
					tmp[index++] = a[begin2++];
				}
				else{
					tmp[index++] = a[begin1++];
				}
			}			
			//肯定還有一個沒跑完
			while (begin1 <= end1){
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2) {
				tmp[index++] = a[begin2++];
			}		
			//printf("       %d", index);
		}
		//printf("\n");
		
		//一行歸并完了再考回去
		for (i = 0; i < n; i++) {
			a[i] = tmp[i];
		}
		gap *= 2;
	}	
	//不用了就free掉
	free(tmp);
	//然后置空
	tmp = NULL;
}

歸一部分拷一部分

我們也可以像遞回那樣歸一半分拷貝一部分，就不需要修正了，因為修正要考慮很多邊界情況，有點繁瑣

歸并排序非遞回實作 歸一部分拷一部分

// 歸并排序非遞回實作
void MergeSortNonR(int* a, int n) {
	assert(a);
	//首先創建一個臨時陣列
	int* tmp = (int*)malloc(sizeof(int) * n);
	//空就直接錯
	assert(tmp);
	int gap = 1;
	int i = 0;
	while (gap<n){
		for (i = 0; i < n; i += 2 * gap){
			//單組需要排序的區間
			//[i,i+gap-1]  [i+gap,i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i+gap, end2 = i + 2*gap - 1;
			適用任何元素個數的核心部分
			end1出界，[begin2,end2]不存在
			//if (end1 >= n) {
			//	end1 = n - 1;
			//}
			[begin2,end2]不存在
			//if (begin2 >= n) {
			//	begin2 = n ;
			//	end2 = n - 1;
			//}
			end2出界
			//if (end2 >= n) {
			//	end2 = n - 1;
			//}
			//適用任何元素個數的核心部分
			//end1出界，[begin2,end2]不存在 都不需要歸并
			if (end1 >= n || begin2 >= n) {
				//直接跳，因為是在原陣列操作的不需要擔心最后一個沒考進去
				break;
			}
			//end2出界  需要歸并  就修正
			if (end2 >= n) {
				end2 = n - 1;
			}
			//printf("[%d,%d],[%d,%d]",begin1,end1,begin2,end2);
			重復拷貝基本是我們修正到同一個位置的原因
			我們條件斷點一下
			//if (begin1 == end1 && end1 == begin2 && begin2 == end2 && end2 == n-1)
			//{
			//	//隨便一個代碼來承接斷點，一句費代碼
			//	int a = 0;
			//}
			
			//tmp需要一個索引
			int index = i;
			while (begin1 <= end1 && begin2 <= end2){
				if (a[begin1] > a[begin2]) {
					tmp[index++] = a[begin2++];
				}
				else{
					tmp[index++] = a[begin1++];
				}
			}
			
			//肯定還有一個沒跑完
			while (begin1 <= end1){
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2) {
				tmp[index++] = a[begin2++];
			}		
			//歸一部分拷貝一部分
			int j = 0;
			for (j = i; j <= end2; j++) {
				a[j] = tmp[j];
			}
			//printf("       %d", index);
		}
		//printf("\n");
		
		一行歸并完了再考回去
		//for (i = 0; i < n; i++) {
		//	a[i] = tmp[i];
		//}
		gap *= 2;
	}	
	//不用了就free掉
	free(tmp);
	//然后置空
	tmp = NULL;
}

歸并排序的特性總結

1. 歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題，
2. 時間復雜度：O(N*logN)
3. 空間復雜度：O(N)
4. 穩定性：穩定

時間復雜度

時間復雜度:O(N*logN)

歸并排序方法就是把一組n個數的序列，折半分為兩個序列，然后再將這兩個序列再分，一直分下去，直到分為n個長度為1的序列，然后兩兩按大小歸并，如此反復，直到最后形成包含n個數的一個陣列，

歸并排序總時間=分解時間+子序列排好序時間+合并時間

無論每個序列有多少數都是折中分解，所以分解時間是個常數，可以忽略不計，

則：歸并排序總時間=子序列排好序時間+合并時間

測性能

1000 一千

10000 一萬 先拋棄選擇和冒泡

100000 十萬 再拋棄直接插入

1000000 一百萬

10000000 一千萬

排序

常見的排序演算法 擴展

計數排序 不進行資料的比較，而是統計資料出現的次數

思想：計數排序又稱為鴿巢原理，是對哈希直接定址法的變形應用， 操作步驟

1. 統計相同元素出現次數
2. 根據統計的結果將序列回收到原來的序列中

我們可以發現是不是很快，自我感覺一下，沒錯實際上的確是很快的，時間復雜度是高效到==O(N)==級別的，計數的本質是哈希，所謂的映射

這也會面臨一個很現實的問題，就是前面沒有時候數，后面1000的位置反而有數，咋處理

eg.1000 1100 1200 1300 1200 1400 1000 1500 1300 1200

我們也可以發現計數排序比較適合大小范圍集中的陣列

計數排序

// 計數排序
void CountSort(int* a, int n) {
	assert(a);
	int max = a[0], min = a[0];
	int i = 0;
	for (i = 0; i < n; i++) {
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	//范圍
	int range = max - min + 1;
	//開辟計數陣列
	int* count = (int*)malloc(sizeof(int) * range);	
	//沒開辟成功直接錯
	assert(count);
	//陣列全部初始化為零
	memset(count, 0, sizeof(int) * range);
	//統計次數
	for (i = 0; i < n; i++) {
		//相對映射加加
		count[a[i] - min]++;
	}
	//通過計數陣列的次數對原陣列進行排序
	int j = 0;
	for (i = 0; i < range; i++) {
		while (count[i]--)
			//相對映射要回到原陣列的資料+min
			a[j++] = i+min;
	}
	free(count);
	count = NULL;
}

計數排序的特性總結

1. 計數排序在資料范圍集中時，效率很高，但是適用范圍及場景有限，
2. 時間復雜度：O(MAX(N,范圍))
3. 空間復雜度：O(范圍)

測性能

1000 一千

10000 一萬

100000 十萬

1000000 一百萬

10000000 一千萬

排序總結

穩定性

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

再簡單一點：陣列中相同的值，在排序以后相對位置是否變化

可能會變的，就是不穩定

能保持不變，就是穩定

八大排序總結

排序方法	平均時間復雜度	最壞時間復雜度	最好時間復雜度	空間復雜度	穩定性
插入排序	O(N^2)	O(N^2)	O(N)	O(1)	穩定
希爾排序	O(N^1.3)	O(N^2)	O(N)	O(1)	不穩定
選擇排序	O(N^2)	O(N^2)	O(N^2)	O(1)	不穩定
堆排序	O(n*logN)	O(n*logN)	O(n*logN)	O(1)	不穩定
冒泡排序	O(N^2)	O(N^2)	O(N)	O(1)	穩定
快速排序	O(n*logN)	O(N^2)	O(n*logN)	最好O(logN)，最壞O(N)	不穩定
歸并排序	O(n*logN)	O(n*logN)	O(n*logN)	O(N)	穩定
計數排序	O(MAX(N,range))	O(MAX(N,range))	O(N)	O(range)	不穩定

代碼

Sort.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>

#define HEAP        1

// 排序實作的介面
// 列印陣列
extern void PrintArray(int* a, int n);
// 插入排序
extern void InsertSort(int* a, int n);
// 希爾排序
extern void ShellSort(int* a, int n);
//資料交換
extern void Swap(int* pa, int* pb);
// 選擇排序
extern void SelectSort(int* a, int n);
//向下調整
extern void AdjustDwon(int* a, int n, int parent);
// 堆排序
extern void HeapSort(int* a, int n);
// 冒泡排序
extern void BubbleSort(int* a, int n);
// 快速排序遞回實作
// 快速排序hoare版本
extern int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
extern int PartSort2(int* a, int left, int right);
// 快速排序前后指標法
extern int PartSort3(int* a, int left, int right);
extern void QuickSort(int* a, int left, int right);
// 快速排序 非遞回實作
extern void QuickSortNonR(int* a, int left, int right);
// 歸并排序遞回實作
extern void MergeSort(int* a, int n);
// 歸并排序非遞回實作
extern void MergeSortNonR(int* a, int n);
// 計數排序
extern void CountSort(int* a, int n);

Sort.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Sort.h"
#include"Stack.h"

// 列印陣列
void PrintArray(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}
// 插入排序
void InsertSort(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n - 1; i++)	{
		int end = i;
		int x = a[end+1];
		while (end >= 0) {
			//要插入的數比順序中的數小就準備挪位置
			if (a[end] > x) {
				a[end + 1] = a[end];
				end--;
			}
			else {
				//插入的數比順序中的要大就跳出
				break;
			}
		}
		//跳出來兩種情況
		//1.end == -1 的時候
		//2.break 的時候
		//把x給end前面一位
		a[end + 1] = x;
	}
}
// 希爾排序
void ShellSort(int* a, int n) {
	//分組
	int gap = n;
	//多次預排序（gap>1）+ 直接插入（gap == 1）
	while (gap>1){
		//gap /= 2;
		//除以三我們知道不一定會過1，所以我們+1讓他有一個必過1的條件
		gap = gap / 3 + 1;
		//單組多躺
		int i = 0;
		for (i = 0; i < n - gap; i++) {
		int end = i;
		int x = a[end + gap];
		while (end >= 0) {
			if (a[end] > x) {
				a[end + gap] = a[end];
				//步長是gap
				end -= gap;
			}
			else {
				break;
			}
		}
		a[end + gap] = x;
	}
	}	
}
//資料交換
void Swap(int* pa, int* pb) {
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
// 選擇排序
void SelectSort(int* a, int n) {
	int begin = 0;
	int end = n - 1;
	while (begin < end){
		//單趟
		//最大數，最小數的下標
		int mini = begin;//這邊假設是剛開始的下標
		int maxi = end;  //這邊假設是末尾的下標
		int i = 0;
		for (i = begin; i <= end; i++) {
			if (a[i] < a[mini])
				mini = i;
			if (a[i] > a[maxi])
				maxi = i;
		}
		//最小的放前面
		Swap(&a[begin], &a[mini]);
		
		if (begin == maxi)
			//如果最大數就是begin位置的，那么交換的時候最大數連帶著下標一起動
			maxi = mini;
		//最大的放后面
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}
//向下調整函式
void AdjustDown(int* a, int n, int parent)
{
	assert(a);
	//創建一個孩子變數，有兩個孩子就在這個上加1就行
	int child = parent * 2 + 1;
#if HEAP
	while (child < n)
	{
		//選大孩子
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		//大的孩子還大于父親就交換
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
#elif !HEAP
	while (child < n)
	{
		//選小孩子
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}
		//小的孩子還小于父親就交換
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
#endif // HEAP	
}
// 堆排序   我們之前講過升序建大堆
void HeapSort(int* a, int n) {
	//建堆時間復雜度O(N)
	//建大堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	//堆排序時間復雜度O(N*logN)
	while (end>0){
		//交換 把最大的放到后面
		Swap(&a[0], &a[end]);
		//在向下調整
		AdjustDown(a,end,0);
		end--;
	}
}
// 冒泡排序
void BubbleSort(int* a, int n) {
	//多躺
	int j = 0;	
	for (j = 0; j < n - 1; j++) {	
		//交換標記變數
		int flag = 0;
		//單趟
		int i = 0;
		for (i = 0; i < n - 1-j; i++) {			
			if (a[i] > a[i + 1]) {
				//交換標記改變
				flag = 1;
				Swap(&a[i], &a[i + 1]);
			}
		}
		//標記還是0就跳出
		if (!flag)
			break;
	}
}
//三數取中
int GetMinIndex(int* a, int left, int right) {
	//這樣可以防止 int 溢位
	int mid = left + (right - left) / 2;
	if (a[left] < a[mid]) {
		if (a[mid] < a[right])
			return mid;
		else if (a[left] > a[right])
			return left;
		else
			return right;
	}
	else //a[left] >= a[mid]
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[left] < a[right])
			return left;
		else
			return right;
	}
}
// 快速排序hoare版本 單趟排序
//最左邊做key  [left,right]  我們這里給區間
int PartSort1(int* a, int left, int right) {
	//三數取中
	int mini = GetMinIndex(a, left, right);
	//把中間的數放到最左邊，交換即可
	Swap(&a[mini], &a[left]);
	//還是最左邊為keyi
	int keyi = left;
	//左右相遇就停止
	while (left < right)
	{
		//最左邊為key，那么最右邊就先動
		//找小于key的
		while (left < right && a[right] >= a[keyi]) {
			right--;
		}
		//然后再動右邊的
		//找大于key的
		while (left < right && a[left] <= a[keyi]) {
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[right]);
	//回傳正確位置后的keyi
	return left;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right) {
	assert(a);
	//三數取中
	int mini = GetMinIndex(a, left, right);
	//把中間的數放到最左邊，交換即可
	Swap(&a[mini], &a[left]);
	//先把Key存下來
	int Key = a[left];
	//挖坑
	int pit = left;
	while (left<right){
		//右邊找小
		while (left < right && a[right] >= Key) {
			right--;
		}
		//找到后把資料扔到坑里面去
		Swap(&a[right],&a[pit]);
		//自己就變成新的坑
		pit = right;
		//左邊找大
		while (left < right && a[left] <= Key) {
			left++;
		}
		//找到后把資料扔到坑里面去
		Swap(&a[left], &a[pit]);
		//自己就變成新的坑
		pit = left;
	}
	//出來后把Key放到坑里面去
	a[pit] = Key;
	return pit;
}

// 快速排序前后指標法
int PartSort3(int* a, int left, int right) {
	assert(a);	
	//三數取中
	int mini = GetMinIndex(a, left, right);
	//把中間的數放到最左邊，交換即可
	Swap(&a[mini], &a[left]);
	//把keyi記下來
	int keyi = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right){
		比Key小就跳出
		//while (cur <= right && a[cur] >= a[keyi]) {
		//	cur++;
		//}
		//if (cur <= right) {
		//	//跳出來prev++
		//	prev++;
		//	//交換
		//	Swap(&a[prev], &a[cur]);
		//	//交換完后cur也++
		//	cur++;
		//}		
		if(a[cur] < a[keyi])
			Swap(&a[prev++], &a[cur]);
		cur++;
	}
	//跳出來說明交換a[prev]和Key
	Swap(&a[prev],&a[keyi]);
	return prev;
}


// 快速排序  小區間優化
void QuickSort(int* a, int left, int right) {
	if (left >= right)
		return;
	if (right - left + 1 < 10)//10以內的數插入
	{
		InsertSort(a + left, right - left + 1);
	}
	else
	{
		int keyi = PartSort3(a, left, right);
		//[left,keyi-1] keyi [keyi+1,right]
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}	
}
// 快速排序 非遞回實作
void QuickSortNonR(int* a, int left, int right) {
	//建堆疊
	ST st;
	//初始化堆疊
	StackInit(&st);
	//left進堆疊
	StackPush(&st, left);
	//right進堆疊
	StackPush(&st, right);
	//空堆疊跳出 
	while (!StackEmpty(&st))
	{
		//先取尾
		int end = StackTop(&st);
		//pop掉
		StackPop(&st);
		//再取頭
		int start = StackTop(&st);
		//再pop掉
		StackPop(&st);

		//然后單趟排序找到keyi
		int keyi = PartSort3(a,start,end);
		//[start,keyi-1] keyi [keyi+1,end]
		if (keyi + 1 < end)//表示分割開來的區間大于1
		{
			//因為我們先取尾，所以問先入頭
			StackPush(&st, keyi + 1);
			//再入尾
			StackPush(&st, end);
		}
		if (keyi - 1 > start)//表示分割開來的區間大于1
		{
			//因為我們先取尾，所以問先入頭
			StackPush(&st, start);
			//再入尾
			StackPush(&st, keyi - 1);
		}
	}
	//與初始化聯動的堆疊銷毀
	StackDestroy(&st);
}



// 歸并排序遞回子函式
void _MergeSort(int* a, int left, int right, int* tmp){
	//左大于右說明是空陣列，空陣列就跳
	//左等于右就是我們要的單體有序
	if (left >= right)
		return;
	//防溢位寫法
	int mid = left + (right - left) / 2;
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1,right, tmp);
	//
	int begin1 = left;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = right;
	int i = left;
	//跑空一組就直接跳
	while (begin1<=end1 && begin2<=end2){
		if (a[begin1] < a[begin2]) {
			tmp[i++] = a[begin1++];
		}			
		else {
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1) {
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2) {
		tmp[i++] = a[begin2++];
	}
	//把tmp陣列拷貝回到原來的陣列中
	i = left;
	while (i<=right)
	{
		a[i] = tmp[i];
		i++;
	}
}

// 歸并排序遞回實作
void MergeSort(int* a, int n) {
	assert(a);
	//首先創建一個臨時陣列
	int* tmp = (int*)malloc(sizeof(int) * n);
	//空就直接錯
	assert(tmp);
	//子函式
	_MergeSort(a, 0, n - 1, tmp);
	//不用了就free掉
	free(tmp);
	//然后置空
	tmp = NULL;
}
// 歸并排序非遞回實作
void MergeSortNonR(int* a, int n) {
	assert(a);
	//首先創建一個臨時陣列
	int* tmp = (int*)malloc(sizeof(int) * n);
	//空就直接錯
	assert(tmp);
	int gap = 1;
	int i = 0;
	while (gap<n){
		for (i = 0; i < n; i += 2 * gap){
			//單組需要排序的區間
			//[i,i+gap-1]  [i+gap,i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i+gap, end2 = i + 2*gap - 1;
			適用任何元素個數的核心部分
			end1出界，[begin2,end2]不存在
			//if (end1 >= n) {
			//	end1 = n - 1;
			//}
			[begin2,end2]不存在
			//if (begin2 >= n) {
			//	begin2 = n ;
			//	end2 = n - 1;
			//}
			end2出界
			//if (end2 >= n) {
			//	end2 = n - 1;
			//}
			//適用任何元素個數的核心部分
			//end1出界，[begin2,end2]不存在 都不需要歸并
			if (end1 >= n || begin2 >= n) {
				//直接跳，因為是在原陣列操作的不需要擔心最后一個沒考進去
				break;
			}
			//end2出界  需要歸并  就修正
			if (end2 >= n) {
				end2 = n - 1;
			}
			//printf("[%d,%d],[%d,%d]",begin1,end1,begin2,end2);
			重復拷貝基本是我們修正到同一個位置的原因
			我們條件斷點一下
			//if (begin1 == end1 && end1 == begin2 && begin2 == end2 && end2 == n-1)
			//{
			//	//隨便一個代碼來承接斷點，一句費代碼
			//	int a = 0;
			//}
			
			//tmp需要一個索引
			int index = i;
			while (begin1 <= end1 && begin2 <= end2){
				if (a[begin1] > a[begin2]) {
					tmp[index++] = a[begin2++];
				}
				else{
					tmp[index++] = a[begin1++];
				}
			}
			
			//肯定還有一個沒跑完
			while (begin1 <= end1){
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2) {
				tmp[index++] = a[begin2++];
			}		
			//歸一部分拷貝一部分
			int j = 0;
			for (j = i; j <= end2; j++) {
				a[j] = tmp[j];
			}
			//printf("       %d", index);
		}
		//printf("\n");
		
		一行歸并完了再考回去
		//for (i = 0; i < n; i++) {
		//	a[i] = tmp[i];
		//}
		gap *= 2;
	}	
	//不用了就free掉
	free(tmp);
	//然后置空
	tmp = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Sort.h"

// 測驗排序的性能對比
void TestOP()
{
	//設定隨機起點
	srand(time(NULL));
	//將要創建的陣列大小
	const int N = 10000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	int* a8 = (int*)malloc(sizeof(int) * N);
	int* a9 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		//保證兩個陣列是一樣的
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
		a8[i] = a1[i];
		a9[i] = a1[i];
	}
	int begin1 = clock();//開始時間
	//InsertSort(a1, N);
	int end1 = clock();  //結束時間
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	//SelectSort(a3, N);
	int end3 = clock();
	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();
	int begin5 = clock();
	//BubbleSort(a5, N);
	int end5 = clock();
	int begin6 = clock();
	QuickSort(a6, 0, N - 1);
	int end6 = clock();
	int begin7 = clock();
	QuickSortNonR(a7, 0, N - 1);
	int end7 = clock();
	int begin8 = clock();
	MergeSort(a8, N);
	int end8 = clock();
	int begin9 = clock();
	MergeSort(a9, N);
	int end9 = clock();
	printf("InsertSort:%d\n", end1 - begin1);//結束時間減去開始時間 
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("BubbleSort:%d\n", end5 - begin5);
	printf("QuickSort:%d\n", end6 - begin6);
	printf("QuickSortNonR:%d\n", end7 - begin7);
	printf("MergeSort:%d\n", end8 - begin8);
	printf("MergeSortNonR:%d\n", end9 - begin9);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
	free(a8);
	free(a9);
}
//測驗插入排序
void TestInsertSort() {
	int a[] = { 1,5,3,7,0,9 };
	InsertSort(a, sizeof(a) / sizeof(a[0]));	
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//測驗希爾排序
void TestShellSort() {
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };
	ShellSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//測驗選擇排序
void TestSelectSort() {
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };
	SelectSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//測驗堆排序
void TestHeapSort() {
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//測驗冒泡排序
void TestBubbleSort() {
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };
	BubbleSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//測驗單趟排序
void TestPartSort1() {
	int a[] = { 5,5,5,5,5,5,5,5,5,5 };
	PartSort1(a,0 ,sizeof(a) / sizeof(a[0])-1);
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//測驗快速排序
void TestQuickSort() {
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };
	QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1);
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//測驗快速排序--非遞回
void TestQuickSortNonR() {
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };
	QuickSortNonR(a, 0, sizeof(a) / sizeof(a[0]) - 1);
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//測驗歸并排序--遞回
void TestMergeSort() {
	int a[] = { 10,6,7,1,3,9,4,2 };
	MergeSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//測驗歸并排序--非遞回
void TestMergeSortNonR() {
	int a[] = {  10,6,7,1,3,9,4,2,5 };
	MergeSortNonR(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
int main(){
	//TestInsertSort();
	//TestShellSort();
	//TestSelectSort();
	//TestHeapSort();
	//TestBubbleSort();
	//TestPartSort1();
	//TestQuickSort();
	//TestQuickSortNonR();
	//TestMergeSort();
	//TestMergeSortNonR();
	TestOP();
	return 0;
}