Skip to Content
Problem Solving

2-排序与数字统计

2020-05-18Original-language archivelegacy assets may be incomplete

排序

插入排序

for (int j=2; j<A.size(); ++j){
    auto key = A[j];
    for (int i = j-1; i>0 && A[i]>key; --i)
        A[i + 1] = A[i];
    A[i + 1] = key;
}
  • 循环不变量：每次循环开始前，子数组 A[1..j-1] 有序
  • worst: Θ(n2)\Theta(n^2)
  • average: Θ(n2)\Theta(n^2)

归并排序

void merge_sort(vector<int>& A, int l, int r){
    if (l < r){
        int mid = (l+r)/2;
        merge_sort(vector<int>& A, l, mid);
        merge_sort(vector<int>& A, mid, r);
        merge(A, l, mid, r); // O(r-l)
    }
}
  • worst case: Θ(nlg⁡n)\Theta(n\lg n)
  • average case: Θ(nlg⁡n)\Theta(n\lg n)

堆排序

build_max_heap(A)
for i in range(A.length, 1, -1):
    swap(A[1], A[i])
    A.size -= 1
    max_heapify(A, 1)
  • worst case: O(nlg⁡n)O(n\lg n)
  • not stable

快速排序

def partition(A, p, r):
    x = A[r]
    while (1):
        while (a[i] < x) i+=1
        while (a[j] > x) j-=1
        if (i>=j) break
        swap(a[i], a[j])
    swap(A[r], A[j])
    return j
 
def quicksort(A, p, r):
    if p<r:
        q = Partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)
  • worst case: Θ(n2)\Theta(n^2)
  • average: any split of constant yields O(nlg⁡n)O(n\lg n)
  • expected: Θ(nlg⁡n)\Theta(n\lg n)
    • Xij=[zi compared to zj]X_{ij}=[z_i \text{ compared to } z_j]
    • P(zi compared to zj)=2j−i+1P(z_i \text{ compared to } z_j)=\frac{2}{j-i+1}
  • not stable

线性排序

  • Counting sort: Θ(k+n)\Theta(k+n) (range 0 to k)
  • Radix sort: Θ(d(n+k))\Theta(d(n+k)) (d digits up to k values)
  • Bucket sort: worst Θ(n2)\Theta(n^2), average O(n)O(n) (distributed uniformly and independently over [0,1))

Order statics

快排修改

def random_select(A, p, r, i):
    if p==r:
        return A[p]
    q = random_partion(A, p, r)
    k = q - p + 1
    if i==k:
        return A[q]
    elif i<k:
        return random_select(A,p,q-1,i)
    else
        return random_select(A,q+1,r,i-k)
  • worst: Θ(n2)\Theta(n^2)
  • expected: O(n)O(n)
    • Xk=[∣A[p..q]∣=k]X_k = [|A[p..q]|=k]

方法二

def select(A, p, r, i):
    if p==r:
        return A[p]
    # Get divide point
    A_m = []
    for i in range(p, r, 5):
        A_m += [median(A, i, i+5)]
    q = select(A_m, 0, len(A_m), (r-q+1)/2)
    # Partiion on q
    k = partion_on_q(A, p, r, q)
    if i == k:
        return x
    elif i < k:
        select(A, p, k-1, i)
    else:
        select(A, k+1, r, i-k)
  • worst: O(n)O(n)
    • T(n)≤T(⌈n5⌉)+T(3(⌈12⌈n5⌉⌉−2))+O(n)T(n)\leq T(\lceil\frac{n}{5}\rceil)+T(3(\lceil\frac{1}{2}\lceil\frac{n}{5}\rceil\rceil - 2))+ O(n)