经典快速排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| void quick_sort(int q[], int l, int r) { if(l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while(i < j) { do i++; while(q[i] < x); do j--; while(q[j] > x); if(i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r); }
|
完整代码
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
| #include<iostream> #include<cstdio> using namespace std;
const int N = 1e6; int n; int q[N];
void quick_sort(int q[], int l, int r){ if(l >= r) return; int x = q[l+r >> 1], i = l-1, j = r+1; while(i < j){ do i++; while(q[i]<x); do j--; while(q[j]>x); if(i<j) swap(q[i],q[j]); } quick_sort(q, l, j); quick_sort(q, j+1, r); }
int main(){ scanf("%d",&n); for(int i = 0; i < n; i++) scanf("%d", &q[i]); quick_sort(q, 0, n-1); for(int i = 0; i < n; i++) printf("%d ", q[i]); return 0; }
|
注意x的取值与边界问题,背一种模板即可,
若x=q[l],则必须为quick_sort(q, l, j),quick_sort(q, j+1, r);
若x=q[r],则必须为quick_sort(q, l, i-1),quick_sort(q, i, r);