部分排序问题

来源:百度文库 编辑:神马文学网 时间:2024/03/29 15:29:18
 
前一段面试腾讯时遇到这样一个问题,有10亿个整型数,要求找出其中最大的1万个并按顺序输出。这其实是典型的部分排序问题(对M个元素中的前N个最大的元素排序),解决这个问题的思路如下:
  1. 取前1万数放在一个数组中
  2. 对这个数组建立最小堆
  3. 依次取后面的元素与堆顶比较,若大于堆顶元素则取代之,并重建最小堆;否则继续向后取
  4. 对数组中所有元素进行堆排序

实现代码如下:

/******************************************************************
* 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 <= 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;
}