快速排序

Posted on | Edited on | In | Comments:

参考链接：快速排序

代码

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
34
#include <bits/stdc++.h>
using namespace std;

int n;
int a[1000];

void quickSort(int a[], int left, int right){
    if (left > right)   return ;
    int i = left, j = right;
    int splitNum = a[i];
    while (i != j) {
        while (a[j]>=splitNum && i<j)  j--;
        while (a[i]<=splitNum && i<j)   i++;
        if (i<j) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    a[left] = a[i];
    a[i] = splitNum;
    quickSort(a, left, i-1);
    quickSort(a, i+1, right);
}

int main() {
    while (cin >>n) {
        for (int i = 0; i<n; i++)   cin >>a[i];
        quickSort(a, 0, n-1);
        for (int i = 0; i<n; i++)   cout << a[i] << "   " ;
        cout << endl;
    }
    return 0;
}