一、快速排序遞歸法
1.快速排序思想
快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止
2.hoare版本實現(xiàn)快速排序
hoare版本的快速排序的基本思路是，先選出最左邊或者最右邊的值為key，如果選左邊，那就讓右邊先走，如果選右邊，那就讓左邊先走。后面會說為什么必須這樣走。我們假定選左邊為key，那么當右邊碰到比key小的時候，停下來。然后讓左邊走，當左邊的找到一步比key大的時候，左邊停下來，然后交換這兩個值。
之后，我們將循環(huán)結束的位置稱之為keyi，這樣，我們交換key和keyi位置的數(shù)據(jù)。
然后這樣我們會發(fā)現(xiàn)，我們已經將一個數(shù)據(jù)給放到他應該在的位置上了。
這樣我們可以使用遞歸的思想，將左半?yún)^(qū)間和右半?yún)^(qū)間分別遞歸。
如此一來。也就成功實現(xiàn)了排序
//快速排序
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int begin = left;
int end = right;
int keyi = left;
while (left < right)
{
//右邊找小
while (left < right && a[right] >= a[keyi])
{
right--;
}
//左邊找大
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
QuickSort(a, begin, left - 1);
QuickSort(a, left + 1, end);
}
如上代碼所示，但是這種方法我們需要有幾點注意事項
1：遞歸結束條件，不難發(fā)現(xiàn)，我們這樣一直遞歸下去，總有一個區(qū)間只有一個元素，或者不存在元素。這樣的情況就得返回了。由于我們是知道left和right的，一旦上一層遞歸中只有兩個或者三個元素的時候，下一次遞歸傳遞的left和right一定是left>=right的。這就可以作為遞歸結束條件了。
2.右邊找小和左邊找大的時候，假如不添加left<right進行限定。那么一旦整個數(shù)組的其他值都大于key，或者小于key，有可能造成直接越界了。
3.我們所說的找小和找大是嚴格的小于，不能是等于，因為等于可以是在key的左邊也可以是在key的右邊，如果我們特殊處理等于的情況，有可能造成無法預知的后果。
4.如果選左邊為key，那么必須從右邊開始走，反之亦然。只有這樣才能保證相遇位置一定是小于key或者大于key的一個數(shù)。后面會詳細證明
時間復雜度分析
對于上面的快排，我們可以簡單的分析一下時間復雜度。不難得知，他的遞歸方式類似于一顆二叉樹。
不難發(fā)現(xiàn)，他最好情況一共有l(wèi)ogN層，第一層有一個key，每一側的key都是上一層的兩倍。但是當數(shù)據(jù)量很大時候，key的數(shù)量對N的影響不大。所以每一層的數(shù)據(jù)量仍然是O(N)級別，而每一層我們其實都會遍歷一遍的為了選出同key數(shù)量相等的數(shù)。所以每一層的時間復雜度為O(N)。所以總的時間復雜度為O(N*logN)，而空間復雜度為O(logN)，這是因為總共會開logN層棧幀。但是上面的其實是最好的情況，對于快排而言，最壞的情況是數(shù)據(jù)量全部順序，或者全部逆序的情況。在這種情況下，快排由于每次只能搞定一個元素，而這個元素恰好就是最邊緣的元素，這樣就需要開N層棧幀，每層都需要N-i次，類似于等差數(shù)列。時間復雜度變?yōu)榱?strong>O(N2),空間復雜度變?yōu)榱?strong>O(N)。
3.hoare版本的優(yōu)化
我們可以看到hoare版本的快速排序其實還是存在一些問題的，當數(shù)據(jù)順序或逆序的時候，效率很低。反而亂序的時候效率很高。所以我們可以采用一些特殊方法來處理一下。
1>使用隨機值rand()函數(shù)
我們發(fā)現(xiàn)，快速排序的問題就在于一旦出現(xiàn)順序或者逆序就會導致效率很低，但是我們可以使用一種隨機選key來處理一下。使得每一次選出的key都是隨機值，具體做法為使用rand函數(shù)，隨機生成一個下標，將這個下標與最左邊的交換。這樣就能確保每一次都是一個隨機的下標。因為在大量數(shù)據(jù)面前，每次隨機選數(shù)，恰好為順序或逆序的概率為0。根據(jù)這種思想，代碼為
//快速排序
void QuickSort1(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int begin = left;
int end = right;
int keyi = left;
int randi = left + rand() % (right - left);
Swap(&a[randi], &a[left]);
while (left < right)
{
//右邊找小
while (left < right && a[right] >= a[keyi])
{
right--;
}
//左邊找大
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
QuickSort1(a, begin, left - 1);
QuickSort1(a, left + 1, end);
}
2>三數(shù)取中
三數(shù)取中的基本思想是這樣的：將最左邊，最右邊，以及中間三個位置的元素的數(shù)據(jù)中，取出中間的數(shù)據(jù)，然后讓數(shù)值為中間的數(shù)據(jù)的下標與最左邊進行交換，而取中的邏輯可如下
>由于三數(shù)取中的優(yōu)化，可以使得每一次的左值一定不是最大或者最小的。從而優(yōu)化掉順序或者逆序的情況
int GetMidNumi(int* a, int left, int right)
{
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[left] < a[right])
{
return left;
}
else if (a[mid] < a[right])
{
return right;
}
else
{
return mid;
}
}
}
//快速排序：三數(shù)取中
void QuickSort2(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int begin = left;
int end = right;
int keyi = left;
int midi = GetMidNumi(a, left, right);
Swap(&a[midi], &a[left]);
while (left < right)
{
//右邊找小
while (left < right && a[right] >= a[keyi])
{
right--;
}
//左邊找大
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
QuickSort2(a, begin, left - 1);
QuickSort2(a, left + 1, end);
}
3>三路劃分
如果遇到大量相同的元素的話，那么前面的方法都不好使了。這時就引出了三路劃分。三路劃分后面具體詳細講解
4.證明hoare版本的key在左邊，必須讓右邊先走
左邊做key，必須右邊先走，可以保證相遇位置一定小于key或者相遇位置就是key，從而使得key與相遇位置交換后，使得key落到他應該存在的位置。
1.R找到小，L找大沒有找到，L遇到R，相遇位置一定是比key小的
2.R找小，沒有找到，直接遇到L,要么就是一個比key小的，要么就是直接就是key
3.類似道理，右邊作key，左邊就得先走
5.挖坑法實現(xiàn)快速排序
首先是挖坑法的基本思想，先將最左邊的數(shù)保存在一共臨時變量里面，然后讓這個左下標設置為坑，假定坑內沒有有效數(shù)據(jù)，然后右邊先走，當遇到一個比臨時變量小的數(shù)的時候，將這個值甩給坑，然后將坑重新設置為當前的right。然后左邊走，找到一個比臨時變量大的數(shù)據(jù)的時候，將這個數(shù)據(jù)甩給右邊的坑。如此循環(huán)下去。當兩個相遇的時候，我們在將臨時變量的值賦給坑。就將一個數(shù)據(jù)排好了
//快速排序：挖坑法
void QuickSort3(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int begin = left;
int end = right;
int hole = left;
int midi = GetMidNumi(a, left, right);
Swap(&a[midi], &a[left]);
int key = a[left];
while (left < right)
{
//右邊找小
while (left < right && a[right] >= key)
{
right--;
}
a[hole] = a[right];
hole = right;
//左邊找大
while (left < right && a[left] <= key)
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
QuickSort3(a, begin, hole - 1);
QuickSort3(a, hole + 1, end);
}
6.將前面快排的一趟排序給提取出來
這是為了方便我們后面寫快排的非遞歸形式.
int PartSort1(int* a, int left, int right)
{
int keyi = left;
int midi = GetMidNumi(a, left, right);
Swap(&a[midi], &a[left]);
while (left < right)
{
//右邊找小
while (left < right && a[right] >= a[keyi])
{
right--;
}
//左邊找大
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;
}
int PartSort2(int* a, int left, int right)
{
int hole = left;
int midi = GetMidNumi(a, left, right);
Swap(&a[midi], &a[left]);
int key = a[left];
while (left < right)
{
//右邊找小
while (left < right && a[right] >= key)
{
right--;
}
a[hole] = a[right];
hole = right;
//左邊找大
while (left < right && a[left] <= key)
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
//快速排序
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = PartSort2(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
7.雙指針法實現(xiàn)快速排序
雙指針法的基本思路如下：
1.仍然讓最左邊設置為key，然后讓prev指針指向第一個元素，讓cur指針指向第二個元素。
2.當cur所指向的小于key的時候，我們先讓prev++，然后讓prev所指向的與cur所指向的交換位置。然后讓cur++。
3.當cur所指向的大于key的時候，我們直接讓cur++即可。
4.最終當cur大于right的時候結束。此時prev恰好指向最后一個小于key的數(shù)，prev后面的全部數(shù)都是大于key的。
5.我們直接讓key和prev進行交換。這樣就將一趟給排好了
int PartSort3(int* a, int left, int right)
{
int midi = GetMidNumi(a, left, right);
Swap(&a[midi], &a[left]);
int prev = left;
int cur = left + 1;
int key = a[left];
while (cur <= right)
{
if (a[cur] > key)
{
cur++;
}
else
{
prev++;
Swap(&a[prev], &a[cur]);
cur++;
}
}
Swap(&a[prev], &a[left]);
return prev;
}
//快速排序
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = PartSort3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
事實上，上面的代碼還有一種更加優(yōu)雅的寫法
int PartSort3(int* a, int left, int right)
{
int midi = GetMidNumi(a, left, right);
Swap(&a[midi], &a[left]);
int prev = left;
int cur = left + 1;
int key = a[left];
while (cur <= right)
{
if (a[cur] < key && ++prev != cur)
Swap(&a[cur], &a[prev]);
cur++;
}
Swap(&a[prev], &a[left]);
return prev;
}
//快速排序
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = PartSort3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
8.快速排序小區(qū)間優(yōu)化
由于我們的快速排序是使用遞歸的思想。類似于二叉樹。我們可以發(fā)現(xiàn)，在最底層的遞歸中。每一個都是小區(qū)間，但是每一個小區(qū)間我們都需要使用很多次遞歸。而最后的幾層占據(jù)了絕大多數(shù)遞歸。比如最后三層，占據(jù)了50%+25%+12.5%=87.5%的遞歸。這樣的消耗確實挺大。我們可以在最后的小區(qū)間，讓他不要使用遞歸了，直接使用插入排序來進行優(yōu)化。因為小區(qū)間以及很接近有序了。使用插入排序最佳。這樣可以極大的節(jié)約消耗。當然區(qū)間不可以太大，因為我們要考慮小區(qū)間直接插入的效率高于遞歸的效率，否則得不償失
//快速排序
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
if ((right - left + 1) > 10)
{
int keyi = PartSort3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
else
{
InsertSort(a + left, right - left + 1);
}
}
二、快速排序非遞歸
上面我們已經詳細分析了快速排序的遞歸版本。但是只要是遞歸就一定會存在某些問題：
1.效率
2.深度太深，棧溢出
這時候就需要我們將遞歸形式改為非遞歸形式。
遞歸改成非遞歸有兩種情況
1:直接改遞歸，這比較適合一些簡單的遞歸
2:間接改遞歸，使用棧輔助改遞歸
對于這個快排，我們直接改遞歸是比較困難的，我們可以使用間接的方式
遞歸其實就是不斷建立棧幀的過程，而棧是可以模擬一個遞歸的過程的
我們先分析在遞歸下的快排，其實快排遞歸本質就是區(qū)間的變化
我們可以將他的區(qū)間下標給入棧，為了更好的模擬，我們需要使用右邊的變量先入棧，然后再讓左邊的變量入棧。這樣可以保證最終先出的是左邊的，然后是右邊的變量。我們每次入?yún)^(qū)間的時候，也是先讓右區(qū)間入，再讓左區(qū)間入，這樣可以保證出的時候先出左區(qū)間。
然后就是我們不斷取出區(qū)間，進行每一趟快排了，這也就是之前我們需要將一趟快排給提取出來的原因，為了方便我們改為非遞歸。后面就是不斷入?yún)^(qū)間出區(qū)間的過程了文章來源：http://www.zghlxwxcb.cn/news/detail-428318.html
//快速排序非遞歸
void QuickSortNonR(int* a, int left, int right)
{
if (left >= right)
{
return;
}
Stack st;
StackInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
int keyi = PartSort3(a, begin, end);
// [begin,keyi-1] keyi [keyi+1,end]
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (begin < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
StackDestroy(&st);
}
———————————————————————————————————————
好了本期內容就到這里了
如果對你有幫助的話，不要忘記點贊加收藏哦?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-428318.html
到了這里，關于【數(shù)據(jù)結構】第十三站：排序（中）快速排序的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
