Sort

快排

void quickSort(vector<int>& v, int begin, int end) {
    int m = partition(v, begin, end);
    quickSort(v, begin, m - 1);
    quickSort(v, m + 1, end);
}

这里是拿nums[left]作为pivot，从大到小排，退出时r一定在左半区最右边，可以和pivot换

要点就是选左边，从右边开始排

int partition(vector<int>& nums, int left, int right) {
    int r = right, pivot = nums[left];
    for (int i = right; i > left; i --)
        if (nums[i] > pivot) swap(nums[r --], nums[i]);
    swap(nums[left], nums[r]);
    return r;
}

题目

148. Sort List (Medium)

215. Kth Largest Element in an Array (Medium)

---

归并排序

mergeSort(A, p, r):
    q = (p+r)/2
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

# merge A[p, q] and A[q+1, r]
merge(A, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    let L[1 ... n1+1] and R[1 ... n2+1] be new arrays
    for i = 1 to n1 : L[i] = A[p + i - 1]
    for j = 1 to n2 : R[j] = A[q + j]
    L[n1+1] = R[n2+1] = inf
    i = j = 1
    for k = p to r:
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

题目

148. Sort List (Medium)

---

插入排序 (Insertion Sort)

类似于扑克牌整牌，第i次循环将第i张牌插入到前i-1已经排好的牌中

void insertionSort(vector<int>& v) {
    for (int i = 1; i < v.size(); i ++) {
        int key = v[i], j = i - 1;
        while (j > 0 && v[j] > key) {
            v[j + 1] = v[j];
            j --;
        }
        v[j + 1] = key;
    }
}

147. Insertion Sort List (Medium)

---

基数排序 (Radix Sort)

时间复杂度为$O(d(n+b))$，$n$是数组长度，$b$是进制，$d$是执行次数，即$log_bm$，$m$是数组最大值。因为一共执行d遍计数排序，每次扫描一遍数组，再扫描一遍进制计数

空间复杂度为$O(n+b)$，因为要维持一个和数组等长的buffer，还要维持一个进制数组

基数排序即从末尾位开始进行排序，每次按一位来排，但就需要所有数都是非负数，或者最后再按符号来执行一遍排序

如下例子 170 45 75 90 802 24 2 66

先按个位排序 170 90 802 2 24 45 75 66

再按十位排序 802 2 24 45 66 170 75 90

再按最高位排序 2 24 45 66 75 90 170 802

按符号排序的方法是，维护一个进制数组，如10进制就维护0-9，记录数组里这一位数字出现个数，如果没有这位记为0。然后再累加起来，即可以得到每一位数字应该出现的区域，最后再排列起来，即计数排序