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