兵贵神速-快速排序-（分治）

75 阅读 0 评论 50 点赞

我是靠谱客的博主多情纸鹤，最近开发中收集的这篇文章主要介绍兵贵神速-快速排序-（分治），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

算法实现：
（1）分解：先从数据中选择一个基准元素如然后呢将大于该基准元素得数据放在右边将小于该基准元素的数据放在后面。
（2）治理：对两个子序列分别进行快速排序。
（3）合并：将拍好顺序的连个子序列合并在一起，得到原问题的解。

#include<iostream>
using namespace std;
const int maxn=1000+5;
int A[maxn];
void Quick_sort(int front,int real)
{
	if(front>=real)	
		return ;
	int left=front;//序列的左边
	int right=real;//序列的右边
	int povit=A[left];//取基准元素
	while(left<right)//保证left小于right
	{
		while(left<right&&A[right]>povit)//注意再循环中条件left<right的重要性一旦出现left==right的情况
		//就说明该序列已经被基准元素一分为二了
			right--;
		if(left<right)	
			swap(A[left++],A[right]);//交换完成以后从左边的下一位开始比较
		while(left<right&&A[left]<=povit)
			left++;
		if(left<right)
		{
			swap(A[left],A[right--]);//交换完成后从右边的上一位开始比较
		}
	}
	Quick_sort(front,left-1);//递归对左半边进行排序
	//这里要保证第一个系数要大于第二个系数，我们呢也可以在下一个语句的开头加上限制条件
	Quick_sort(left+1,real);//递归对右半边进行排序
}
int main()
{
	int n;
	cin>>n;//输入要排序的数组的值
	for(int i=1;i<=n;i++)
	{	
		cin>>A[i];//输入数组的值
	}
	Quick_sort(1,n);
	for(int j=1;j<=n;j++)
		cout<<A[j]<<" ";
}

算法分析：
该算法中我们选择了A[left]作为数组的基准元素，从右边开始寻找小于 pivot 的数字，和基准元素交换。
再从数组的左边开始寻找一个大于pivot的汉字再和基准元素交换，到最后left=righ后A[left]=A[right]，
然后再分别对做序列进行排序和有序列进行排序。
算法的优化：上诉算法中我们每次从数组中找到一个大于或等于pivot的数字后都要和pivot进行交换，
而我们为什么不同是先从两边分别找到不满足的位置进行交换呢，这样大大的提高了算法的效率。

#include<iostream>
using namespace std;
const int maxn=1000+5;
int A[maxn];
void Quick_sort(int front,int real)
{
	if(front>=real)
		return ;
	//出口
	int left=front;
	int right=real;
	int pivot=A[left];//取A[left]为基准元素
	
	while(left<right)
	{
		while(left<right&&pivot<A[right])
			right--;//选中右边坐标
		while(left<right&&pivot>=A[left])
			left++;//选中左边坐标
		if(left<right)
		{
			swap(A[right--],A[left++]);//left不等于right时可以直接进行交换//并让left++，right--。
		}	
	}//while
	if(A[left]>pivot)//A[left]大于pivot时我们需要将left的前一位于pivot进行交换
	{
			swap(A[front],A[left-1]);//这里需要注意的是交换的值为A[front]而不是pivot
			Quick_sort(front,left-2);
			Quick_sort(left,real);
	}
	else//A[left]小于pivot正好将它交换过来保证小于pivot的数放在左侧
	{
			swap(A[front],A[left]);
			Quick_sort(front,left-1);//递归调用函数
			Quick_sort(left+1,real);
	}
}
int main()
{
	int n,m;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>A[i];
	}
	Quick_sort(1,n);
	for(int i=1;i<=n;i++)	
		cout<<A[i]<<" "; 
}