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)文章!