2613: 分治策略-快速排序
金币值：3
定数：6
时间限制：1.000 s
内存限制：128 M
正确：4
提交：4
正确率：100.00% 命题人：
题目描述
快速排序问题：输入一个正整数n（n<=10）并输入n个无序的整数，要求将其排列成一个有序的序列（从小到大）并输出到屏幕，要求用分治策略实现。
测试代码 复制
#include <stdio.h>
int partition(int a[], int low, int high) {
int i = low;
int j = high;
while (i<=j) {
// 从左到右
// 从右到左
// 交换
if(i<j){
}
}
// 交换
return j; // 注意返回的是j而不是i
}
void quickSort(int a[], int left, int right) {
if(left<right) {
int index = partition(a, left, right);
quickSort(a, left, index-1);
quickSort(a, index+1, right);
}
}
int main(void) {
int a[10],i,n;
scanf("%d",&n);
for(i = 0; i < n; i++ ) {
scanf("%d",&a[i]);
}
quickSort(a, 0, n-1);
for (i = 0; i < n; i++) {
if(i<n-1) printf("%d ",a[i]);
else printf("%d\n",a[i]);
}
return 0;
}输入格式
第1行输入一个整数n，表示无序序列中的元素个数
第2行输入n个整数，每两个整数之间用空格隔开
第2行输入n个整数，每两个整数之间用空格隔开
输出格式
第3行输出一个有序的序列，该序列中有n个整数，每两个整数之间用一个空格隔开。
输入样例 复制
5
1 3 4 5 2输出样例 复制
1 2 3 4 5