目錄

常見的八種排序

直接插入排序

希爾排序

直接選擇排序

堆排序

冒泡排序?

快速排序

hoare版本?

挖坑法

前后指針版

快速排序代碼

歸并排序?

計數(shù)排序

?

常見的八種排序

?直接插入排序

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

如圖所示，要排序的數(shù)據(jù)是4，5，6，1，3，2，其中左側(cè)為已排序區(qū)間，右側(cè)是未排序區(qū)間。

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

C代碼

?輸出結(jié)果

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

穩(wěn)定性：穩(wěn)定

穩(wěn)定性的說明

?圖中紅色的5在排完序后依舊在藍(lán)色的5后面，這就是穩(wěn)定的表現(xiàn)

希爾排序

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

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

對直接插入排序進(jìn)行了優(yōu)化！！！

?

?執(zhí)行結(jié)果

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

穩(wěn)定性：不穩(wěn)定

直接選擇排序

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

?排序結(jié)果：

?堆排序

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

堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種。它是通過堆來進(jìn)行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。

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

?

執(zhí)行結(jié)果：

?上面代碼中數(shù)組arr已經(jīng)是個大堆了，這里只是對堆排序的過程進(jìn)行了說明，

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

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

冒泡排序?

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

?

1. 時間復(fù)雜度：O(N^2)
2. 空間復(fù)雜度：O(1)
3. 穩(wěn)定性：穩(wěn)定

?快速排序

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

將區(qū)間按照基準(zhǔn)值劃分為左右兩半部分的常見方式有：

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

?

1. 三數(shù)取中法選key（可以保證不會出現(xiàn)最壞的情況，而且當(dāng)數(shù)據(jù)有序的時候就是最好的情況）
2. 遞歸到小的子區(qū)間時，可以考慮使用插入排序

//快排，時間復(fù)雜度，最好的情況O(N*log2(N)),最壞O（N^2)//優(yōu)化方法1：三數(shù)取中，避免快排出現(xiàn)最壞的情況int GetMidIndex(int* a, int left, int right){	int mid = (left + right) >> 1;//移位的效率比除以2的效率要高一點(diǎn)	// 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)//排序一趟就返回相遇點(diǎn){	int midIndex = GetMidIndex(a, left, right);//使用三數(shù)取中	Swap(&a[left], &a[midIndex]);//將三數(shù)取中后的結(jié)果與最左邊的值進(jìn)行交換	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);//使用三數(shù)取中	Swap(&a[left], &a[midIndex]);//將三數(shù)取中后的結(jié)果與最左邊的值進(jìn)行交換	int key = a[left];//將最左邊的值給key,然后將最左邊的視為坑（沒有數(shù)據(jù)的意思）	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;//最后相遇點(diǎn)一定是坑，將key放到坑中	return left;//返回相遇點(diǎn)，也就是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小的數(shù)		{			Swap(&a[cur], &a[prev]);		}		++cur;	}	Swap(&a[keyi], &a[prev]);	return prev;//最后返回prev的位置，也就是keyi，這里的keyi表示的是下標(biāo)}

快速排序代碼

?上面的都是各版本進(jìn)行單趟排序的代碼

void QuickSort(int* a, int begin, int end)//（用的是hoare法）{	if (begin >= end)//[begin,end]區(qū)間為0或者區(qū)間不存在則返回		return;	// 1、如果這個子區(qū)間是數(shù)據(jù)較多，繼續(xù)選key單趟，分割子區(qū)間分治遞歸	// 2、如果這個子區(qū)間是數(shù)據(jù)較小，再去分治遞歸不太劃算	//此時越往后遞歸，子區(qū)間就越多，每個子區(qū)間的數(shù)據(jù)就越少，每個子區(qū)間都要遞歸就不劃算，	//可以在后面進(jìn)行插入排序，因?yàn)榇藭r每個子區(qū)間是接近有序的，接近于希爾排序了	if (end - begin > 0)//小區(qū)間優(yōu)化的效果沒那么明顯，如果對相應(yīng)數(shù)據(jù)量級進(jìn)行針對性的調(diào)		//往往數(shù)據(jù)量越大，比如將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. 時間復(fù)雜度：O(N*logN)
2. 空間復(fù)雜度：O(logN)
3. 穩(wěn)定性：不穩(wěn)定

歸并排序?

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

?

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

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

?計數(shù)排序

?

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

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