服务器之家

服务器之家 > 正文

C/C++实现快速排序(两种方式)图文详解

时间:2021-12-15 13:40     来源/作者:你的代码没bug

介绍

快速排序是对冒泡排序算法的一种改进,快速排序算法通过多次比较和交换来实现排序。

流程如下:

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/C++实现快速排序(两种方式)图文详解

C/C++实现快速排序(两种方式)图文详解

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

C/C++实现快速排序(两种方式)图文详解

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

C/C++实现快速排序(两种方式)图文详解

最后得到如下图的情况:

C/C++实现快速排序(两种方式)图文详解

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

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

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

对于第二种方式,看下图即可很好理解。

高低指针不是轮流替换空余位置,而是同时找到不符合的元素,然后交换二者。

最后,高低指针相遇,再把基准元素与相遇位置上的元素交换即可。

C/C++实现快速排序(两种方式)图文详解

C/C++实现快速排序(两种方式)图文详解

C/C++实现快速排序(两种方式)图文详解

C/C++实现快速排序(两种方式)图文详解

 

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注服务器之家的更多内容!

原文链接:https://blog.csdn.net/weixin_44915226/article/details/119535259

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部