本節，咱們將依據下圖所示的步驟，采取中位數的中位數選取樞紐元的方法來實現此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;
}
