快速选择问题 - 笔试题目 - Welcome to my blog

快速选择问题
快速选择问题有如下两种常见的形式：
1、数组S中有M个元素，从中选出第N小（或大）的元素
2、数组S中有M个元素，从中选出前N个最小（或大）的元素
如果先对数组S做排序的话时间复杂度最低为O(MlongM)。当N远小于M时，这样做效率很低，因为存在很多多余的排序。这里介绍一个解决此类问题的经典算法，它由快速排序类比得到，可以在O(M+NlogM)的时间内完成。
算法思想：
设|S|为数组S中的元素个数。
1、如果|S|〈＝CUTOFF（注），则对S进行直接插入排序，排序后算法结束；否则转到2。
2、在S中选择一个比较的基准元素，即pivot。
3、把S分成两部分S1和S2，S1中的元素全部小于或等于pivot，S2中的元素则全部大于或等于pivot。
4、如果N〈＝|S1|，则第N小的元素一定在S1中，这时quickselect(S1, N)；如果N>1+|S1|，则第N小的元素一定在S2中，这时quickselect(S2, k-|S1|-1)；否则，算法结束。
算法结束后，第N个元素即为第N小的元素，前N个元素即为前N个最小的元素。
C语言实现代码如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：QuickSelect.h
* 简要描述：快速选择问题
*
* 当前版本：1.0
* 作    者：raincatss
* 完成日期：2007-11-17
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/
#ifndef QUICKSELECT_H
#define QUICKSELECT_H
#define CUT_OFF 10
void QuickSelect(int a[], int k, int left, int right);
int  MedianThree(int a[], int left, int right);
void InsertionSort(int a[], int n);
void Swap(int *p, int *q);
#endif /* QUICKSELECT_H */
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：QuickSelect.c
* 简要描述：快速选择问题
*
* 当前版本：1.0
* 作    者：raincatss
* 完成日期：2007-11-17
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/
#include "QuickSelect.h"
void QuickSelect(int a[], int k, int left, int right)
{
int i, j;
int pivot;
if (left + CUT_OFF <= right) {
pivot = MedianThree(a, left, right);
i = left;
j = right - 1;
for ( ; ; ) {
while (a[++i] < pivot)
;
while (a[--j] > pivot)
;
if (i < j) {
Swap(&a[i], &a[j]);
} else {
break;
}
}
Swap(&a[i], &a[right - 1]);
if (k <= i) {
QuickSelect(a, k, left, i - 1);
} else if (k > i + 1) {
QuickSelect(a, k, i + 1, right);
}
} else {
InsertionSort(a + left, right - left + 1);
}
}
int MedianThree(int a[], int left, int right)
{
int center = (left + right) / 2;
/* a[left] <= a[center] <= a[right] */
if (a[left] > a[center]) {
Swap(&a[left], &a[center]);
}
if (a[left] > a[right]) {
Swap(&a[left], &a[right]);
}
if (a[center] > a[right]) {
Swap(&a[center], &a[right]);
}
Swap(&a[center], &a[right - 1]);
return a[right - 1];
}
void InsertionSort(int a[], int n)
{
int i, p;
int tmp;
for (p=1; ptmp = a[p];
for (i=p; i>0&&a[i-1]>tmp; i--) {
a[i] = a[i - 1];
}
a[i] = tmp;
}
}
void Swap(int *p, int *q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：QS_Test.c
* 简要描述：快速选择问题
*
* 当前版本：1.0
* 作    者：raincatss
* 完成日期：2007-11-17
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/
#include
#include
#include "QuickSelect.h"
#define ARRAY_SIZE    50
#define KTH_LARGEST    20
int main(int argc, char *argv[])
{
int i;
int a[ARRAY_SIZE];
/* 用随机数填充数组 */
for (i=0; ia[i] = rand() % 1000;
}
printf("Before select...\n");
for (i=0; iprintf("%3d%s", a[i], ((i + 1) % 10 != 0) ? " " : "\n");
}
QuickSelect(a, KTH_LARGEST, 0, ARRAY_SIZE - 1);
printf("After select...\n");
for (i=0; iprintf("%3d%s", a[i], ((i + 1) % 10 != 0) ? " " : "\n");
}
return 0;
}
注：同快速排序一样，快速选择也是递归的，当数据量比较少时效果并没有直接插入排序好，所以根据数据量的多少选择合适的算法。设分界点为CUTOFF，当5〈＝CUTOFF〈＝20时效果相差不大，但一般取CUTOFF＝10，之所以取10是建立在统计实验的基础上。
参考文献：Mark Allen Weiss, "Data Structures and Algorithm Analysis in C(Second Edition)," 陈越改编。北京：人民邮电出版社，2005