快速排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
void quick_sort(int *a,int left,int right)
{
    if(left>=right)return;
    swap(a[left],a[(left+right)/2]);
    int i=left,j=right,key=a[left];
    while(i<j)
    {
        while(i<j&&key<a[j])j--;
        if(i<j)a[i++]=a[j];
        while(i<j&&key>a[i])i++;
        if(i<j)a[j--]=a[i];
    }
    a[i]=key;
    quick_sort(a,left,i-1);
    quick_sort(a,i+1,right);
}
int main()
{
    int N,a[100020];
    cin>>N;
    for(int i=0;i<N;i++)
        cin>>a[i];
    quick_sort(a,0,N-1);
    for(int i=0;i<N;i++)
    {
        if(!i)cout<<a[i];
        else cout<<' '<<a[i];
    }
    cout<<endl;
    return 0;
}