快速选择SELECT算法的实现

本节，咱们将依据下图所示的步骤，采取中位数的中位数选取枢纽元的方法来实现此SELECT算法，不过，在实现之前，有个细节我还是必须要提醒你，即上文中2.2节开头处所述，“数组元素索引是从“0...i”开始计数的，所以第k小的元素应该是返回a[i]=a[k-1].即k-1=i。换句话就是说，第k小元素，实际上应该在数组中对应下标为k-1”这句话，我想，你应该明白了：返回数组中第k小的元素，实际上就是返回数组中的元素array[i]，即array[k-1]。ok，最后请看此快速选择SELECT算法的完整代码实现（据我所知，在此之前，从没有人采取中位数的中位数选取枢纽元的方法来实现过这个SELECT算法）：//copyright@ yansha && July && 飞羽
//July、updated，2011.05.19.清晨。
//版权所有，引用必须注明出处：http://www.linuxidc.com。
#include <iostream>
#include <time.h>
using namespace std;

const int num_array = 13;
const int num_med_array = num_array / 5 + 1;
int array[num_array];
int midian_array[num_med_array];

//冒泡排序（晚些时候将修正为插入排序）
/*void insert_sort（int array[], int left, int loop_times, int compare_times）
{
for （int i = 0; i < loop_times; i++）
{
for （int j = 0; j < compare_times - i; j++）
{
if （array[left + j] > array[left + j + 1]）
swap（array[left + j], array[left + j + 1]）;
}
}
}*/

/*
//插入排序算法伪代码
INSERTION-SORT（A） cost times
1 for j ← 2 to length[A] c1 n
2 do key ← A[j] c2 n - 1
3 Insert A[j] into the sorted sequence A[1 ‥ j - 1]. 0...n - 1
4 i ← j - 1 c4 n - 1
5 while i > 0 and A[i] > key c5
6 do A[i + 1] ← A[i] c6
7 i ← i - 1 c7
8 A[i + 1] ← key c8 n - 1
*/
//已修正为插入排序，如下：
void insert_sort（int array[], int left, int loop_times）
{
for （int j = left; j < left+loop_times; j++）
{
int key = array[j];
int i = j-1;
while （ i>left && array[i]>key ）
{
array[i+1] = array[i];
i--;
}
array[i+1] = key;
}
}

int find_median（int array[], int left, int right）
{
if （left == right）
return array[left];

int index;
for （index = left; index < right - 5; index += 5）
{
insert_sort（array, index, 4）;
int num = index - left;
midian_array[num / 5] = array[index + 2];
}

// 处理剩余元素
int remain_num = right - index + 1;
if （remain_num > 0）
{
insert_sort（array, index, remain_num - 1）;
int num = index - left;
midian_array[num / 5] = array[index + remain_num / 2];
}

int elem_aux_array = （right - left） / 5 - 1;
if （（right - left） % 5 ！= 0）
elem_aux_array++;

// 如果剩余一个元素返回，否则继续递归
if （elem_aux_array == 0）
return midian_array[0];
else
return find_median（midian_array, 0, elem_aux_array）;
}

// 寻找中位数的所在位置
int find_index（int array[], int left, int right, int median）
{
for （int i = left; i <= right; i++）
{
if （array[i] == median）
return i;
}
return -1;
}

int q_select（int array[], int left, int right, int k）
{
// 寻找中位数的中位数
int median = find_median（array, left, right）;

// 将中位数的中位数与最右元素交换
int index = find_index（array, left, right, median）;
swap（array[index], array[right]）;

int pivot = array[right];

// 申请两个移动指针并初始化
int i = left;
int j = right - 1;

// 根据枢纽元素的值对数组进行一次划分
while （true）
{
while（array[i] < pivot）
i++;
while（array[j] > pivot）
j--;
if （i < j）
swap（array[i], array[j]）;
else
break;
}
swap（array[i], array[right]）;

/* 对三种情况进行处理：（m = i - left + 1）
1、如果m=k，即返回的主元即为我们要找的第k小的元素，那么直接返回主元a[i]即可;
2、如果m>k，那么接下来要到低区间A[0....m-1]中寻找，丢掉高区间;
3、如果m<k，那么接下来要到高区间A[m+1...n-1]中寻找，丢掉低区间。
*/
int m = i - left + 1;
if （m == k）
return array[i];
else if（m > k）
//上条语句相当于if（（i-left+1） >k），即if（（i-left） > k-1 ），于此就与2.2节里的代码实现一、二相对应起来了。
return q_select（array, left, i - 1, k）;
else
return q_select（array, i + 1, right, k - m）;
}

int main（）
{
//srand（unsigned（time（NULL）））;
//for （int j = 0; j < num_array; j++）
//array[j] = rand（）;

int array[num_array]={0,45,78,55,47,4,1,2,7,8,96,36,45};
// 寻找第k最小数
int k = 4;
int i = q_select（array, 0, num_array - 1, k）;
cout << i << endl;

return 0;
}本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-12/110861.htm