快速排序知识总结

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 const int N = 1e5 + 10;
 6 
 7 int n;
 8 int q[N];
 9 
10 void quick_sort(int q[], int l, int r)
11 {
12     if (l >= r) return;
13 
14     int x = q[(l + r) / 2], i = l - 1, j = r + 1;
15     while (i < j)
16     {
17         do i++; while (q[i] < x);
18         do j--; while (q[j] > x);
19         if (i < j) swap(q[i], q[j]);
20     }
21 
22     quick_sort(q, l, j);
23     quick_sort(q, j + 1, r);
24 }
25 
26 int main()
27 {
28     scanf("%d", &n);
29     for (int i = 0; i < n; i++) scanf("%d", &q[i]);
30 
31     quick_sort(q, 0, n - 1);
32 
33     for (int i = 0; i < n; i++) printf("%d ", q[i]);
34 
35     return 0;
36 }