快速排序
快速排序运用了分治的思想
分治法解题的一般步骤： （1）分解，将要解决的问题划分成若干规模较小的同类问题； （2）求解，当子问题划分得足够小时，用较简单的方法解决； （3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。#includeusing namespace std; const int N = 1e6; int q[N]; void quickSort(int q[], int l, int r) { if (l >= r) return; int x = q[l], 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]); } quickSort(q, l, j); quickSort(q, j + 1,r); } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &q[i]); quickSort(q, 0, n - 1); for (int i = 0; i < n; i++) printf("%d ", q[i]); return 0; }