C/C++實現快速排序(兩種方式)圖文詳解
介紹
快速排序是對冒泡排序算法的一種改進，快速排序算法通過多次比較和交換來實現排序。
流程如下：
實現
以下有兩種實現方式，說是兩種，其實就是在交換元素時具體細節上有點不同罷瞭。
方式一
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);
}
}
該方式，先把基準元素保存起來
如下圖數組，把49看作基準元素，先移動high指針，當指向27時退出while循環，把27放到low位置
這時候，high位置就空出來一個，那麼讓low移動，移動到下圖所示時，65>49，退出while循環，再將65放到high位置
這樣low這個位置又空出來瞭，再移動high，如此反復。
最後得到如下圖的情況：
這樣我們就按照“49”，把數組分為瞭左右兩部分。
對左右兩部分分別進行上述操作即可。
方式二
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);
}
對於第二種方式，看下圖即可很好理解。
高低指針不是輪流替換空餘位置，而是同時找到不符合的元素，然後交換二者。
最後，高低指針相遇，再把基準元素與相遇位置上的元素交換即可。
總結
本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！