题目描述
给出一个数据序列,使用快速排序算法进行从小到大的排序
--程序要求--
若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件,不看代码,作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
第一行输入t,表示有t个测试示例
第二行输入n,表示第一个示例有n个数据
第三行输入n个数据,都是正整数,数据之间用空格隔开
以此类推
输出
每组测试数据,输出每趟快排的结果,即每次排好一个数字结果(长度为1的子序列,不用排,不用输出)。不同测试数据间用空行分隔。
样例输入
2 6 111 22 6 444 333 55 8 77 555 33 1 444 77 666 2222样例输出
55 22 6 111 333 444 6 22 55 111 333 444 6 22 55 111 333 444 6 22 55 111 333 444 1 33 77 555 444 77 666 2222 1 33 77 555 444 77 666 2222 1 33 77 77 444 555 666 2222 1 33 77 77 444 555 666 2222 1 33 77 77 444 555 666 2222提示
#include<iostream> using namespace std; int n; int Partition(int *array,int low,int high) { int mid_key=array[low];///记录枢轴的值 while(low<high) { while(low<high&&array[high]>=mid_key) { high--; }///找到小的退出 array[low]=array[high];///小于枢轴的值前移 while(low<high&&array[low]<=mid_key) { low++; }///找到大的退出 array[high]=array[low];///大于枢轴的值后移 }///循环结束,low=high时退出 array[low]=mid_key;///最后将枢轴的值记录到位 return low;///返回枢轴的位置 } void printarray(int *array) { for(int i=0;i<n;i++) { if(i!=n-1) cout<<array[i]<<" "; else cout<<array[i]<<endl; } } void Quicksort(int *array,int low,int high) { if(low<high) { int loc=Partition(array,low,high); printarray(array); Quicksort(array,low,loc-1);//将数组分成[low,loc-1]和[loc+1,high]两个区间 Quicksort(array,loc+1,high); } } int main() { int T; cin>>T; while(T--) { cin>>n; int *array=new int[n]; for(int i=0;i<n;i++) cin>>array[i]; int low=0; int high=n-1; Quicksort(array,low,high); delete []array; cout<<endl; } return 0; }