【算法导论】第i小的元素-阿里云开发者社区

开发者社区> tengweitw> 正文

【算法导论】第i小的元素

简介: 第i小的元素       时间复杂度:O(n).       基本思想:和快速排序的思想相似,也是对数组进行递归划分,但是有所差别的是,快速排序会递归处理划分的两边,而随机化的选择算法只选择一边。
+关注继续查看

第i小的元素

      时间复杂度:O(n).

      基本思想:和快速排序的思想相似,也是对数组进行递归划分,但是有所差别的是,快速排序会递归处理划分的两边,而随机化的选择算法只选择一边。

      具体步骤为:首先,随机选择一个数组元素作为主元,从而将数组分解为两个子数组,并得到主元在元素中的位置q,假设较小子数组元素的个数为k-1;然后比较i与k的大小,来确定下一次递归选择哪一边的子数组(注意i的值的改变情况);最后,当i==k时,就求得了第i小的元素。具体实例见图解


具体的程序实现如下:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int Partition(int*arrayA,int n,int p,int r);
int RandomPartition(int* arrayA,int n,int p,int r);
int RandomSelect(int* arrayA,int n,int p,int r,int i);

void main()
{
	int arrayA[8]={2,1,3,4,8,6,7,5};
	int n=sizeof(arrayA)/sizeof(int);
	int p=0;
	int r=7;
	int i=4;
	int result=0;
	result=RandomSelect(arrayA,n,p,r,i);
	printf("数组中第%d小的数是%d\n",i,result);

}


/**************************************************\
函数功能:将原数组分成全大于和全小于x的两个子数组
输入:原始数组、要对数组进行操作的起始和结束下标p、r
	  即只对数组指定部分进行操作。
输出:x在数组中的位置
\**************************************************/
int Partition(int*arrayA,int n,int p,int r)
{
	int x=arrayA[r];//使主元x选为数组选中部分的最后一个元素
	int i=p-1;
	int temp=0;
	for(int j=p;j<=r-1;j++)
	{
		if(arrayA[j]<=x)
		{
			i++;
			temp=arrayA[i];
			arrayA[i]=arrayA[j];
			arrayA[j]=temp;
		}
	}
	temp=arrayA[i+1];
	arrayA[i+1]=arrayA[r];
	arrayA[r]=temp;

	return i+1;//最终主元的位置
}


/**************************************************\
函数功能:用随机数确定主元
输入:原始数组、要对数组进行操作的起始和结束下标p、r
	  即只对数组指定部分进行操作
输出:x在数组中的位置
\**************************************************/
int RandomPartition(int* arrayA,int n,int p,int r)
{
	int suiji=0;
	srand(time(0));
	suiji=rand()%(r-p)+p;//产生大于等于p,小于r的随机数
  printf("suiji=%d\n",suiji);
	int temp=0;
	temp=arrayA[r]; //使主元由随机数确定
	arrayA[r]=arrayA[suiji];
	arrayA[suiji]=temp;

	return Partition(arrayA,n,p,r);
}

/**************************************************\
函数功能:找出数组中第i小的数
输入:原始数组、要对数组进行操作的起始和结束下标p、r
	  即只对数组指定部分进行操作
输出:x在数组中的位置
\**************************************************/
int RandomSelect(int* arrayA,int n,int p,int r,int i)
{
	int q=0;
	
	if(p==r)
		return arrayA[p];

	for(int j=p;j<=r;j++)
		printf("%d ",arrayA[j]);
	printf("\n");
	q=RandomPartition(arrayA,n,p,r);//主元的位置
	printf("gaihou:\n");
	for(int j=p;j<=r;j++)
		printf("%d ",arrayA[j]);
	printf("\n\n");

	int k=q-p+1;
	if(i==k)
		return arrayA[q];
	else if(i<k)
		return RandomSelect(arrayA,n,p,q-1,i);
	else
		return RandomSelect(arrayA,n,q+1,r,i-k);

}

注意:我是在vs2008上运行的,与vc 6.0有点区别,主要是循环体中的循环变量的作用域,出错体现在循环变量的重复定义上。例如:在vs2008或vs2010上,程序为:

#include<stdio.h>
void main()
{
int i=0;
for(int i=0;i<5;i++)
printf("%d ",i);
}

则在VC 6.0上需改为:

#include<stdio.h>
void main()
{
int i=0;
for(i=0;i<5;i++)
printf("%d ",i);
} 


原文:http://blog.csdn.net/tengweitw/article/details/9668849

作者:nineheadedbird

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10086 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
2962 0
【算法导论】第i小的元素
第i小的元素       时间复杂度:O(n).       基本思想:和快速排序的思想相似,也是对数组进行递归划分,但是有所差别的是,快速排序会递归处理划分的两边,而随机化的选择算法只选择一边。
744 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13890 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
11890 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
4660 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
7365 0
+关注
tengweitw
所在学校:西电 兴趣爱好:编程、英语,象棋,乒乓球 email:771257840@qq.com
159
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载