P.Linux Laboratory

本文内容遵从CC版权协议, 可以随意转载, 但必须以超链接形式标明文章原始出处和作者信息及版权声明
网址: http://www.penglixun.com/tech/program/dichotomy_topk_cpp.html

在Jacky一篇关于Oracle排序算法的文章中，讨论了下Oracle的Short sort算法。文章中对此算法有详细描述，这里不赘述，大致就是通过Heap来实现。
虽然Heap在处理优先队列类型的问题上很有优势，但是我一致觉得它不太适合做排序，调堆的代价其实是比较高的，每加入一个元素删除一个元素都要调堆。
对于TopK的问题，我还是觉得二分法实现比较好。首先按快排的算法把数据分成两堆，左大右小，再判断左边的大堆是不是数量小于了K，小于了了就使用上次的右边界进入排序流程，不到则继续二分。
程序如下：

#include 
#include 
#include 
#include 
#define MAXN 10000
#define LIMIT 500

int a[MAXN];
int last;
int count_sw, count_cmp;

//初始化测试数据
void init () {
	srand(time(0));
	//参与查询的数据
	for(int i=0; i mid) count_cmp++;
			while (arr[--j] < mid) count_cmp++;
			if(i>=j) break;
			swap(arr[i], arr[j]);
			count_sw++;
		}
		qsort (arr, start, i-1);
		qsort (arr, j+1, end);
	}
	return ;
}

void topK(int arr[], int start, int end, int k) {
	if(start < end) {
		int mid = arr[rand()%(end-start) + start];
		int i = start - 1;
		int j = end + 1;
		while (true) {
			while (arr[++i] > mid) count_cmp++;
			while (arr[--j] < mid) count_cmp++;
			if(i>=j) break;
			swap(arr[i], arr[j]);
			count_sw++;
		}
		if(i-start > k) {
			last = i-1;
			topK (arr, start, i-1, k);
		} else{
			qsort(arr, start, last);
		}
	}
	return ;
}

int main() {
	init();
	count_sw = 0;
	count_cmp = 0;
	topK(c, 0, MAXN-1,10);
	cout << "Result:" << MAXN << endl;
	for(int i=0; i<10; ++i) {
		cout << c[i] << endl;
	}
	cout << "Swaps:" << count_sw << endl;
	cout << "Campare:" << count_cmp << endl;
	return 0;
}

测试结果比Heap要好一些。