欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2022年05月10日 17:57:17   作者:_奇奇  
這篇文章主要為大家介紹了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)堆排序圖文示例

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

快速排序

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

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

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

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

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

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

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

具體實現(xiàn):

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

整體思路:

1.先進行一趟排序。

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

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

1.單趟排序

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

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

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

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

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

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

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

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

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

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

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

對于單趟來說。

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

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

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

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

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

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

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

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

3.代碼實現(xiàn)

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

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

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

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

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

{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)
{
	//當有個區(qū)間為空的時候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法思想類似,大差不差,沒什么區(qū)別。相比Hoare法較好理解。因為挖坑填坑思想很生動形象,所以較好理解。

1.單趟思路

單趟思路:

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

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

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

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

2.代碼實現(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)點:有了雙指針的優(yōu)化,不需要考慮 邊界問題!寫代碼不易出錯。

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

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

2.具體思路

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

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

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

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

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

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

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

3.代碼遞歸圖

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

4.代碼實現(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;
}

到這里快速排序還沒有完,因為它存在缺陷。還需繼續(xù)優(yōu)化。請往下看

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

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

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

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

當給你一組上萬個數(shù)據(jù)測試時,會發(fā)生超時現(xiàn)象。

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

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

1.三數(shù)取中

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

9 8 7 6 5 4 3 2 1 0

思路:

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

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

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

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

這樣做可以打破單邊樹形狀,可以使之變?yōu)槎?。因為這時候5做了key,key的左邊是比5小的,

key的右邊是比key大的。

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

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

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

2.代碼實現(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;
}

五、時間復(fù)雜度(重點)

結(jié)論大家都會,是N*LogN。怎么算出來的呢?

1.最好情況下

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

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

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

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

2.最壞情況下

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

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

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

每次選最左邊的為key。

3.空間復(fù)雜度

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

但是快排需要一個棧空間來實現(xiàn)遞歸

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

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

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

六、非遞歸寫法

1.棧模擬遞歸快排

如圖對以下數(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,注意后進先出
		int end = StackTop(&st);
		StackPop(&st);
		int begin = StackTop(&st);
		StackPop(&st);
		//然后再進行對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);
}

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

2.隊列實現(xiàn)快排

廢話不多說??磮D

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

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

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

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

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

相關(guān)文章

  • C/C++實現(xiàn)捕獲所有信號的示例詳解

    C/C++實現(xiàn)捕獲所有信號的示例詳解

    Linux的信號機制大部分情況下用不到,但是由于大部分信號的默認處理是終止進程,不正確處理會惹麻煩,所以我們來看看如何使用C/C++實現(xiàn)捕獲所有信號吧
    2024-03-03
  • 詳解C++之類和對象(1)

    詳解C++之類和對象(1)

    類是創(chuàng)建對象的模板,一個類可以創(chuàng)建多個對象,每個對象都是類類型的一個變量;創(chuàng)建對象的過程也叫類的實例化。每個對象都是類的一個具體實例(Instance),擁有類的成員變量和成員函數(shù)
    2021-11-11
  • 一個win32窗口創(chuàng)建示例

    一個win32窗口創(chuàng)建示例

    這篇文章主要介紹了一個win32窗口創(chuàng)建示例,需要的朋友可以參考下
    2014-04-04
  • C++?超詳細梳理繼承的概念與使用

    C++?超詳細梳理繼承的概念與使用

    這篇文章主要介紹了C++?多繼承詳情,C++支持多繼承,即允許一個類同時繼承多個類。只有C++等少數(shù)語言支持多繼承,下面我們就來看看具體的多繼承介紹吧,需要的朋友可以參考一下
    2022-03-03
  • 單鏈表實現(xiàn)反轉(zhuǎn)的3種方法示例代碼

    單鏈表實現(xiàn)反轉(zhuǎn)的3種方法示例代碼

    單鏈表的反轉(zhuǎn)是常見的面試題目,下面這篇文章主要給大家介紹了關(guān)于單鏈表實現(xiàn)反轉(zhuǎn)的3種方法,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習或者工作具有一定的參考學(xué)習價值,需要的朋友們下面來一起學(xué)習學(xué)習吧
    2019-02-02
  • c++入門必學(xué)算法之快速冪思想及實現(xiàn)

    c++入門必學(xué)算法之快速冪思想及實現(xiàn)

    快速冪相較于普通的冪,具有占用空間少,效率更高等優(yōu)點,全面碾壓普通的冪,下面這篇文章主要給大家介紹了關(guān)于c++入門必學(xué)算法之快速冪思想及實現(xiàn)的相關(guān)資料,需要的朋友可以參考下
    2022-11-11
  • C++ 中Vector常用基本操作

    C++ 中Vector常用基本操作

    標準庫vector類型是C++中使用較多的一種類模板,本文給大家分享C++ 中Vector常用基本操作,感興趣的朋友一起看看吧
    2017-10-10
  • C++?vector的簡單實現(xiàn)

    C++?vector的簡單實現(xiàn)

    這篇文章主要為大家詳細介紹了C++?vector的簡單實現(xiàn),使用數(shù)據(jù)庫,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-03-03
  • strtok函數(shù)的使用示例

    strtok函數(shù)的使用示例

    今天小編就為大家分享一篇關(guān)于strtok函數(shù)的使用示例,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2018-12-12
  • Qt事件過濾實現(xiàn)點擊圖片的放大和縮小

    Qt事件過濾實現(xiàn)點擊圖片的放大和縮小

    這篇文章主要為大家詳細介紹了Qt事件過濾實現(xiàn)點擊圖片的放大和縮小,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-08-08

最新評論