“田家少閑月，五月人倍忙”“夜來南風(fēng)起，小麥覆隴黃”

C語言朱武大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)專欄

C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)希爾排序算法

C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)堆排序圖文示例

C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹遞歸

快速排序

快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法。所以快速排序有種方法是以他的名字命名的。相比70年前的祖師爺級(jí)的 大佬 來說，今天我們學(xué)習(xí)快速排序的成本已經(jīng)非常低了。今天的我們的是站在巨人的肩膀上學(xué)習(xí)快速排序。

快速排序有三種方法實(shí)現(xiàn)，我們 都 需要掌握。

一、經(jīng)典1962年Hoare法

讓我們來看看1962年祖師爺發(fā)明的快排吧。

什么是快速排序？給你以下代碼，請(qǐng)你完善快速排序，你將怎么完善？

快速排序：顧名思義，它比較快，整體而言適合各種場景下的排序。缺陷相較于其他排序小。且大部分 程序語言 排序的庫函數(shù) 的 源代碼都是由快速排序?qū)崿F(xiàn)的

void QuickSort(int* a, int left, int right)
{
	//請(qǐng)你完善以下代碼
}
int main()
{
	int arr[] = {6,1,2,7,9,3,4,5,10,8};
	int sz = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, sz-1);
	return 0;
}

具體實(shí)現(xiàn)：

Hoare法和二叉樹的**前序遍歷(根 左子樹 右子樹)**簡直一模一樣。

整體思路：

1.先進(jìn)行一趟排序。

2.進(jìn)行左半?yún)^(qū)間(左子樹)遞歸。

3.進(jìn)行右半?yún)^(qū)間(右子樹)遞歸。

1.單趟排序

所有的排序的思想：就是先考慮單趟的排序，再合成n躺排序。這是毋庸置疑的，因?yàn)檫@樣的思想很自然。

對(duì)于單趟排序，也有一個(gè)思路?？梢哉f算是規(guī)定吧，這是祖師爺Hoare的規(guī)定。

為了好理解思路，以下思路是整體上的思路，寫出來的程序還是有bug的。具體細(xì)節(jié)需要后期修改。

一定要按照規(guī)定走哦，不要問那么多為什么。按照規(guī)定走你就知道為什么要這么做了?？傮w思路規(guī)定：

1.設(shè)置一個(gè)基準(zhǔn)值key，key一般為左邊第一個(gè)數(shù)的下標(biāo)。定義左指針left和有指針right分別指向第一個(gè)和最后一個(gè)。

2.先讓右邊的right指針往左走，一直找比key所指向小的數(shù)，找到后就停下。

3.緊接著讓left指針往右走，一直找比key所指向大的數(shù)，找到后就停下。

4.如果第2步的right和第3步left都找到了，則交換swap兩者的值。然后繼續(xù)循環(huán)2和3步，直到left >= right為止。

5.此時(shí)left = right, 交換left和right相遇的位置的值 與 key位置上的值。

此時(shí)，Hoare 的單趟排序完成。產(chǎn)生的效果是key作為分割線，把大小分割開了，比key所指向值小的在key左邊，比key所指向值大的在key右邊。

2.遞歸左半?yún)^(qū)間和右半?yún)^(qū)間

對(duì)于單趟來說。

單趟排完之后，key已經(jīng)放在正確的位置了。

如果左邊有序，右邊有序，那么我們整體就有序了。

那左邊和右邊如何有序呢？

解釋：分治解決子問題。相當(dāng)于二叉樹。

一趟排序完成后，再對(duì)左半?yún)^(qū)間進(jìn)行單趟排序，一直遞歸到什么時(shí)候結(jié)束呢？

解釋：遞歸到左半?yún)^(qū)間只有一個(gè)值的時(shí)候，或者為空的時(shí)候遞歸結(jié)束。

這個(gè)過程適合用 畫遞歸圖 來查看。

由于數(shù)據(jù)是10個(gè)數(shù)，遞歸圖龐大。所以此處省略。下面雙指針法有具體遞歸圖。

3.代碼實(shí)現(xiàn)

具體代碼實(shí)現(xiàn)和你想的總是那么不同。因?yàn)樘厥馇闆r確實(shí)是存在，且還是那么離譜。

我認(rèn)為這個(gè)題難在了邊界問題，邊界問題要時(shí)刻注意！。

特殊情況1：當(dāng)排以下數(shù)據(jù)時(shí)，我只是把6改了，這樣會(huì)導(dǎo)致right和left直接不走了。

{6,1,2,7,9,3,4,5,10,6}

特殊情況2：當(dāng)排以下數(shù)據(jù)時(shí)，會(huì)發(fā)生left找不到最大的值導(dǎo)致越界。

{5,4,3,2,1}

改動(dòng)如下。

//快速排序Hoare
int PartSort(int* a, int left,int right)
{
	int key = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[key])
		{
			--right;
		}
		while (left < right && a[left] <= a[key])
		{
			++left;
		}
		swap(&a[left], &a[right]);
	}
	swap(&a[left], &a[key]);
	return left;
}
void QuickSort(int* a, int left, int right)
{
	//當(dāng)有個(gè)區(qū)間為空的時(shí)候right-left會(huì)小于0。
	if (right <= left)
		return;
	int div = PartSort(a, left, right);
	QuickSort(a, left, div-1);
	QuickSort(a, div+1, right);
}
int main()
{
	int arr[] = {6,1,2,7,9,3,4,5,10,8};
	int sz = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, sz-1);
	return 0;
}

二、填坑法(了解)

和Hoare法思想類似，大差不差，沒什么區(qū)別。相比Hoare法較好理解。因?yàn)橥诳犹羁铀枷牒苌鷦?dòng)形象，所以較好理解。

1.單趟思路

單趟思路：

1.先保存key的值。讓左邊的key做坑(pit)，讓右邊找比key小的，然后填到坑中。

2.然后讓那個(gè)小的做坑，再讓左邊找比key大的，找到后填到坑中。依次循環(huán)，直到right和left相遇。

3.相遇后，把key的值填到相遇的位置。

這時(shí)，單趟循環(huán)結(jié)束。

2.代碼實(shí)現(xiàn)

和Hoare法相似，只是少了交換的步驟。注意：要事先把key的值保存下來。

int PartSort(int* a, int left, int right)
{
	int keyval = a[left];
	int pit = left;
	while (left < right)
	{
		while (left < right && a[right] >= keyval)
		{
			right--;
		}
		a[pit] = a[right];
		pit = right;
		while (left < right && a[left] <= keyval)
		{
			left++;
		}
		a[pit] = a[left];
		pit = left;
	}
	a[pit] = keyval;
	return left;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int div = PartSort(a, left, right);
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, sz-1);
	return 0;
}

三、雙指針法(最佳方法)

1.單趟排序

和以上兩種方法的不同之處只有單趟排序，也就是PartSort函數(shù)的部分.

優(yōu)點(diǎn)：有了雙指針的優(yōu)化，不需要考慮 邊界問題！寫代碼不易出錯(cuò)。

代碼好寫，不好理解。代碼極為簡單，只需五行。

雙指針法也稱快慢指針法，兩個(gè)指針一前一后

2.具體思路

對(duì)于排6,3,2,1,5,4的升序來說。

思路：讓cur找比key指向的值小的，找到后，++prev，交換prev和cur位置的值。若cur比key指向的值大，則不交換。

prev和cur的關(guān)系：

1.cur還沒遇到比key大的值時(shí)，prev緊跟著cur，一前一后。

2.cur遇到比key大的，prev和cur之間的一段都是最大的值

第一趟排序后的結(jié)果。這時(shí)候div為基準(zhǔn)值。將左右子樹分隔開。

全部排完序后的二叉樹圖。

3.代碼遞歸圖

紅色線代表遞歸，綠色線代表返回。

4.代碼實(shí)現(xiàn)

#include <stdio.h>
void Swap(int* x, int* y)
{
	int t = 0;
	t = *x;
	*x = *y;
	*y = t;
}
int PartSort(int* a, int left, int right)
{
	int key = left;
	int prev = left;
	int cur = left + 1;
	//推薦寫法一，較好理解
	while (cur <= right)
	{
		if (a[cur] < a[key])
		{
			++prev;
			Swap(&a[cur], &a[prev]);
		}
		++cur;
	}
	//寫法二。比較妙，不好理解
	//while (cur <= right)
	//{
	//	if (a[cur] < a[key] && a[++prev] != a[cur])
	//	{
	//		Swap(&a[cur], &a[prev]);
	//	}
	//	++cur;
	//}
	Swap(&a[prev], &a[key]);
	return prev;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int div = PartSort(a, left, right);
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
}
int main()
{
	int arr[] = {6,3,2,1,5,4};
	int sz = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, sz-1);
	return 0;
}

到這里快速排序還沒有完，因?yàn)樗嬖谌毕?。還需繼續(xù)優(yōu)化。請(qǐng)往下看

四、三數(shù)取中優(yōu)化(最終方案)

以上三種方法的時(shí)間復(fù)雜度

最好情況：是O(N*Log2N)。

最壞情況：也就是在數(shù)據(jù)有序的情況下，就退化為了冒泡排序 O(N2)

當(dāng)給你一組上萬個(gè)數(shù)據(jù)測試時(shí)，會(huì)發(fā)生超時(shí)現(xiàn)象。

例如LeetCode912. 排序數(shù)組

快排竟然超時(shí)了，這時(shí)候用三數(shù)取中來解決此問題。

1.三數(shù)取中

三數(shù)取中的含義：取三個(gè)數(shù)中間不是最大也不是最小的那個(gè)。哪三個(gè)數(shù)？第一個(gè)，最后一個(gè)，和中間那個(gè)。例如排以下數(shù)據(jù)時(shí)。

9 8 7 6 5 4 3 2 1 0

思路：

默認(rèn)key選最左邊的數(shù)。

1.三個(gè)數(shù)取第一個(gè) 9 和第二個(gè) 1 和中間的 5

2.選出不是最大也不是最小的那個(gè)，也就是5。

3.將5和key交換位置。也就是和最左邊的數(shù)交換。

這樣做可以打破單邊樹形狀，可以使之變?yōu)槎帧Ｒ驗(yàn)檫@時(shí)候5做了key，key的左邊是比5小的，

key的右邊是比key大的。

二分后的時(shí)間復(fù)雜度還是N*LogN

注意：三數(shù)取中仍然無法完全解決

在某種特殊情況序列下時(shí)間復(fù)雜度變?yōu)镺(n2)的情況

2.代碼實(shí)現(xiàn)(最終代碼)

int GetMidIndex(int* a, int left, int right)
{
	//防溢出寫法
	//int mid = left + (right - left) / 2;
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
int PartSort(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[midi], &a[left]);
	int key = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key])
		{
			++prev;
			Swap(&a[cur], &a[prev]);
		}
		++cur;
	}
	Swap(&a[prev], &a[key]);
	return prev;
}
void QuickSort(int* a, int left, int right)
{
	if (right <= left)
		return;
	int div = PartSort(a, left, right);
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, sz-1);
	return 0;
}

五、時(shí)間復(fù)雜度(重點(diǎn))

結(jié)論大家都會(huì)，是N*LogN。怎么算出來的呢？

1.最好情況下

在最好的情況下：每次選key剛好能平分這組數(shù)據(jù)，一直都是二分，構(gòu)成了滿二叉樹。

1.對(duì)于單趟排序的一層遞歸，不管是哪種方法，left和right每次都遍歷了一遍數(shù)組，時(shí)間復(fù)雜度為N。

2.因?yàn)闈M二叉樹的高度為Log2N，所以遞歸深度(深度不等于次數(shù))也為Log2N，所以遞歸Log2N層就是(N *Log2N).

3.綜上所述，快排最好情況下時(shí)間復(fù)雜度為O(N * LogN).

2.最壞情況下

最壞情況下，每次選key都是最大或者最小的那個(gè)元素，這使得每次劃分所得的子表中一個(gè)為空表，另一個(gè)表的長度為原表的長度-1.

這樣，長度為n的數(shù)據(jù)表的快速排序需要經(jīng)過n趟劃分，使得整個(gè)排序算法退化為冒泡排序，時(shí)間復(fù)雜度為N2

如圖是給9 8 7 6 5 4 3 2 1排升序的例子。

每次選最左邊的為key。

3.空間復(fù)雜度

在空間上來看，盡管快排只需要一個(gè)元素的輔助空間。

但是快排需要一個(gè)?？臻g來實(shí)現(xiàn)遞歸

最好情況下：每一次都被均勻的分割為深度相近的兩個(gè)子表，所需要棧的最大深度為Log2N。空間復(fù)雜度為O(Log2N)

最壞情況下：但最壞的情況下，棧的最大深度為n.這樣快速排序的空間復(fù)雜度為O(N).這時(shí)就會(huì)導(dǎo)致棧溢出(Stack Overflow)。因?yàn)闂５目臻g很小。

這時(shí)候就需要非遞歸的算法，來解決棧溢出問題。

六、非遞歸寫法

1.棧模擬遞歸快排

如圖對(duì)以下數(shù)據(jù)排序

{ 6,1,2,7,9,3,4,5,10,8 }

void QuickSort(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	//先入0和9這段區(qū)間
	StackPush(&st, begin);
	StackPush(&st, end);
	while (!StackEmpty(&st))
	{
		//接著出棧，9和0，注意后進(jìn)先出
		int end = StackTop(&st);
		StackPop(&st);
		int begin = StackTop(&st);
		StackPop(&st);
		//然后再進(jìn)行對(duì)0和9這段區(qū)間單趟排序。
		int keyi = PartSort(a, begin, end);
		//[begin , keyi - 1] [keyi+1,end]
		//最后判斷區(qū)間是否為最小規(guī)模子問題，來判斷是否需要繼續(xù)入棧。
		if (begin < keyi - 1)
		{
			StackPush(&st, begin);
			StackPush(&st, keyi - 1);
		}
		if (keyi + 1 < end)
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, end);
		}
	}
	//記得銷毀棧。
	StackDestory(&st);
}

由此可以看出，雖然棧實(shí)現(xiàn)快排不是遞歸，但是和遞歸的思想一樣。簡直和遞歸一模一樣。

2.隊(duì)列實(shí)現(xiàn)快排

廢話不多說?？磮D

//快速排序的非遞歸形式1：通過隊(duì)列來實(shí)現(xiàn)
void QuickSort(int* a, int begin, int end)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, begin);
	QueuePush(&q, end);
	while (!QueueEmpty(&q))
	{
		int left = QueueFront(&q);
		QueuePop(&q);
		int right = QueueFront(&q);
		QueuePop(&q);
		int keyi = PartSort(a, left, end);//[left,keyi-1][keyi+1,right]
		if (left < keyi - 1)
		{
			QueuePush(&q, left);
			QueuePush(&q, keyi - 1);
		}
		if (keyi + 1 < right)
		{
			QueuePush(&q, keyi + 1);
			QueuePush(&q, right);
		}
	}
	QueueDestory(&q);
}

淺淺總結(jié)下

快排的平均時(shí)間復(fù)雜度為O(N*LogN)

如果每次劃分只有一半?yún)^(qū)間，另一半?yún)^(qū)間為空，則時(shí)間復(fù)雜度為n2

快排對(duì)初始順序影響較大，假如數(shù)據(jù)有序時(shí)，其性能最差。對(duì)初始順序比較敏感

以上就是C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)快速排序圖文示例的詳細(xì)內(nèi)容，更多關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)快速排序的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論