C++快速排序超詳細(xì)講解
一、快速排序原理
快速排序（QuickSort）是一種基于分治法的高效排序算法。它的基本思想是通過一個稱為“基準(zhǔn)”（pivot）的元素將數(shù)組劃分為兩部分，一部分的所有元素都比基準(zhǔn)小，另一部分所有元素都比基準(zhǔ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ù)組的元素進行比較交換進行部分排序，再利用遞歸整體排序
四、使用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 為分界點不會造成此問題.
因此再進行一次循環(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ù)調(diào)用約定_cdecl與_stdcall及_fastcall詳細(xì)講解
本篇文章使用的工具是vs2010，內(nèi)容可能涉及到匯編的知識，建議有一些匯編基礎(chǔ)的再來看，不過沒有匯編基礎(chǔ)也沒有關(guān)系，了解一下這三種調(diào)用約定即可2022-10-10
這篇文章主要為大家介紹了詳解如何使用openssl創(chuàng)建自簽名證書示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-04-04
深入C/C++浮點數(shù)在內(nèi)存中的存儲方式詳解
本篇文章是對C/C++浮點數(shù)在內(nèi)存中的存儲方式進行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
Visual Studio Code配置C、C++環(huán)境并編寫運行的方法
這篇文章主要介紹了Visual Studio Code配置C、C++環(huán)境并編寫運行的方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-08-08
這篇文章主要為大家詳細(xì)介紹了QT實現(xiàn)秒表項目，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
C語言實現(xiàn)修改文本文件中特定行的實現(xiàn)代碼
最近由于項目需要實現(xiàn)修改文件的功能，所以，博主認(rèn)真查閱了一些資料，但是，很遺憾，并沒有太多的收獲2013-06-06
使用編程語言進行編程時，需要用到各種變量來存儲各種信息。變量保留的是它所存儲的值的內(nèi)存位置。這意味著，當(dāng)您創(chuàng)建一個變量時，就會在內(nèi)存中保留一些空間。您可能需要存儲各種數(shù)據(jù)類型的信息，操作系統(tǒng)會根據(jù)變量的數(shù)據(jù)類型，來分配內(nèi)存和決定在保留內(nèi)存中存儲什么2022-07-07![深入理解C語言的new[]和delete[]](http://img.jbzj.com/images/xgimg/bcimg7.png)
new和delete既是C++中的關(guān)鍵字也是一種特殊的運算符。這篇文章主要介紹了C++的new和delete詳解,需要的朋友可以參考下2021-09-09
C語言中，我們經(jīng)常使用數(shù)據(jù)類型，那么整形數(shù)據(jù)在內(nèi)存中如何存儲？存儲方式是什么？如果你對這些內(nèi)容不太了解的話，相信看完這篇博客后，你會對整形數(shù)據(jù)的存儲有一個新的認(rèn)識。話不多說，我們進入正題2022-08-08
C語言中send()函數(shù)和sendto()函數(shù)的使用方法
這篇文章主要介紹了C語言中send()函數(shù)和sendto()函數(shù)的使用方法,是C語言入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09