189 8069 5689
（1）问题描述
创新互联公司坚持“要么做到，要么别承诺”的工作理念，服务领域包括：网站制作、成都网站设计、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的鹤壁网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！对于任意的无序正整数序列，写程序用快速排序算法将其排序成按值非递减有序序列。
（2）输入描述
文本文件“input.txt”中保存了n个测试用例，文件以-1结束。每个用例的第一行m表示第一个待排序整数序列的元素个数，第二行为该序列的m个元素。
（3）输出描述
输出结果保存在文本文件“output.txt”中。对于每个测试用例均有二行输出，第一行输出“Case #:##”，#表示用例的编号（1…n），##表示排序后有序序列的元素个数，第二输出##个按值非递减有序元素。
（4）输入示例
5
10 1 8 4 30
7
35 60 50 2 20 4 86
3
38 100 45
-1
（5）输出示例
Case 1:5
4 8 10 30
Case 2:7
2 4 20 35 50 60 86
Case 3:3
38 45 100
代码实现：
#define _CRT_SECURE_NO_WARNINGS
#include#includevoid swap(int a[], int low, int high) //交换两个数的值
{
int t = a[low];
a[low] = a[high];
a[high] = t;
}
int getpoint(int a[], int low, int high) //计算基准点，分割为左右两个数组
{
int point = a[low];//基准点等于第一个元素
while (low< high)
{
while (low< high && a[high] >= point)//控制high指针比较并左移
{
high--;
}
swap(a, low, high);
while (low< high && a[low]<= point)//控制low指针比较并右移
{
low++;
}
swap(a, low, high);
}
return low;//返回基准点位置
}
void quicksort(int a[], int low, int high) //low:起始位置 high:末尾位置
{
if (low< high) {
int point = getpoint(a, low, high);//计算基准点
quicksort(a, low, point - 1); //对基准点的左边进行排序
quicksort(a, point + 1, high);//对基准点的右边进行排序
}
}
int main()
{
FILE* fin = fopen("D:\\input.txt", "r");
FILE* fout = fopen("D:\\output.txt", "w");
int N; //数组中的元素个数
int a[5000];
int count = 0;//记录一共有多少组数
int i, j;
while (true)
{
fscanf(fin, "%d", &N);
if (N == -1) break;//文件以-1结束
count++;
fprintf(fout, "case %d:%d\n", count, N);
for (i = 0; i< N; i++)
{
fscanf(fin, "%d", &a[i]);
}
quicksort(a, 0, N - 1);
for (j = 0; j< N; j++)
{
fprintf(fout, "%d ", a[j]);
}
fprintf(fout, "\n");
}
fclose(fin);
fclose(fout);
system("pause");
} 运行结果：（当然，题目真正的input.txt是一个巨长无比的文件，为了方便展示我用题干的样例写数据进行测试啦）
算法时间复杂度分析：
最坏情况：每一轮都分不成两组，一共要分n轮
时间复杂度:O(n^2）
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧