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其它相關文章！