Top K有关问题（求前k个最大的数）

Top K问题（求前k个最大的数）

最近在笔试的时候经常会遇到求前k个最大的数的算法，查阅了一些资料，总结如下：

在数据不多的情况下采用快速排序，在海量数据下则采用堆排序。

以下将针对这两种方法给出详细的实现代码，希望能帮到大家，顺便替自己复习一下，如果发现有错的，欢迎指正。

一、快速实现前k个最大数据的排序，总数据为n个

1、以下的partition函数对线性表从low到high进行一趟快速排序

int partition(SqList &L,int low,int high){
//交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大（小）于它。
 temp=L.r[low];//记录子表的第一个记录作枢轴记录
int pivotkey=L.r[low].key;//枢轴记录关键字
while(low<high){//从表的两端交替地向中间扫描
       while(low<high&&L.r[high].key>=pivotkey) --high;
L.r[low]=L.r[high];
      while(low<high&&L.r[low].key<=pivotkey) ++low;
L.r[high]=L.r[low];
}
L.r[low]=temp;//枢轴记录到位
//只有在一趟排序结束时，即low=high的位置才是枢轴记录的最后位置
return low;//返回枢轴位置
}

2、以下的QSort函数对从low到high进行快速排序

void QSort(SqList &L,int low,int high){
//对顺序表L中的子序列L.r[low..high]作快速排序
if(low<high){
pivotloc =partition(L,low,high);
Qsort(L,low,pivotloc-1);
Qsort(L,pivotloc+1,high);
}
}

3、KSort对线性表的前k个最大数进行排序

void KSort(SqList &L,int low,int high,int k){

int pi=partition(L,low,high);

while(pi>=k+1)
pi=partition(L,low,pi-1);
//找出小于k的分界点，对低值表进行快排，对高值表继续递归
if(pi==k)
QSort(L,low,k-1);
if(pi==k+1)
Qsort(L,low,k);
else{
QSort(L,low,pi-1);
KSort(L,pi+1,high,k);
}
}

4、对线性表前k个的则表示为

KSort(L,0,n,k);

二、堆排序实现前k个最大数据的排序，总数据为n个

堆排序其实就是对一个最大（小）堆”反复筛选“的过程

大顶堆排序后变成从小到大

1、以下HeapAdjust函数实现筛选算法

typedef SqList HeapType;//采用顺序表存储堆

void HeapAdjust(HeapType &H,int s,int m){
//已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义（即堆出元素之后的状况）

temp=H.r[s];
for(int j=2*s; j<=m;j*=2){//沿key较大的孩子结点向下筛选
if(j<m&&H.r[j].key<H.r[j+1].key) ++j;//j为较大 的孩子结点下标
if(temp>=H.r[j].key) break;//不变
//否则
H.r[s]=H.r[j]; s=j;
}
H.r[s]=temp;//插入
}

2、HeapSort函数实现堆排序算法

void HeapSort(HeapType &H){

for(int i=H.length/2;i>0;--i)
HeapAdjust(H,i,H.length);//把H.r[1..H.length]建成大顶堆,从非终端结点开始

for(int i=H.length;i>1;--i)
H.r[1]<——>H.r[i];//将堆顶元素和当前未经排序子序列H[1..i]中最后一个记录相互交换

HeapAdjust(H,1,i-1);//将H.r[1..i-1]重新调整为大顶堆
}
}

3、堆排序算法实现前k个最大的数

void KHeapSort(HeapType &H){

for(int i=H.length/2;i>0;--i)
HeapAdjust(H,i,H.length);//把H.r[1..H.length]建成大顶堆,从非终端结点开始

for(int i=H.length;i>H.length-k;--i)
H.r[1]<——>H.r[i];//将堆顶元素和当前未经排序子序列H[1..i]中最后一个记录相互交换

HeapAdjust(H,1,i-1);//将H.r[1..i-1]重新调整为大顶堆
}
}

该线性表的最后k个数即为最大的k个数