C++中怎样实现快速排序

发布时间：2021-08-13 17:24:49 阅读：112 作者：Leah 栏目：开发技术

C++开发者专用服务器限时活动，0元免费领，库存有限，领完即止！点击查看>>

这期内容当中小编将会给大家带来有关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位置

C++中怎样实现快速排序

这时候，high位置就空出来一个，那么让low移动，移动到下图所示时，65>49，退出while循环，再将65放到high位置

C++中怎样实现快速排序

这样low这个位置又空出来了，再移动high，如此反复。

C++中怎样实现快速排序

最后得到如下图的情况：

C++中怎样实现快速排序

这样我们就按照“49”，把数组分为了左右两部分。

对左右两部分分别进行上述操作即可。

C++中怎样实现快速排序

方式二

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);
}