复试准备

快速排序

优点：
好写
局部性好
空间复杂度平均为Ologn)

缺点：
不稳定
朴素地选择第一个元素或者最后一个元素容易退化
选择中间的元素不容易退化，但是对特定的序列仍然有可能退化

优势在于局部性原理，相邻几次调整的区间都几乎涉及同一片内存，所以比归并排序以及堆排序更优。

挺好记的。为什么要写>=呢，防止传入一个空数组的情况。

void QuickSortint *a, int l, int r) {
    ifl >= r)
        return;
    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    whilei < j) {
        whilea[++i] < x);
        whilea[--j] > x);
        ifi < j)
            swapa[i], a[j]);
    }
    QuickSorta, l, j);
    QuickSorta, j + 1, r);
    return;
}

int KthElementint *a, int l, int r, int k) {
    ifl >= r)
        return a[l];
    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    whilei < j) {
        whilea[++i] < x);
        whilea[--j] > x);
        ifi < j)
            swapa[i], a[j]);
    }
    ifj - l + 1 >= k)
        return KthElementa, l, j, k);
    else
        return KthElementa, j + 1, r, k - j - l + 1));
}

堆排序

优点：
空间复杂度为O1)
时间复杂度稳定为Onlogn)

缺点：
不稳定
需要非常有效率的随机存取

归并排序

优点：
非常容易改用于链表排序
外部排序
稳定
时间复杂度稳定为Onlogn)

缺点：
空间复杂度为On)
需要非常有效率的随机存取