排序算法千千万，快排虐我千万遍！！！能够完成这道题的排序算法很多，这里主要学习快速排序。

我爱思考

• 有一个特殊的数组，他由左右两部分组成，并且右边部分的数字都大于等于左边数组中的数字。如下图：

若果分别将数组的左半部分排好序，右半部分排好序，整个数组就有序了。

• 可以得出一个结论：将一个无需数组分成左右两部分，右边部中的每个树大于等于左边部分中的每个数。将左右部分分别排好序，整个数组就有序了。
• 可以得出这样一个排序算法：这个算法会先将数组分成左右两部分，保证右半部分中的每个数大于等于左半部分中的每个数，然后分别对左右部分数组使用该算法排好序，那么整个数组就排好序了。

快速排序由C. A. R. Hoare在1962年提出。

它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1. 快排的思想是分治
2. 我们有一个待排序的数组，长度为n。选定一个基准，将数组分成左右两部分，左边的数小于基准，右边的数大于基准。
3. 然后我们分别看分割后左右两部分数组，如果元素个数大于1，就再次分割。
4. 直到最后，我们得到了n个数组，每个数组含有1个元素。
5. 这n个数组中，每两个挨着的，都是排好序的，所以整体有序。
6. 最好情况下，每次将原来的数组分成两份，第二次将两份成四份....最后一个元素一份。每次分割是O(n),
7. 假设分割次数为k，则2的k次方等于n，k = logn。每次分割的总时间复杂度是O(n)，所以说，平均复杂度是O(n*logn)。
8. 最坏就是原数组有序，每次只能分割开1个元素，需要分割n次，时间复杂度是O(n^2)。
   

快排思路

1. 首先设定一个分界值(基准值)，通过该分界值将数组分成左右两部分。
2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
3. 左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

代码

/*
快排写法千千万，
边界处理难又难，
大神算法背下来，
乐无边呀乐无边
*/
#include<iostream>
using namespace std;
int a[100010];
int n;
void quickSort(int a[], int l, int r){
    //如果数组中就一个数，就已经排好了，直接返回。
    if(l >= r) return;
    //选取分界线。这里选数组中间那个数
    int x = a[l + r >> 1];
    int i = l - 1, j = r + 1;
    //划分成左右两个部分
    while(i < j){
        while(a[++i] < x);
        while(a[--j] > x);
        if(i < j){
            swap(a[i], a[j]);
        }
    }
    //对左部分排序
    quickSort(a, l, j);
    //对右部分排序
    quickSort(a, j + 1, r);
}

int main(){
    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] << " ";
    }
}

重要的建议：快排算法划分的边界处理很很麻烦，找一个神的写好的，背下来。