C語言植物大戰數據結構快速排序圖文示例

“田傢少閑月,五月人倍忙”“夜來南風起,小麥覆隴黃”

快速排序

快速排序是Hoare於1962年提出的一種二叉樹結構的交換排序方法。所以快速排序有種方法是以他的名字命名的。相比70年前的祖師爺級的 大佬 來說,今天我們學習快速排序的成本已經非常低瞭。今天的我們的是站在巨人的肩膀上學習快速排序。

快速排序有三種方法實現,我們 都 需要掌握。

一、經典1962年Hoare法

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

什麼是快速排序?給你以下代碼,請你完善快速排序,你將怎麼完善?

快速排序:顧名思義,它比較快,整體而言適合各種場景下的排序。缺陷相較於其他排序小。且大部分 程序語言 排序的庫函數 的 源代碼都是由快速排序實現的

void QuickSort(int* a, int left, int 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法和二叉樹的**前序遍歷(根 左子樹 右子樹)**簡直一模一樣。

整體思路:

1.先進行一趟排序。

2.進行左半區間(左子樹)遞歸。

3.進行右半區間(右子樹)遞歸。

1.單趟排序

所有的排序的思想:就是先考慮單趟的排序,再合成n躺排序。這是毋庸置疑的,因為這樣的思想很自然。

對於單趟排序,也有一個思路。可以說算是規定吧,這是祖師爺Hoare的規定。

為瞭好理解思路,以下思路是整體上的思路,寫出來的程序還是有bug的。具體細節需要後期修改。

一定要按照規定走哦,不要問那麼多為什麼。按照規定走你就知道為什麼要這麼做瞭。總體思路規定:

1.設置一個基準值key,key一般為左邊第一個數的下標。定義左指針left和有指針right分別指向第一個和最後一個。

2.先讓右邊的right指針往左走,一直找比key所指向小的數,找到後就停下。

3.緊接著讓left指針往右走,一直找比key所指向大的數,找到後就停下。

4.如果第2步的right和第3步left都找到瞭,則交換swap兩者的值。然後繼續循環2和3步,直到left >= right為止。

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

此時,Hoare 的單趟排序完成。產生的效果是key作為分割線,把大小分割開瞭,比key所指向值小的在key左邊,比key所指向值大的在key右邊。

2.遞歸左半區間和右半區間

對於單趟來說。

單趟排完之後,key已經放在正確的位置瞭。

如果左邊有序,右邊有序,那麼我們整體就有序瞭。

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

解釋:分治解決子問題。相當於二叉樹。

一趟排序完成後,再對左半區間進行單趟排序,一直遞歸到什麼時候結束呢?

解釋:遞歸到左半區間隻有一個值的時候,或者為空的時候遞歸結束。

這個過程適合用 畫遞歸圖 來查看。

由於數據是10個數,遞歸圖龐大。所以此處省略。下面雙指針法有具體遞歸圖。

3.代碼實現

具體代碼實現和你想的總是那麼不同。因為特殊情況確實是存在,且還是那麼離譜。

我認為這個題難在瞭邊界問題,邊界問題要時刻註意!。

特殊情況1:當排以下數據時,我隻是把6改瞭,這樣會導致right和left直接不走瞭。

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

特殊情況2:當排以下數據時,會發生left找不到最大的值導致越界。

{5,4,3,2,1}

改動如下。

//快速排序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)
{
	//當有個區間為空的時候right-left會小於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法思想類似,大差不差,沒什麼區別。相比Hoare法較好理解。因為挖坑填坑思想很生動形象,所以較好理解。

1.單趟思路

單趟思路:

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

2.然後讓那個小的做坑,再讓左邊找比key大的,找到後填到坑中。依次循環,直到right和left相遇。

3.相遇後,把key的值填到相遇的位置。

這時,單趟循環結束。

2.代碼實現

和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函數的部分.

優點:有瞭雙指針的優化,不需要考慮 邊界問題!寫代碼不易出錯。

代碼好寫,不好理解。代碼極為簡單,隻需五行。

雙指針法也稱快慢指針法,兩個指針一前一後

2.具體思路

對於排6,3,2,1,5,4的升序來說。

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

prev和cur的關系:

1.cur還沒遇到比key大的值時,prev緊跟著cur,一前一後。

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

第一趟排序後的結果。這時候div為基準值。將左右子樹分隔開。

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

3.代碼遞歸圖

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

4.代碼實現

#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;
}

到這裡快速排序還沒有完,因為它存在缺陷。還需繼續優化。請往下看

四、三數取中優化(最終方案)

以上三種方法的時間復雜度

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

最壞情況:也就是在數據有序的情況下,就退化為瞭冒泡排序 O(N2)

當給你一組上萬個數據測試時,會發生超時現象。

例如LeetCode912. 排序數組

快排竟然超時瞭,這時候用三數取中來解決此問題。

1.三數取中

三數取中的含義:取三個數中間不是最大也不是最小的那個。哪三個數?第一個,最後一個,和中間那個。例如排以下數據時。

9 8 7 6 5 4 3 2 1 0

思路:

默認key選最左邊的數。

1.三個數取第一個 9 和第二個 1 和中間的 5

2.選出不是最大也不是最小的那個,也就是5。

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

這樣做可以打破單邊樹形狀,可以使之變為二分。因為這時候5做瞭key,key的左邊是比5小的,

key的右邊是比key大的。

二分後的時間復雜度還是N*LogN

註意:三數取中仍然無法完全解決

在某種特殊情況序列下時間復雜度變為O(n2)的情況

2.代碼實現(最終代碼)

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;
}

五、時間復雜度(重點)

結論大傢都會,是N*LogN。怎麼算出來的呢?

1.最好情況下

在最好的情況下:每次選key剛好能平分這組數據,一直都是二分,構成瞭滿二叉樹。

1.對於單趟排序的一層遞歸,不管是哪種方法,left和right每次都遍歷瞭一遍數組,時間復雜度為N。

2.因為滿二叉樹的高度為Log2N,所以遞歸深度(深度不等於次數)也為Log2N,所以遞歸Log2N層就是(N *Log2N).

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

2.最壞情況下

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

這樣,長度為n的數據表的快速排序需要經過n趟劃分,使得整個排序算法退化為冒泡排序,時間復雜度為N2

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

每次選最左邊的為key。

3.空間復雜度

在空間上來看,盡管快排隻需要一個元素的輔助空間。

但是快排需要一個棧空間來實現遞歸

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

最壞情況下:但最壞的情況下,棧的最大深度為n.這樣快速排序的空間復雜度為O(N).這時就會導致棧溢出(Stack Overflow)。因為棧的空間很小。

這時候就需要非遞歸的算法,來解決棧溢出問題。

六、非遞歸寫法

1.棧模擬遞歸快排

如圖對以下數據排序

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

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

由此可以看出,雖然棧實現快排不是遞歸,但是和遞歸的思想一樣。簡直和遞歸一模一樣。

2.隊列實現快排

廢話不多說。看圖

//快速排序的非遞歸形式1:通過隊列來實現
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);
}

淺淺總結下

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

如果每次劃分隻有一半區間,另一半區間為空,則時間復雜度為n2

快排對初始順序影響較大,假如數據有序時,其性能最差。對初始順序比較敏感

以上就是C語言植物大戰數據結構快速排序圖文示例的詳細內容,更多關於C語言數據結構快速排序的資料請關註LevelAH其它相關文章!

推薦閱讀: