基础算法

快速排序（QuickSort）

算法思想：

• 首先设置一个分界值 pivot，通过该分界值将数组分成左右两个部分 partition，将小于分界值的数据集中到数组左边、大于或等于分界值的数据集中到数组右边。此时左边部分中个元素都小于或等于分界值，而右边各部分中的元素都大于或等于分界值。
• 将上面分割的区间继续分割 递归执行此步骤，直至不能再划分为止。

代码实现：

void quickSort(vector<int> &a, int l, int r) {
    if (l > r)  return ;
    int mid = l + r >> 1;
    int x = a[mid];
    int i = l - 1, j = r + 1;
    while(i < j) {
        do i ++; while(a[i] < x);
        do j --; while(a[j] > x);
        if (i < j)  swap(a[i], a[j]);
    }
    quickSort(a, l, i - 1);
    quickSort(a, j + 1, r);
}

归并排序（MergeSort）

算法思想：

分：先递归将数组分成只有一个元素的有序数组。

治：合二为一：将两个有序数组合并成一个有序数组。

代码实现：

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