Comparison-based sorting

最优Runtime为Ω(n log n)

QuickSelect

用QuickSort algorithm快速查找第k大的数 (avg rumtime: Θ(n))

组成函数

• choose-pivot(A) 在数据中选择其中一个作为pivot
• partition(A, p) 使用A[p]作为pivot, 将A中的数据分为
  
  
  • 所有小于等于pivot的数据
  • pivot本身
  • 所有大于pivot的数据

Implementation

下载: quickselect.cc

void swap(int *A, int i, int j){ 
    int temp; 
    temp = A[i]; 
    A[i] = A[j]; 
    A[j] = temp; 
    return; 
}

Read more...