部分排序问题 - 笔试题目 - Welcome to my blog
前一段面试腾讯时遇到这样一个问题,有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
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
}
}
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 <= endOfHeap) {
if (j < endOfHeap && heap[j] > heap[j + 1])
j++;
if (tmp <= heap[j])
break;
else {
heap[i] = heap[j];
i = j;
j = 2 * j + 1;
}
}
heap[i] = tmp;
}