首页 > 代码库 > ACM——快速排序法

ACM——快速排序法

快速排序

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:653            测试通过:297

描述

 

给定输入排序元素数目n和相应的n个元素,写出程序,利用内排序算法中快速排序算法进行排序,并输出排序最后结果的相应序列。

 

输入

 

共两行,第一行给出排序元素数目n,第二行给出n个元素,1≤n≤100000,每个元素值范围为 [0,100000)

 

输出

 

一行,输出排序结果。

 

样例输入

7
48 36 68 72 12 48 2

样例输出

2 12 36 48 48 68 72

提示

 数据结构A实验四

题目来源

CHENZ

 

//快速排序#include<iostream>using namespace std;int* l;void Swap(int &a,int &b){    int temp=a;    a=b;    b=temp;}int Partition(int left,int right){    int i=left,j=right+1;    do    {        do i++;while(l[i]<l[left]);        do j--;while(l[j]>l[left]);        if(i<j) Swap(l[i],l[j]);    }while(i<j);    Swap(l[left],l[j]);    return j;}void QuickSort(int left,int right){    if(left<right)    {        int j=Partition(left,right);        QuickSort(left,j-1);        QuickSort(j+1,right);    }}int main(){    int N,i;    cin>>N;    l=new int[N];    for(i=0;i<N;i++)        cin>>l[i];    QuickSort(0,N-1);    for(i=0;i<N;i++)    {        cout<<l[i];        if(i<N-1) cout<<" ";//此处oj格式要求    }    return 0;}