快速select算法的实现

代码来自：
http://blog.csdn.net/v_JULY_v
算法思想：
// Quick_select.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#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];

/*

//插入排序算法伪代码

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;

	}

}

void insertion_sort(int array[],int first,int last)

{

	int i,j;

	int temp;

	for(i = first + 1 ;i<=last;i++)

	{

		temp = array[i];

		j=i-1;

		//与已排序的数逐一比较，大于temp时，该数移后

		while((j>=0)&&(array[j]>temp))

		{

			array[j+1]=array[j];

			j--;

		}

		//存在大于temp的数

		if(j!=i-1)

		{array[j+1]=temp;}

	}

}

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);

		insertion_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);

		insertion_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 _tmain(int argc, _TCHAR* argv[])

{

	//srand(unsigned(time(NULL)));

	//for (int j = 0; j < num_array; j++)

	int a[4] = {13,26,9,100};

	insert_sort(a,0,3);

	//insertion_sort(a,0,3);

	cout<<a[0]<<a[1]<<a[2]<<a[3]<<endl;

	//array[j] = rand();

	int array[num_array]={0,45,78,55,47,4,1,2,7,8,96,36,45};

	// 寻找第k 最小数

	int k = 13;

	int i = q_select(array, 0, num_array - 1, k);

	cout << i << endl;

	getchar();

	return 0;

}
巴特西

快速select算法的实现

最新文章

热门文章
