经典算法之快速排序

 

 活动地址：CSDN21天学习挑战赛 

 作者简介：大家好我是小唐同学(๑>؂<๑），为梦想而奋斗的小唐，让我们一起加油！！！

个人主页：小唐同学(๑>؂<๑）的博客主页

系列专栏：数据结构

博友们如果也是新手入门数据结构我希望大家可以多加练习 数据结构题库在牛客网就有已经给大家附上链接，可以直接点击跳转：刷题点这里

牛客网支持ACM模式哦，刷算法题也很推荐哦！！！

下面上文章------》

目录

快排思想：

 上全代码：

第一部分：

第二部分：

题解样例：

题目描述

输入格式

输出格式

输入输出样例

说明/提示

---

快排思想：

快速排序的排序速度是非常快的，效率较高，再加上快速排序思想----分治法和递归也确实实用，

该方法的基本思想是：

1．先从数列中取出一个数作为基准数

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

相对于冒泡排序来说，快速排序是从两边进行判断。

 上全代码：

# include 
using namespace std;
int a[100010];
void qsortt(int a[],int l,int r)
{
if(l>=r)
{
	return ;
}
int pivot=a[l];
	int left=l;
	int right=r;
	while(left
	{
		while(left=pivot)
			{
				
				right--;
			}
			if(left//说明  a[right]
			{
				a[left]=a[right];  //把最左值覆盖   因为有pivot可以暂存 
			}
			while(left//进行完右边进行左边 
			{
				left++; 
			}
			if(left//说明 a[left]>pivot    右调 
			{
			a[right]=a[left];      //  此时right的值已经调走 				
			} 
			if(left>=right)
			{
			a[left]=pivot;	
			} 
			//上边是进行初次排序
			//下边是分治  左右
	}
	
		qsortt(a,l,right-1);//最初位置到 pivot位置的前一个 
		qsortt(a,right+1,r); // 从pivot位置的下一个到最后 
}
 
int main() 
{
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i
	{
		cin>>a[i];
	}
	qsortt(a,0,n-1); 
	
		for(int i=0;i
	{
		cout<" ";
	}
	
}

第一部分：

	int pivot=a[l];
	int left=l;
	int right=r;

把基准数进行存储   左右结尾进行赋值

第二部分：

	while(left<right)
	{
		while(left<right&&a[right]>=pivot)
			{
				
				right--;
			}
			if(left<right)      //说明  a[right]<pivot   需要移位pivot左边 
			{
				a[left]=a[right];  //把最左值覆盖   因为有pivot可以暂存 
			}
			while(left<right&&a[left]<=pivot)//进行完右边进行左边 
			{
				left++; 
			}
			if(left<right)  //说明 a[left]>pivot    右调 
			{
			a[right]=a[left];      //  此时right的值已经调走 				
			} 
			if(left>=right)
			{
			a[left]=pivot;	
			} 
			//上边是进行初次排序
			//下边是分治  左右
	}
	
		qsortt(a,l,right-1);//最初位置到 pivot位置的前一个 
		qsortt(a,right+1,r); // 从pivot位置的下一个到最后 
}

题解样例：

题目描述

利用快速排序算法将读入的 NN 个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）

输入格式

第 11 行为一个正整数 NN，第 22 行包含 NN 个空格隔开的正整数 a_iai​，为你需要进行排序的数，数据保证了 A_iAi​ 不超过 10^9109。

输出格式

将给定的 NN 个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例

输入 #1复制

5
4 2 4 5 1

输出 #1复制

1 2 4 4 5

说明/提示

对于 20\%20% 的数据，有 N\leq 10^3N≤103；

对于 100\%100% 的数据，有 N\leq 10^5N≤105。

# include 
using namespace std;
int a[100010];
void qsort(int a[],int l,int r)
{
if(l>=r)
{
	return ;
}
int pivot=a[l];
	int left=l;
	int right=r;
	while(left
	{
		while(left=pivot)
			{
				
				right--;
			}
			if(left//说明  a[right]
			{
				a[left]=a[right];  //把最左值覆盖   因为有pivot可以暂存 
			}
			while(left//进行完右边进行左边 
			{
				left++; 
			}
			if(left//说明 a[left]>pivot    右调 
			{
			a[right]=a[left];      //  此时right的值已经调走 				
			} 
			if(left>=right)
			{
			a[left]=pivot;	
			} 
			//上边是进行初次排序
			//下边是分治  左右
	}
	
		qsort(a,l,right-1);//最初位置到 pivot位置的前一个 
		qsort(a,right+1,r); // 从pivot位置的下一个到最后 
}
 
int main() 
{
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i
	{
		cin>>a[i];
	}
	qsort(a,0,n-1); 
	
		for(int i=0;i
	{
		cout<" ";
	}
	
}