神马文学网快速选择问题 - 笔试题目 - Welcome to my blog
来源：百度文库 编辑：神马文学网 时间：2024/04/29 18:10:59
快速选择问题有如下两种常见的形式： 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; 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; i
}
printf("Before select...\n");
for (i=0; i
}
QuickSelect(a, KTH_LARGEST, 0, ARRAY_SIZE - 1);
printf("After select...\n");
for (i=0; i
}
return 0;
}
注：同快速排序一样，快速选择也是递归的，当数据量比较少时效果并没有直接插入排序好，所以根据数据量的多少选择合适的算法。设分界点为CUTOFF，当5〈＝CUTOFF〈＝20时效果相差不大，但一般取CUTOFF＝10，之所以取10是建立在统计实验的基础上。
参考文献：Mark Allen Weiss, "Data Structures and Algorithm Analysis in C(Second Edition)," 陈越改编。北京：人民邮电出版社，2005