wizen-coder
10/4/2018 - 10:25 AM

线性时间选择问题：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，（这里给定的线性集是无序的）。 1、随机划分线性选择        线性时间选择随机划分法可以模仿随机化快速排序算法设计。基本思想是对输入数组进行递归划分，与快速排序不同的是，它只

线性时间选择问题：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，（这里给定的线性集是无序的）。 1、随机划分线性选择 线性时间选择随机划分法可以模仿随机化快速排序算法设计。基本思想是对输入数组进行递归划分，与快速排序不同的是，它只对划分出的子数组之一进行递归处理。在最坏的情况下，例如：总是找到最小元素时，总是在最大元素处划分，这是时间复杂度为O(n^2)。但平均时间复杂度与n呈线性关系，为O(n)。 2、利用中位数线性时间选择 中位

RandomizedSelect1.cpp
content_copyfile_download
//2d9-1 随机划分线性时间选择
#include "stdafx.h"
#include <iostream> 
#include <ctime>
using namespace std; 
 
int a[] = {5,7,3,4,8,6,9,1,2};
 
template <class Type>
void Swap(Type &x,Type &y);
 
inline int Random(int x, int y);
 
template <class Type>
int Partition(Type a[],int p,int r);
 
template<class Type>
int RandomizedPartition(Type a[],int p,int r);
 
template <class Type>
Type RandomizedSelect(Type a[],int p,int r,int k);
 
int main()
{
	for(int i=0; i<9; i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
	cout<<RandomizedSelect(a,0,8,3)<<endl;
}
 
template <class Type>
void Swap(Type &x,Type &y)
{
	Type temp = x;
	x = y;
	y = temp;
}
 
inline int Random(int x, int y)
{
     srand((unsigned)time(0));
     int ran_num = rand() % (y - x) + x;
     return ran_num;
}
 
template <class Type>
int Partition(Type a[],int p,int r)
{
	int i = p,j = r + 1;
	Type x = a[p];
 
	while(true)
	{
		while(a[++i]<x && i<r);
		while(a[--j]>x);
		if(i>=j)
		{
			break;
		}
		Swap(a[i],a[j]);
	}
	a[p] = a[j];
	a[j] = x;
	return j;
}
 
template<class Type>
int RandomizedPartition(Type a[],int p,int r)
{
	int i = Random(p,r);
	Swap(a[i],a[p]);
	return Partition(a,p,r);
}
 
template <class Type>
Type RandomizedSelect(Type a[],int p,int r,int k)
{
	if(p == r)
	{
		return a[p];
	}
	int i = RandomizedPartition(a,p,r);
	int j = i - p + 1;
	if(k <= j)
	{
		return RandomizedSelect(a,p,i,k);
	}
	else
	{
		//由于已知道子数组a[p:i]中的元素均小于要找的第k小元素
		//因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。
		return RandomizedSelect(a,i+1,r,k-j);
	}
}
RandomizedSelect2.cpp
content_copyfile_download
//2d9-2 中位数线性时间选择
#include <ctime>
#include <iostream> 
using namespace std; 
 
template <class Type>
void Swap(Type &x,Type &y);
 
inline int Random(int x, int y);
 
template <class Type>
void BubbleSort(Type a[],int p,int r);
 
template <class Type>
int Partition(Type a[],int p,int r,Type x);
 
template <class Type>
Type Select(Type a[],int p,int r,int k);
 
int main()
{
	//初始化数组
	int a[100];
 
	//必须放在循环体外面
	srand((unsigned)time(0));
 
	for(int i=0; i<100; i++)
	{
		a[i] = Random(0,500);
		cout<<"a["<<i<<"]:"<<a[i]<<" ";
	}
	cout<<endl;
 
	cout<<"第83小元素是"<<Select(a,0,99,83)<<endl;
 
	//重新排序，对比结果
	BubbleSort(a,0,99);
 
	for(int i=0; i<100; i++)
	{
		cout<<"a["<<i<<"]:"<<a[i]<<" ";
	}
	cout<<endl;
}
 
template <class Type>
void Swap(Type &x,Type &y)
{
	Type temp = x;
	x = y;
	y = temp;
}
 
inline int Random(int x, int y)
{
     int ran_num = rand() % (y - x) + x;
     return ran_num;
}
 
//冒泡排序
template <class Type>
void BubbleSort(Type a[],int p,int r)
{
	 //记录一次遍历中是否有元素的交换   
     bool exchange;  
     for(int i=p; i<=r-1;i++)  
     {  
		exchange = false ;  
        for(int j=i+1; j<=r; j++)  
        {  
			if(a[j]<a[j-1])  
            {  
                Swap(a[j],a[j-1]); 
                exchange = true;  
            }   
        }   
        //如果这次遍历没有元素的交换,那么排序结束   
        if(false == exchange)  
		{
             break ;  
		}
	 }
}
 
template <class Type>
int Partition(Type a[],int p,int r,Type x)
{
	int i = p-1,j = r + 1;
 
	while(true)
	{
		while(a[++i]<x && i<r);
		while(a[--j]>x);
		if(i>=j)
		{
			break;
		}
		Swap(a[i],a[j]);
	}	
	return j;
}
 
 
template <class Type>
Type Select(Type a[],int p,int r,int k)
{
	if(r-p<75)
	{
		BubbleSort(a,p,r);
		return a[p+k-1];
	}
	//(r-p-4)/5相当于n-5
	for(int i=0; i<=(r-p-4)/5; i++)
	{
		//将元素每5个分成一组，分别排序，并将该组中位数与a[p+i]交换位置
		//使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数
		BubbleSort(a,p+5*i,p+5*i+4);
		Swap(a[p+5*i+2],a[p+i]);
	}
	//找中位数的中位数
	Type x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10);
	int i = Partition(a,p,r,x);
	int j = i-p+1;
	if(k<=j)
	{
		return Select(a,p,i,k);
	}
	else
	{
		return Select(a,i+1,r,k-j);
	}
}