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];//第一個元素作為基準
	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，如此反復(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);
}

對于第二種方式，看下圖即可很好理解。

高低指針不是輪流替換空余位置，而是同時找到不符合的元素，然后交換二者。

最后，高低指針相遇，再把基準元素與相遇位置上的元素交換即可。

在這里插入圖片描述