前言
最近學習了演算法導論上的快速排序部分，有不少體會，
今天就來分享一下，在此歡迎大家批評指正文中的錯誤，
快速排序
正文
1.快速排序的優點
說起快速排序，它的名字就顯現出快排最大的優點————快，到底有多快呢？咱們用資料說話:
綜合一般情況來說，快排確實有(億點快)，特別是對較大資料量的排序，
快速排序的綜合時間復雜度是O(nlgn),但在極端最壞情況下，時間復雜度會到O(n^2)，
很多人在看到O(n^2)會產生疑問？為什么我們還要在實際生活中使用快排呢，
盡管快排的最壞時間復雜度很差，但是它的平均性能好，通常是實際排序中最好的選擇，它的期望時間復雜度是O(nlgn)，(絕大多數是這樣，在下文快排的性能分析中會有說明)，在排序中很少遇到最壞情況，并且O(nlgn)中隱含的常數因子非常小，
在C++庫函式中sort()函式底層大部分用快排實作的(可以參照下文的小區間優化)，
所以：快排，yyds！！！
2.快排的原理及實作
我們來理解快排的原理，快排運用了分治的思想，
在每一次排序中，選取一個資料作為主元x，在將資料的每個值與主元x進行比較，使每趟排序結束時，小于或等于x的在x資料的左邊，大于或等于x的在x的右邊，(和x相等的數可以在x的兩側，這就造成了快排的不穩定性)，
左子區間都是不大于x的數，右子區間都是不小于x的數，以x為界限，遞回左右子區間，從大致有序到全部有序，
下面我們來簡單實作快速排序，
void quick_sort(int *a, int l, int r)
{
if (l >= r)
return;
int x = a[l]; // 取最左邊的值作為主元x
int i = l, j = r;
while (i < j)
{
while (a[i] <= x && i<r) ++i; // 回圈結束時a[i]比x大
while (a[j] >= x && j>l) --j; // 回圈結束時a[j]比x小
if (i < j)
swap(a[i], a[j]); // 交換a[i],a[j]
}
// j為分界點
swap(a[l], a[j]); // 將主元x放在正確的位置，作為分界點
// 遞回左右子區間
quick_sort(a, l, j - 1);
quick_sort(a, j+1, r);
}
3.快排的性能分析
我們對上面的代碼進行分析：
-
最理想的情況：每次回圈的主元x都在區間的中間，遍歷一次資料的復雜度為O(n)，遞回次數為lgn，所以時間復雜度為O(nlgn)，
-
最壞的情況：當輸入的資料基本有序(逆序)時，在遞回時，產生兩個大小為n-1和0的子區間，使遞回的深度為n，時間復雜度變為O(n^2)，效率不及插入排序（后面會介紹用插入排序實作小區間優化以減少遞回的堆疊深度）
-
就平均情況來看，左區間長度：右區間長度=n，當n為9:1或者99:1時，只要n為常數比例的，演算法的時間復雜度總是O(nlgn)，
快排的幾種優化方式
對于快速排序，我們有很多優化方式避免快排達到最壞時間復雜度，
1.主元的隨機化選取
我們將主元的選取隨機化，可以降低快排達到最壞時間復雜度的可能性，
void quick_sort(int *a, int l, int r)
{
if (l >= r)
return;
int k = rand() % (r - l + 1) + l; // 產生l到r的亂數
// 從a[l]到a[r]中隨機選取
swap(a[l], a[k]);
int x = a[l];
int i = l, j = r;
while (i < j)
{
while (a[i] <= x && i<r) ++i; // 回圈結束時a[i]比x大
while (a[j] >= x && j>l) --j; // 回圈結束時a[j]比x小
if (i < j)
swap(a[i], a[j]); // 交換a[i],a[j]
}
// j為分界點
swap(a[l], a[j]); // 將主元x放在正確的位置，作為分界點
// 遞回左右子區間
quick_sort(a, l, j - 1);
quick_sort(a, j + 1, r);
}
2.三數取中
三數取中比主元的隨機化更有優勢，
三數取中的意思是：在a[l],a[(l+r)/2],a[r]三個數中選取中間大的數作為主元，可以有效的優化快排效率，
int Getmid(int *a, int l, int r)
{
// 取得中間值的下標
}
void quick_sort(int *a, int l, int r)
{
if (l >= r)
return;
swap(a[l], a[Getmid(a, l, r)]); // 三數取中
int x = a[l];
int i = l, j = r;
while (i < j)
{
while (a[i] <= x && i<r) ++i; // 回圈結束時a[i]比x大
while (a[j] >= x && j>l) --j; // 回圈結束時a[j]比x小
if (i < j)
swap(a[i], a[j]); // 交換a[i],a[j]
}
// j為分界點
swap(a[l], a[j]); // 將主元x放在正確的位置，作為分界點
// 遞回左右子區間
quick_sort(a, l, j - 1);
quick_sort(a, j + 1, r);
}
3.減小遞回的堆疊深度——小區間優化
在C++庫函式中sort()的底層實作是有一部分是快排的小區間優化，
我們看一下sort()函式底層實作的源代碼：
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
if (__first != __last)
{
// sort函式默認為內省排序，當子陣列小于16時回傳
std::__introsort_loop(__first, __last,
std::__lg(__last - __first) * 2,
__comp);
// 對大致排序過的陣列進行插入排序操作
std::__final_insertion_sort(__first, __last, __comp);
}
}
小區間優化：在子區間的長度小于16時，進行插入排序，減小遞回的堆疊深度，
模擬實作：
void Insert_sort(int *a, int l, int r)
{
for (int i = l + 1; i < r; ++i)
{
if (a[i] < a[i - 1])
{
int j = i, k = a[i];
while (a[i]<a[--j] && j>l);
int tmp = j;
while (j < i)
{
a[j + 1] = a[j];
++j;
}
a[tmp] = k;
}
}
}
void quick_sort(int *a, int l, int r)
{
if (r - l < 16) // 在子區間的長度小于16時，進行插入排序，減小遞回的堆疊深度
Insert_sort(a, l, r);
int x = a[l]; // 取最左邊的值作為主元x
int i = l, j = r;
while (i < j)
{
while (a[i] <= x && i<r) ++i; // 回圈結束時a[i]比x大
while (a[j] >= x && j>l) --j; // 回圈結束時a[j]比x小
if (i < j)
swap(a[i], a[j]); // 交換a[i],a[j]
}
// j為分界點
swap(a[l], a[j]); // 將主元x放在正確的位置，作為分界點
// 遞回左右子區間
quick_sort(a, l, j - 1);
quick_sort(a, j+1, r);
}
4.其他優化：
演算法導論還提到了其他的優化方法，比如用尾遞回減少堆疊深度，針對相同元素值的快速排序等等，
今天就分享到這里，歡迎大家在評論區留言，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/302129.html
標籤：其他