Tag Archives: kth

算法技术手册 - 排序 - 求第K大的数

借助刚才的划分算法,我们可以比较容易的求出第K大的数,平均性能为O(N),最坏可能是O(N^2)。

注意关于idx的选择,随机的话效果会比选left、right和median好,如果数据不是很特殊的化。
#include <stdio.h>

typedef int TYPE;

int cmp(TYPE a, TYPE b)
{
return a - b;
}

void swap(TYPE* a, TYPE* b)
{
TYPE tm[......]

继续阅读