快速排序的主要思想——分治（顾名思义：分别治理）
思路
1.确定分界点
找分界点有四种：最左端、最右端、中间数、随机数
2.调整区间
找到临界点，调整两个区间，使得：
左区间<=X 右区间>=X
分界点的数不一定是x！！！
方法1：
①开两个数组a[ ] b[ ];
②扫描整个要排序的区间q[ ]，若当前的数<=x,放入a[ ],>x放入b[ ];
③先把a[ ]中的数放入q[ ],再把b[ ]中的数放入q[ ]中。方法2：
①分别在整个要排序的区间的左右两端放入指针：左指针和右指针
② 当左指针指向的数字<X时，指针往右移动一个再比较，直到>X,停止移动；当右指针指向的数字>于X时，往左移动一个再比较，直到<X,停止移动
③当指针都停止时，交换指针所指的数，再移动一个，继续重复以上操作，直至两指针重合交叠3.递归排序左右区间
只要左右两区间都排好，所有的都排好了。
因为左区间<=X 右区间>=X
例题
题解
#include <iostream> #include<bits/stdc++.h> using namespace std;const int N = 100010; int q[N];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); }int main() {int n;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; }
