最近在补习算法，学一学基础的算法知识

快速排序

快速排序的思路就是从当前的这堆数字里随便挑一个数字x，现在把这个x放在中间，通过某种变化，使得左面<=x，右面>=x能够成立，然后把左右两边也这样排序，递归即可得到最终解。

可以看出算法的步骤如下：

选一个分界数字x（咋选都可以，选第一个数字或者最后一个数字都行，一般选(l+r)/2中值数字）
将所有的数字分组，使得左面<=x，右面>=x（这是这个算法的核心步骤）
左右分别排序，即可得到完整排序

等于x的数字放在哪边实际上是无所谓的，因为快速排序是不稳定算法

那第二步的这个变换怎么操作呢？
一种暴力做法：定义两个数组a和b，将<=x的数字放入a，>x的放入b中，最后a和b排回原数组即可实现。

但是一种常见的优化技巧就是利用双指针实现。
定义i和j，i初始位于最左端，j位于最右端。i应当时刻保证左侧的数字<=x，j时刻保证右侧数字>=x。
操作的时候：

先移动i，直到i当前数字大于x，停止
再移动j，移动至j当前数字小于x，将i与j位置上的数字交换
重复上面两步，直到i和j相遇

快排在手写时应当小心边界情况。

void quickSort(int q[], int l, int r){
    if(l>=r) return;
    int x = q[(l+r+1)/2], 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,i-1);
    quickSort(q,i,r);
}

这种题一定要小心边界情况。常用的数据就是对1 2这组数排序，试试当x=1和x=2程序能不能跑得了，最后两行会不会造成死循环。

归并排序

上面的思路是随便选了一个数当衡量标准，现在我们换个衡量标准，我们直接把一个数组对半切开，分成左半边和右半边。

先把一个数组对半分开，分成左半边和右半边，并分别内部排序，然后归并起来，合二为一，这就是归并排序。
这个排序方法中，合二为一的步骤是核心步骤。

实现方法有多种，还是利用双指针比较方便。
i和j分别从左半边和右半边的第一个位置开始往右走，开一个新数组，判断一下哪边当前位置最小，丢入新开的数组尾部，并把那一边指针往右挪，直到i走到左半边最右端或者j走到右半边最右端。
然后，把左半边或者右半边剩下的元素直接放入新开的数组后面，并把新开的数组里的元素导入到原数组，排序就完毕了。

int tmp[];
void mergeSort(int q[], int l, int r){
    if(l>=r) return;
    int mid = (l+r)>>1;
    mergeSort(q,l,mid); mergeSort(q,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid && j<=r){
        if(q[i]<=q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    for(i=l,j=0;i<=r;i++,j++){
        q[i] = tmp[j];
    }
}