首页 > 编程语言 > 详细

快速排序

时间:2018-01-08 16:10:06      阅读:241      评论:0      收藏:0      [点我收藏+]
Description

有n个无序的整数,试把它们从小到大排序。

要求:本题采用快速排序法来完成。

Input

输入共有2行,第一行是一个整数n ( 0 < n ≤ 100000 ),表示有n个整数。

第二行是n个整数。

Output

输出每一次Partition之后的结果。规定每次选取"枢轴",都是选择当前区间的第一个元素。

Sample Input

14
39 80 76 41 13 29 50 78 30 11 100 7 41 86

Sample Output

7 11 30 29 13 39 50 78 41 76 100 80 41 86
7 11 30 29 13 39 50 78 41 76 100 80 41 86
7 11 30 29 13 39 50 78 41 76 100 80 41 86
7 11 13 29 30 39 50 78 41 76 100 80 41 86
7 11 13 29 30 39 50 78 41 76 100 80 41 86
7 11 13 29 30 39 41 41 50 76 100 80 78 86
7 11 13 29 30 39 41 41 50 76 100 80 78 86
7 11 13 29 30 39 41 41 50 76 100 80 78 86
7 11 13 29 30 39 41 41 50 76 86 80 78 100
7 11 13 29 30 39 41 41 50 76 78 80 86 100
7 11 13 29 30 39 41 41 50 76 78 80 86 100

 
#include<iostream>
#include<stdio.h>
using namespace std;
int a[100002];
int n;
void qsort(int p,int r)
{
    if(p>=r)
    {
        return ;
    }
    int x = a[p]; //基准数
    int i = p,j=r;
    while(i!=j)
    {
        while(a[j]>=x&&i<j)j--;a[i]=a[j];
        while(a[i]<=x&&i<j)i++;a[j]=a[i];
    }
    a[i]=x;
    for(int k=1; k<=n; k++)
    {
        cout << a[k] ;
        if(k==n)printf("\n");
        else printf(" ");
    }
    qsort(p,i-1);
    qsort(i+1,r);

}
int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
    }
    qsort(1,n);
    return 0;
}

 

 

快速排序

原文:https://www.cnblogs.com/dichuan/p/8157981.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!