C/C++實現(xiàn)快速排序(兩種方式)圖文詳解
更新時間：2021年08月13日 14:33:04 作者：你的代碼沒bug
這篇文章主要介紹了C/C++實現(xiàn)快速排序的方法,這幾天在找工作，被問到快速排序，結(jié)果想不出來快速排序怎么弄的；回來搜索了一下，現(xiàn)在記錄下來，方便以后查看
介紹
快速排序是對冒泡排序算法的一種改進，快速排序算法通過多次比較和交換來實現(xiàn)排序。
流程如下：
實現(xiàn)
以下有兩種實現(xiàn)方式，說是兩種，其實就是在交換元素時具體細節(jié)上有點不同罷了。
方式一
int Partition(int A[],int low,int high){
int pivot=A[low];//第一個元素作為基準(zhǔn)
while(low<high){
while(low<high && A[high]>=pivot) high--;
A[low]=A[high];
while(low<high && A[low]<=pivot) low++;
A[high]=A[low];
}
A[low]=pivot;
return low;
}
void QuickSort(int A[],int low,int high){
if(low<high){
int pivotpos=Partition(A,low,high);
QuickSort(A,low,pivotpos-1);
QuickSort(A,pivotpos+1,high);
}
}
該方式，先把基準(zhǔn)元素保存起來
如下圖數(shù)組，把49看作基準(zhǔn)元素，先移動high指針，當(dāng)指向27時退出while循環(huán)，把27放到low位置
這時候，high位置就空出來一個，那么讓low移動，移動到下圖所示時，65>49，退出while循環(huán)，再將65放到high位置
這樣low這個位置又空出來了，再移動high，如此反復(fù)。
最后得到如下圖的情況：
這樣我們就按照“49”，把數(shù)組分為了左右兩部分。
對左右兩部分分別進行上述操作即可。
方式二
void Quick_sort(int left,int right,int arr[]){
if(left>=right)return;
int i,j,base,temp;
i=left,j=right;
base=arr[left];
while(i<j){
while(arr[j]>=base && i<j)j--;
while(arr[i]<=base && i<j)i++;
if(i<j){
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
arr[left]=arr[i];
arr[i]=base;
Quick_sort(left,i-1,arr);
Quick_sort(i+1,right,arr);
}
對于第二種方式，看下圖即可很好理解。
高低指針不是輪流替換空余位置，而是同時找到不符合的元素，然后交換二者。
最后，高低指針相遇，再把基準(zhǔn)元素與相遇位置上的元素交換即可。
總結(jié)
本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！
相關(guān)文章
C++類的內(nèi)存布局跟結(jié)構(gòu)體有點像,實際上,類中成員變量的內(nèi)存布局規(guī)則跟結(jié)構(gòu)體是一樣的,區(qū)別在于函數(shù),虛函數(shù)的放置,下面這篇文章主要給大家介紹了關(guān)于c++對象內(nèi)存布局的相關(guān)資料,需要的朋友可以參考下2021-10-10
這篇文章主要給大家介紹了關(guān)于C++ string字符串修改與替換方法的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
基于OpenCV自定義色條實現(xiàn)灰度圖上色功能代碼
今天通過本文給大家分享基于OpenCV自定義色條實現(xiàn)灰度圖上色功能代碼，代碼簡單易懂，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友參考下吧2021-11-11
大家好，本篇文章主要講的是C語言中結(jié)構(gòu)體實例解析，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下2022-02-02
下面小編就為大家?guī)硪黄P(guān)于memcpy和memmove的一點重要說明。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
C語言創(chuàng)建線程thread_create()的方法
這篇文章主要介紹了C語言創(chuàng)建線程thread_create()的方法，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
這篇文章主要為大家詳細介紹了C語言實現(xiàn)飛機訂票系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12
這篇文章主要介紹了病毒程序原理,寫個小程序做演示，大家可以參考這個以防中相似C病毒2013-12-12
C++數(shù)組模擬之單鏈表與雙鏈表和棧和隊列的實現(xiàn)過程
這篇文章主要介紹了C++數(shù)組模擬之單鏈表與雙鏈表和棧和隊列的實現(xiàn)過程，了解內(nèi)部原理是為了幫助我們做擴展，同時也是驗證了一個人的學(xué)習(xí)能力，如果你想讓自己的職業(yè)道路更上一層樓，這些底層的東西你是必須要會的，跟隨下文來具體了解吧2023-02-02
本文主要介紹了C++ 逗號運算符的具體使用,使用逗號運算符是為了把幾個表達式放在一起,具有一定的參考價值,感興趣的可以了解一下2023-08-08