C++快速排序超詳細(xì)講解
一、快速排序原理
快速排序（QuickSort）是一種基于分治法的高效排序算法。它的基本思想是通過一個稱為“基準(zhǔn)”（pivot）的元素將數(shù)組劃分為兩部分，一部分的所有元素都比基準(zhǔn)小，另一部分所有元素都比基準(zhǔn)大，然后遞歸地對這兩部分進(jìn)行同樣的操作，直到整個數(shù)組有序。
二、快速排序標(biāo)準(zhǔn)代碼
void quick_sort(int q[], int l, int r)
{
if (l >= r) return; //遞歸停止條件
int i = l - 1, j = r + 1, x = q[l + r >> 1]; //設(shè)定指針,基準(zhǔn)
while (i < j)
{
do i++; while (q[i] < x); //q[i]大于等于基準(zhǔn)時,指針i停止
do j--; while (q[j] > x); //q[j]小于等于基準(zhǔn)時,指針j停止
if (i < j) swap(q[i], q[j]); //判斷是否i<j,交換i,j對應(yīng)的數(shù)組元素
} // 結(jié)束時數(shù)組被分為 >=x,<=x 的兩部分
quick_sort(q, l, j); //繼續(xù)分直到分到一到兩個元素此時數(shù)組有序
quick_sort(q, j + 1, r);
}三、代碼解析
我們以一個簡單的例子幫助我們了解快速排序
| 5 | 3 | 4 | 1 | 2 |
1.排序的數(shù)組以及需要排序元素的范圍，無返回值
void quick_sort(int q[], int l, int r)
2.遞歸結(jié)束的條件：元素剩一個或空
if (l >= r) return;
3.設(shè)定變量，其中 i, j 為兩個指針分別減 1 加 1 是為了下一步的 do while 循環(huán)，x 即為“基準(zhǔn)”（pivot) 用來將列表分為 <=x 和 >=x 的兩部分，x 是隨機的，這里取了數(shù)組中間的一個元素，l + r >> 1相當(dāng)于 (l + r)/2 (pivot:q[2] = 4)向下取整(提高了效率)
int i = l - 1, j = r + 1, x = q[l + r >> 1];
| 5 | 3 | 4 | 1 | 2 | ||
| i | 0 | 1 | 2 | 3 | 4 |
4.while循環(huán)實現(xiàn)了遍歷、比較、交換的功能，先使 i 指針遞增直到 i 所對應(yīng)的元素 >=x 停止,接下來使 j 指針遞減直到其對應(yīng)的元素 <=x 停止
while (i < j)
{
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}| 5 | 3 | 4 | 1 | 2 |
| i(>=4停止) | j(<=4停止) |
交換之后開啟下一次循環(huán)
| 2 | 3 | 4 | 1 | 5 |
| <4 | <4 | i(>=4停止) | j(<=4停止) | >4 |
滿足 i<j 交換
| 2 | 3 | 1 | 4 | 5 |
| <4 | <4 | j(<=4停止) | i(>=4停止) | >4 |
不滿足 i<j 不交換,此時整個 while 循環(huán)結(jié)束,注意此時 j(包含)往左為 <=4 部分,j + 1 及其往右為 >=4部分
5.接下來就是遞歸了,每次運行分將數(shù)組為左<=右的兩部分,我們只需將左右兩部分分別執(zhí)行函數(shù)程序得到直到剩兩個或一個元素,此時數(shù)組便有序了
quick_sort(q, 0, 2);
| 2 | 3 | 1 | 4 | 5 |
| <4 | <4 | j(<=4停止) | i(>=4停止) | >4 |
x(pivot)=3
| 2 | 3 | 1 |
| <3 | i(>=3停止) | j(<=3停止) |
| 2 | 1 | 3 |
| <3 | j(<=3停止) | i(>=3停止) |
quick_sort(q, 0, 1);
x(pivot)=2
2 | 1 |
| i(>=2停止) | j(<=2停止) |
1 | 2 |
| j(<=2停止) | i(>=2停止) |
剩一個元素時,執(zhí)行遞歸停止程序:
if (l >= r) return;
數(shù)組中最初的“左”部分就變?yōu)?/p>
| 1 | 2 | 3 |
而最初的“右”部分:x(pivot)=4
| 4 | 5 |
| i(>=4停止)j(<=4停止) | >5 |
if (i < j) swap(q[i], q[j]);
不滿足 if 條件以及 while 條件,while 循環(huán)停止,依舊選擇了 j 為分界點分到一個元素時結(jié)束遞歸
此時代碼全部有序
| 1 | 2 | 3 | 4 | 5 |
quick_sort(q, l, j); quick_sort(q, j + 1, r);
6.總結(jié)
快速排序利用兩個指針對數(shù)組的元素進(jìn)行比較交換進(jìn)行部分排序，再利用遞歸整體排序
四、使用while循環(huán)的快速排序
1.代碼
代碼1.由快排代碼等價轉(zhuǎn)化而來
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l, j = r, x = q[l + r >> 1];
while (i < j)
{
while (q[i] < x) i++;
while (q[j] > x) j--;
if (i < j)
{
swap(q[i], q[j]);
if (i + 1 < j - 1)
{
i++;
j--;
}
else
{
i++;
j--;
while (q[i] < x) i++;
while (q[j] > x) j--;
break;
}
}
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}代碼2.效率提高版
void quick_sort(int q[], int l, int r) {
if (l >= r) return;
int x = q[l + r >> 1];
int i = l, j = r;
while (i <= j) { // 注意：這里應(yīng)該是 i <= j 而不是 i < j
while (q[i] < x) i++;
while (q[j] > x) j--;
if (i <= j) {
swap(q[i], q[j]);
i++;
j--;
}
}
quick_sort(q, l, j);
quick_sort(q, i, r);
}2.代碼2解析
1.因為沒有 do 過程,所以指針起始位置直接設(shè)在了 0 和 -1 的位置,
if (l >= r) return; int x = q[l + r >> 1]; int i = l, j = r;
| 5 | 3 | 4 | 1 | 2 |
| i |
2. while 循環(huán)中的 while 循環(huán)先判斷是否滿足條件,滿足的話指針加/減 1,這樣停止時依舊是對應(yīng)元素 >=x 或 <=x 時的指針,
while (i <= j)
{
while (q[i] < x) i++;
while (q[j] > x) j--;
if (i <= j)
{
swap(q[i], q[j]);
i++;
j--;
}
}| 5 | 3 | 4 | 1 | 2 |
| i(停) | j(停) |
換過之后+=或--
| 2 | 3 | 4 | 1 | 5 |
| <4 | i(停) | j(停) |
交換，++/--
| 2 | 3 | 1 | 4 | 5 |
| j | i |
不滿足 i<=j while 循環(huán)結(jié)束.
關(guān)于 i<=j 的條件判斷,我們給出新的案例
| 3 | 2 | 1 |
| i(停) | j(停) |
交換之后 ++/--
| 1 | 2 | 3 |
| i(停) j(停) |
注意此時并沒有返回(return),
遞歸代碼:分別以 j 和 i 作為分界點
quick_sort(q, l, j); quick_sort(q, i, r);
而如果條件判斷為 < 的話 i=j 時就會造成下一次遞歸多了一個元素,
而標(biāo)準(zhǔn)代碼的運行過程到此處后結(jié)束,以 j 和 j+1 為分界點不會造成此問題.
因此再進(jìn)行一次循環(huán)
| 1 | 2 | 3 |
| j | i |
而此時元素 2 的位置是 i,j同時停過的位置即為基準(zhǔn) x,而i,j也會再下一次++/--后停止,所以我們可以直接將元素 2 所對應(yīng)的數(shù)組位置固定不動,將元素 2 左右的數(shù)組遞歸處理.
quick_sort(q, l, j); quick_sort(q, i, r);
五、總結(jié)
使用 while 循環(huán)會比 do while 多一層內(nèi)層循環(huán),所以 do while 循環(huán)效率更高,建議只用 do while 循環(huán).
到此這篇關(guān)于C++快速排序的文章就介紹到這了,更多相關(guān)C++快速排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語言編程數(shù)據(jù)結(jié)構(gòu)帶頭雙向循環(huán)鏈表全面詳解
這篇文章主要為大家介紹了C語言編程的數(shù)據(jù)結(jié)構(gòu)中帶頭雙向循環(huán)鏈表全面詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助祝大家多多進(jìn)步，早日升職加薪2021-10-10
C語言strlen和sizeof在數(shù)組中的使用詳解
對于 strlen 和 sizeof，相信不少程序員會混淆其功能。雖然從表面上看它們都可以求字符串的長度，但二者卻存在著許多不同之處及本質(zhì)區(qū)別2021-10-10
這篇文章主要介紹了c++中std::hash以及萬能hash的使用方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
C語言實現(xiàn)酒店客房管理系統(tǒng)課程設(shè)計
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)酒店客房管理系統(tǒng)課程設(shè)計，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
本文主要介紹了如何解決Devc++運行窗口中文亂碼，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
C/C++題解LeetCode1295統(tǒng)計位數(shù)為偶數(shù)的數(shù)字
這篇文章主要為大家介紹了C/C++題解LeetCode1295統(tǒng)計位數(shù)為偶數(shù)的數(shù)字示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-01-01
這篇文章主要介紹了C++選擇文件夾代碼的封裝,實例展示了將選擇文件夾功能代碼封裝為一個類并對其進(jìn)行實例化調(diào)用的過程,對于學(xué)習(xí)C++程序設(shè)計有不錯的參考價值,需要的朋友可以參考下2014-10-10
這篇文章介紹了軟件構(gòu)建工具makefile，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-12-12
C++靜態(tài)庫與動態(tài)庫文件的生成和使用教程
庫文件是計算機上的一類文件,可以簡單的把庫文件看成一種代碼倉庫,它提供給使用者一些可以直接拿來用的變量、函數(shù)和類,下面這篇文章主要給大家介紹了關(guān)于C++靜態(tài)庫與動態(tài)庫文件的生成和使用的相關(guān)資料,需要的朋友可以參考下2023-03-03
以下是對C語言中頭文件和庫的一些問題進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以參考下2013-07-07