堆排序\链表实现局部排序
以前面试时被问一个问题：有10万个乱序的数，要前5个最大(或最小)的数？
作为一个没好好学算法的人，还没有算法时间、空间复杂度的概念，只提出了冒泡、快速排序等，然后取前5。这显然不是合理的做法。
读了几本书，有一点点心得，下面介绍两个做法：
假设：输入为[31,5,12,24,41,63,7,61,42,21,9,123,24...] ,总数为N=100000，要求前M=5个最大的数
- 对10万个建立二叉堆，然后应用堆排序5次，即取出前5个最大(或最小)的数。
只是一个可行的方法，在此不敖述，具体可参见《数据结构与算法分析:C语言描述》、《数据结构(C语言版)》严蔚敏等书中的堆排序。 - 考虑：能否维护一个数据结构用来存储排好序的5个数，要求如果输入数大于5个中最小的数，就将其插入至正确位置，并删除最小的数。这样对输入进行一次遍历，即可找出最大的5个数。
此处想到的是用单链表，首先对输入中前5个数字升序排序，插入空的链表中。
//简单冒泡排序，输入少，对整体性能影响可忽略不计
for(int j=1; j<M; j++){
for(int k=0; k<M-j; k++){
if(input[k]>input[k+1]){
tmp = input[k];
input[k] = input[k+1];
input[k+1]=tmp;
}
}
}
for(int i=0; i<M; i++){
Insert(input[i],L,P);//依次插入链表
P = P->Next;
}
Position Tmp,TmpCell;
for( ; i<N; i++){ //对其余输入进行一次遍历
P = Header(L); //表头
do{
Tmp = P;//暂存前驱元,保存位置
P = P->Next;//第一个元素
if( input[i] <= P->Value ){ //小于第一个元素或者后面的某一个元素
if(P != L->Next){ //input[i]大小介于第一个元素与此位置的元素
Insert(in[i],L1,Tmp); //插入
TmpCell = L1->Next;
L1->Next = TmpCell->Next;
free( TmpCell ); //挤出第一个元素，也就是5+1=6个中最小的元素
}
break;
}else if(input[i] > P->Value && IsLast( P, L )){ //如果大于最后一个(也就是最大的)元素
Insert(in[i],L,P); //插入到最后
TmpCell = L->Next; L->Next = TmpCell->Next; free(TmpCell); //删除第一个元素(6个中最小的)
break;
}
} while( !IsLast(P, L) );
}
插入可能是这样的：
删除首元可能是这样的：
小结：当输入大数据量，而只需前m个最大(最小)值时，应用链表不失为一个好办法，它只对输入进行一次遍历，时间复杂度O(N),空间也只不过额外是一个含6个元素的链表大小而已。
欢迎指教。
