解题思路:
快速排序（Quicksort）
基本思想：
一、选定中心轴pivot
二、将大于pivot的数字放在pivot的右边
三、将小于pivot的数字放在pivot的左边
四、分别对左右子序列重复前三步操作
例如：
19 97 9 17 1 8 //通常为了方便会选取第一个为pivot
19（pivot）
97 9 17 1 8
▲L ▲R
①首先是R（8<19）所以要放在pivot的左边，紧接着L向右移动
19（pivot）
8 97 9 17 1
▲L ▲R
②然后是L（97>19）所以要放在pivot的右边,紧接着R向左移动
19（pivot）
8 9 17 1 97
▲L ▲R
③R（1<19）所以要放在pivot的左边,紧接着L向右移动
19（pivot）
8 1 9 17 97
▲L ▲R
④L（9<19）所以要放在pivot的左边，即9保持不动，紧接着L继续向右移动
19（pivot）
8 1 9 17 97
▲L ▲R
⑤L（17<19）所以要放在pivot的左边，即17保持不动，紧接着L继续向右移动
19（pivot）
8 1 9 17 97
▲R（▲L）
⑥ 可以观察到 ▲L 与▲R 已经重合，那么就把pivot放回去
8 1 9 17 19 97
/* 左子序列 */ （8，1，9，17） /*右子序列*/ （97）
⑦ 这时挑出左子序列重复上述操作
8 1 9 17 //依然是取第一个为pivot
8（pivot）
1 9 17
▲L ▲R
⑧首先是R（17>8）所以要放在pivot的右边，即17保持不动，紧接着R继续向左移动
8（pivot）
1 9 17
▲L ▲R
⑨R(9>8)所以要放在pivot的右边，即9保持不动，紧接着R继续向左移动
8（pivot）
1 9 17
▲L ▲R
⑩R（1<8）所以要放在pivot的左边，紧接着L向右移动
8（pivot）
1 9 17
▲L（▲R）
⑪可以观察到 ▲L 与▲R 已经重合，那么就把pivot放回去
1 8 9 17
所以全排列为 1 8 9 17 19 97 （如果右子序列没拍完也是和左子序列一样的思路）
参考代码:
#include <stdio.h>
void Quicksort(int arry[],int L,int R) //L向左移动，R向右移动
{
if(L>=R)
return ;
int left=L,right=R; //大于pivot的放在右边小于的放在左边
int pivot=arry[left]; //取中心轴
while(left<right)
{
while(left<right && arry[right]>=pivot) //右边的数字大于中心轴，则不动
{
right--; //继续向左移动right
}
if(left<right)
{
arry[left]=arry[right]; //右边的数字小于中心轴就放在左边
}
while(left<right && arry[left]<=pivot) //左边的数字小于中心轴，则不动
{
left++; //继续向右移动left
}
if(left<right)
{
arry[right]=arry[left]; //左边的数字大于中心轴就放在右边
}
if(left>=right) //如果L与R重合
{
arry[left]=pivot; //中心轴归队
}
}
Quicksort(arry,L,right-1); //左子序列重复做
Quicksort(arry,right+1,R); //右子序列重复做
}
int main()
{
int n,i,a[100000];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
Quicksort(a,0,n-1);
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}0.0分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复