TopK

TopK問題

選択アルゴリズム（英: selection algorithm）とは、数列から k 番目に小さい（あるいは k 番目に大きい）数を探すアルゴリズムである。
Wiki

アルゴリズム

Sort

sort(arr, 1, n);
return arr[1, k];

O(n*lg(n))

Partition Sort

for(i=1 to k){
    bubble_find_max(arr,i);
}
return arr[1, k];

O(n*k)

Heap

heap[k] = make_heap(arr[1, k]);
for(i=k+1 to n){
         adjust_heap(heep[k],arr[i]);
}
return heap[k];

O(n*lg(k))

Quick Sort

void quick_sort(int[]arr, int low, inthigh){
         if(low== high) return;
         int i = partition(arr, low, high);
         quick_sort(arr, low, i-1);
         quick_sort(arr, i+1, high);
}

O(n*lg(n))

Binary Search

int BS(int[]arr, int low, inthigh, int target){
         if(low> high) return -1;
         mid= (low+high)/2;
         if(arr[mid]== target) return mid;
         if(arr[mid]> target)
                   return BS(arr, low, mid-1, target);
         else
                   return BS(arr, mid+1, high, target);
}

O(lg(n))

Randomized Select

int RS(arr, low, high, k){
  if(low== high) return arr[low];
  i= partition(arr, low, high);
  temp= i-low; //数组前半部分元素个数
  if(temp>=k)
      return RS(arr, low, i-1, k); 
  else
      return RS(arr, i+1, high, k-i); 

}

O(n)