C/C++實(shí)現(xiàn)快速排序算法的兩種方式實(shí)例
介紹
快速排序是對(duì)冒泡排序算法的一種改進(jìn)，快速排序算法通過多次比較和交換來實(shí)現(xiàn)排序。
流程如下
（圖片來自百度）
實(shí)現(xiàn)
以下有兩種實(shí)現(xiàn)方式，說是兩種，其實(shí)就是在交換元素時(shí)具體細(xì)節(jié)上有點(diǎn)不同罷了。
方式一
int Partition(int A[],int low,int high){
int pivot=A[low];//第一個(gè)元素作為基準(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)元素，先移動(dòng)high指針，當(dāng)指向27時(shí)退出while循環(huán)，把27放到low位置
這時(shí)候，high位置就空出來一個(gè)，那么讓low移動(dòng)，移動(dòng)到下圖所示時(shí)，65>49，退出while循環(huán)，再將65放到high位置
這樣low這個(gè)位置又空出來了，再移動(dòng)high，如此反復(fù)。
最后得到如下圖的情況：
這樣我們就按照“49”，把數(shù)組分為了左右兩部分。
對(duì)左右兩部分分別進(jìn)行上述操作即可。
方式二
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);
}
對(duì)于第二種方式，看下圖即可很好理解。
高低指針不是輪流替換空余位置，而是同時(shí)找到不符合的元素，然后交換二者。
最后，高低指針相遇，再把基準(zhǔn)元素與相遇位置上的元素交換即可。
（以下圖片來自網(wǎng)絡(luò)，侵刪）
總結(jié)
到此這篇關(guān)于C/C++實(shí)現(xiàn)快速排序的兩種方式的文章就介紹到這了,更多相關(guān)C/C++實(shí)現(xiàn)快速排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Qt自繪實(shí)現(xiàn)蘋果按鈕滑動(dòng)效果的示例代碼
這篇文章主要介紹了Qt自繪實(shí)現(xiàn)蘋果按鈕滑動(dòng)效果的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
C++使用map實(shí)現(xiàn)多進(jìn)程拷貝文件的程序思路
這篇文章主要介紹了C++使用mmap實(shí)現(xiàn)多進(jìn)程拷貝文件,通過本文給大家分享程序思路及完整代碼，代碼簡(jiǎn)單易懂，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-12-12
VC中控制臺(tái)程序創(chuàng)建窗口的實(shí)例方法
在本篇文章里小編給大家分享的是關(guān)于VC中控制臺(tái)程序創(chuàng)建窗口的實(shí)例方法及相關(guān)代碼內(nèi)容，有需要的朋友學(xué)習(xí)下吧。2021-12-12
小提琴圖 (Violin Plot)是用來展示多組數(shù)據(jù)的分布狀態(tài)以及概率密度。這種圖表結(jié)合了箱形圖和密度圖的特征，主要用來顯示數(shù)據(jù)的分布形狀。本文將介紹如何利用Matlab繪制小提琴圖，需要的可以參考一下2022-02-02
Vector是一個(gè)能夠存放任意類型的動(dòng)態(tài)數(shù)組，有點(diǎn)類似數(shù)組，是一個(gè)連續(xù)地址空間。本文將用C++模擬實(shí)現(xiàn)vector，感興趣的小伙伴可以了解一下2022-08-08
這篇文章主要為大家詳細(xì)介紹了QT實(shí)現(xiàn)用戶登錄注冊(cè)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章主要為大家詳細(xì)介紹了C++中的基本組件——內(nèi)存池的相關(guān)知識(shí)，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)C++有一定的幫助，需要的可以參考一下2023-03-03
這篇文章主要介紹了C++中的STL常用算法之遍歷算法詳解,ransform() 可以將函數(shù)應(yīng)用到容器的元素上,并將這個(gè)函數(shù)返回的值保存到另一個(gè)容器中,它返回的迭代器指向輸出容器所保存的最后一個(gè)元素的下一個(gè)位置,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了C++控制結(jié)構(gòu)詳情，C++的控制結(jié)構(gòu)和其它編程語言類似包括順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，更多相關(guān)資料需要的小伙伴可以參考下面文章內(nèi)容2022-03-03
c語言詳解動(dòng)態(tài)內(nèi)存分配及常見錯(cuò)誤的解決
給數(shù)組分配多大的內(nèi)存空間？你是否和初學(xué)C時(shí)的我一樣，有過這樣的疑問。這一期就來聊一聊動(dòng)態(tài)內(nèi)存的分配，讀完這篇文章，你可能對(duì)內(nèi)存的分配有一個(gè)更好的理解2022-04-04