部分排序问题
前一段面试腾讯时遇到这样一个问题，有10亿个整型数，要求找出其中最大的1万个并按顺序输出。这其实是典型的部分排序问题（对M个元素中的前N个最大的元素排序），解决这个问题的思路如下：
取前1万数放在一个数组中
对这个数组建立最小堆
依次取后面的元素与堆顶比较，若大于堆顶元素则取代之，并重建最小堆；否则继续向后取
对数组中所有元素进行堆排序
实现代码如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：PartSort.h
* 简要描述：部分排序
*
* 当前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-19
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/
#ifndef PARTSORT_H
#define PARTSORT_H
#define NUM_OF_RESULT 10000
typedef unsigned Type;
void PartSort(FILE *in, FILE *out, int size);
#endif /* PARTSORT_H */
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：PartSort.c
* 简要描述：部分排序
*
* 当前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-19
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/
#include
#include "PartSort.h"
static Type heap[NUM_OF_RESULT];
static void Swap(Type *p, Type *q);
static void HeapSort(int endOfHeap);
static void FilterDown(int start, int endOfHeap);
void PartSort(FILE *in, FILE *out, int size)
{
int i;
int endOfHeap;
Type tmp;
char buf[64];
for (i=0; i
fgets(buf, sizeof(buf), in);
sscanf(buf, "%u", &tmp);
heap[i] = tmp;
}
/* create heap */
endOfHeap = size - 1;
for (i=(endOfHeap-1)/2; i>=0; i--) {
FilterDown(i, endOfHeap);
}
while (fgets(buf, sizeof(buf), in) != NULL) {
sscanf(buf, "%u", &tmp);
if (tmp > heap[0]) {
heap[0] = tmp;
FilterDown(0, endOfHeap);
}
}
HeapSort(endOfHeap);
/* out put the result */
for (i=0; i
fprintf(out, "%u\n", heap[i]);
}
}
static void Swap(Type *p, Type *q)
{
Type tmp;
tmp = *p;
*p = *q;
*q = tmp;
}
static void HeapSort(int endOfHeap)
{
int i;
for (i=endOfHeap; i>0; i--) {
Swap(&heap[0], &heap[i]);
FilterDown(0, i - 1);
}
}
static void FilterDown(int start, int endOfHeap)
{
int i = start;
int j = 2 * i + 1;
Type tmp = heap[i];
while (j
if (j heap[j + 1])
j++;
if (tmp
break;
else {
heap[i] = heap[j];
i = j;
j = 2 * j + 1;
}
}
heap[i] = tmp;
}