目錄

常見的八種排序

直接插入排序

希爾排序

直接選擇排序

堆排序

冒泡排序?

快速排序

hoare版本?

挖坑法

前后指針版

快速排序代碼

歸并排序?

計數排序

?

常見的八種排序

?直接插入排序

?先，我們將數組中的數據分為兩個區間，已排序區間和未排序區間。初始已排序區間只有?個元素，就是數組的第?個元素。插?算法的核?思想是取未排序區間中的元素，在已排序區間中找到合適的插?位置將其插?，并保證已排序區間數據?直有序。重復這個過程，直到未排序區間中元素為空，算法結束

如圖所示，要排序的數據是4，5，6，1，3，2，其中左側為已排序區間，右側是未排序區間。

?插?排序包含兩種操作，?種是元素的?較，?種是元素的移動。比如我們需要將?個數據3插?
到已排序區間[1,4,5,6]時，需要拿3與已排序區間的元素6,5,4,1依次?較??，找到合適的插?位置。找到插?點之后，我們還需要將插?點之后的元素順序往后移動?位，這樣才能騰出位置給元素3插?。比如3和6比較，此時就可以將3和6的位置進行交換，依次類推，3再和5交換，3再和4交換，當3和1比較發現3比1大就不用再交換了，完成了3的插入過程了

C代碼

?輸出結果

?時間復雜度O(N^2),空間復雜度O(1）

穩定性：穩定

穩定性的說明

?圖中紅色的5在排完序后依舊在藍色的5后面，這就是穩定的表現

希爾排序

?希爾排序可以看成是對直接插入排序的優化：我們可以看到直接插入排序的缺點即對一個降序的數組進行升序那么時間復雜度為O(N^2)，但是對該數組進行降序那么時間復雜度就為O(N)了，此時大家會想該數組都是降序的了，你再對其降序圖啥呢？這里想闡述的觀點是如果將該數組變為

接近有序的狀態那么使用直接插入排序其時間復雜度不就降下來了嗎，希爾排序就是用了這個思想

對直接插入排序進行了優化?。?！

?

?執行結果

?時間復雜度O(N^logN),空間復雜度O(1)

穩定性：不穩定

直接選擇排序

?基本思想：一次挑一個數據：每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完

?排序結果：

?堆排序

?注意：使用堆排序首先需要理解什么是堆，大堆與小堆的區別，這里就不對堆的概念進行說明

堆排序(Heapsort)是指利用堆這種數據結構所設計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數據。需要注意的是排升序要建大堆，排降序建小堆。

將數組key=[20,17,4,16,5,3]建立一個大堆，對該數組排升序

?

執行結果：

?上面代碼中數組arr已經是個大堆了，這里只是對堆排序的過程進行了說明，

如何將一個普通的數組建立成一個大堆這里就不作講述

1. 時間復雜度：O(N*logN)
2. 空間復雜度：O(1)
3. 穩定性：不穩定

冒泡排序?

?冒泡排序只會操作相鄰的兩個數據。每次冒泡操作都會對相鄰的兩個元素進??較，看是否滿???關系要求。如果不滿?就讓它倆互換。圖中相鄰的元素如果左邊的元素大于右邊的元素，那么就進行交換，即相鄰的兩個元素右邊總是較大的。

?

1. 時間復雜度：O(N^2)
2. 空間復雜度：O(1)
3. 穩定性：穩定

?快速排序

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

將區間按照基準值劃分為左右兩半部分的常見方式有：

1. hoare版本
2. 挖坑法
3. 前后指針版本

?

1. 三數取中法選key（可以保證不會出現最壞的情況，而且當數據有序的時候就是最好的情況）
2. 遞歸到小的子區間時，可以考慮使用插入排序

//快排，時間復雜度，最好的情況O(N*log2(N)),最壞O（N^2)//優化方法1：三數取中，避免快排出現最壞的情況int GetMidIndex(int* a, int left, int right){	int mid = (left + right) >> 1;//移位的效率比除以2的效率要高一點	// left  mid  right	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版本?

?

int PartSort1(int* a, int left, int right)//排序一趟就返回相遇點{	int midIndex = GetMidIndex(a, left, right);//使用三數取中	Swap(&a[left], &a[midIndex]);//將三數取中后的結果與最左邊的值進行交換	int 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[keyi], &a[left]);	return left;//返回相遇的位置，也就是keyi}

挖坑法

?

int PartSort2(int* a, int left, int right){	int midIndex = GetMidIndex(a, left, right);//使用三數取中	Swap(&a[left], &a[midIndex]);//將三數取中后的結果與最左邊的值進行交換	int key = a[left];//將最左邊的值給key,然后將最左邊的視為坑（沒有數據的意思）	while (left < right)	{		// 找小		while (left < right && a[right] >= key)		{			--right;		}		// 放到左邊的坑位中,右邊就形成新的坑		a[left] = a[right];		// 找大		while (left < right && a[left] <= key)		{			++left;		}		// 放到右邊的坑位中，左邊就形成新的坑		a[right] = a[left];	}	a[left] = key;//最后相遇點一定是坑，將key放到坑中	return left;//返回相遇點，也就是key值所在的位置}

前后指針版

?

int PartSort3(int* a, int left, int right){	int midIndex = GetMidIndex(a, left, right);	Swap(&a[left], &a[midIndex]);	int keyi = left;	int prev = left, cur = left + 1;	while (cur <= right)	{		if (a[cur] < a[keyi] && ++prev != cur)//cur找比keyi小的數		{			Swap(&a[cur], &a[prev]);		}		++cur;	}	Swap(&a[keyi], &a[prev]);	return prev;//最后返回prev的位置，也就是keyi，這里的keyi表示的是下標}

快速排序代碼

?上面的都是各版本進行單趟排序的代碼

void QuickSort(int* a, int begin, int end)//（用的是hoare法）{	if (begin >= end)//[begin,end]區間為0或者區間不存在則返回		return;	// 1、如果這個子區間是數據較多，繼續選key單趟，分割子區間分治遞歸	// 2、如果這個子區間是數據較小，再去分治遞歸不太劃算	//此時越往后遞歸，子區間就越多，每個子區間的數據就越少，每個子區間都要遞歸就不劃算，	//可以在后面進行插入排序，因為此時每個子區間是接近有序的，接近于希爾排序了	if (end - begin > 0)//小區間優化的效果沒那么明顯，如果對相應數據量級進行針對性的調		//往往數據量越大，比如將20換成1000效果就明顯了，20是官方給的，官方不敢給大了	{		int keyi = PartSort1(a, begin, end);		//int keyi = PartSort2(a, begin, end);		//int keyi = PartSort3(a, begin, end);		// [begin, keyi-1] keyi [keyi+1, end]		QuickSort(a, begin, keyi - 1);//遞歸		QuickSort(a, keyi + 1, end);//遞歸	}	else	{		InsertSort(a + begin, end - begin + 1);		//HeapSort(a + begin, end - begin + 1);也可以換成其如堆排，希爾排序效果會更好	}}

1. 時間復雜度：O(N*logN)
2. 空間復雜度：O(logN)
3. 穩定性：不穩定

歸并排序?

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

?

void _MergeSort(int* a, int left, int right, int* tmp){	if (left >= right)		return;	int mid = (left + right) >> 1;	// [left, mid][mid+1,right]	_MergeSort(a, left, mid, tmp);//先遞歸進行分治	_MergeSort(a, mid + 1, right, tmp);	// 兩段有序子區間歸并tmp,并拷貝回去	int begin1 = left, end1 = mid;	int begin2 = mid + 1, 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++];	// 歸并完成以后，拷貝回到原數組	for (int j = left; j <= right; ++j)		a[j] = tmp[j];}void MergeSort(int* a, int n){	int* tmp = (int*)malloc(sizeof(int)*n);//創建臨時數組	if (tmp == NULL)	{		printf("malloc fail/n");		exit(-1);	}	_MergeSort(a, 0, n - 1, tmp);	free(tmp);}

1. 時間復雜度：O(N*logN)
2. 空間復雜度：O(N)
3. 穩定性：穩定

?計數排序

?

//計數排序void CountSort(int* a, int n){	int min = a[0];//記錄數組中的最小值	int max = a[0];//記錄數組中的最大值	for (int i = 0; i < n; i++)	{		if (a[i] < min)			min = a[i];		if (a[i] > max)			max = a[i];	}	int range = max - min + 1;//min和max之間的自然數個數（包括min和max本身）	int* count = (int*)calloc(range, sizeof(int));//開辟可儲存range個整型的內存空間，并將內存空間置0	if (count == NULL)	{		printf("malloc fail/n");		exit(-1);	}	//統計相同元素出現次數（相對映射）	for (int i = 0; i < n; i++)	{		count[a[i] - min]++;	}	int i = 0;	//根據統計結果將序列回收到原來的序列中	for (int j = 0; j < range; j++)	{		while (count[j]--)		{			a[i++] = j + min;		}	}	free(count);//釋放空間}

1. 時間復雜度：O(MAX(N+范圍))
2. 空間復雜度：O(范圍)
3. 穩定性：穩定