DS排序--快速排序

题目描述

给出一个数据序列，使用快速排序算法进行从小到大的排序

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入

第一行输入t，表示有t个测试示例
第二行输入n，表示第一个示例有n个数据
第三行输入n个数据，都是正整数，数据之间用空格隔开
以此类推

输出

每组测试数据，输出每趟快排的结果，即每次排好一个数字结果（长度为1的子序列，不用排，不用输出）。不同测试数据间用空行分隔。

样例输入

26111 22 6 444 333 55877 555 33 1 444 77 666 2222

样例输出

55 22 6 111 333 4446 22 55 111 333 4446 22 55 111 333 4446 22 55 111 333 4441 33 77 555 444 77 666 22221 33 77 555 444 77 666 22221 33 77 77 444 555 666 22221 33 77 77 444 555 666 22221 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;
}