| 等 级 | |
| 排 名 | 107 |
| 经 验 | 7883 |
| 参赛次数 | 17 |
| 文章发表 | 13 |
| 年 龄 | 1 |
| 在职情况 | 学生 |
| 学 校 | 贺州学院 |
| 专 业 |
自我简介：
TA的其他文章
| 1159偶数求和，简单思路。 浏览：1293 |
| 5个条件搞定敲七游戏 浏览：731 |
| DFS算法解析 浏览：256 |
你可能喜欢
C语言程序设计教程（第三版）课后习题1.5 （C语言代码）浏览：369 |
Hello, world! （Java代码）浏览：1735 |
C二级辅导-计负均正 （C语言代码）浏览：506 |
C语言程序设计教程（第三版）课后习题7.5 （C语言代码）浏览：538 |
矩形面积交 （C语言代码）浏览：1511 |
解题思路:
快速排序（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分
2 人评分