待字闺中之巧妙排序分析:[通俗易懂]

待字闺中之巧妙排序分析:

大家好,又见面了,我是全栈君。

题目来源。待字闺中。原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中” 

排序仅仅有1。2,3三个元素的数组。不能统计1,2。3的个数。

分析:这个题目,虽然也是排序,但却不能使用高速排序的方法。仅仅有三个元素,假设时间复杂度仍旧是O(nlogn)。显然不是最好的。那就行使用线性的排序算法,比如计数排序。但是题目中要求,不可以对1,2,3进行统计个数。那该怎样处理呢?请大家看以下的方法,我们首先通过样例来说明:

2 1 1 3 3 2
p1 p2       p3

如果,我们有三个指针:p1、p2、p3.p1从左側開始,指向第一个非1的数字。p3从右側開始,指向第一个非3的数字。

p2从p1開始遍历。如果是2,p2继续遍历,直到p2遇到1或者3:

假设遇到1,则和p1进行交换,然后p1向右,指向第一个非1的数字

假设遇到3,则和p3进行交换。然后p3向左。指向第一个非3的数字

1 2 1 3 3 2
  p1,p2       p3
 

交换之后,p2继续从p1開始。假设是2继续遍历。假设是1或者3,反复上面的步骤,所得例如以下:

1 1 2 3 3 2
    p1,p2     p3

依据上面的方法继续下去

1 1 2 2 3 3
p1 p3 p2      
 

p2在p3右側。算法结束。详细代码例如以下:

void SortWithThreePointer(vector<int>& data)//用三个指针进行排序。缺点。仅仅能对三个数有效{	int length = data.size();	if(length <= 0)return;	int begin = 0,cur = 0,end = length -1;	while(cur <=  end )	{		if(data[cur] == 1)		{			swap(data[begin],data[cur]);			begin ++;			cur ++;		}		else if(data[cur] == 3)		{			swap(data[cur],data[end]);			end --;		}		else cur ++;	}}

基于快排划分的思路

上面的思路。是针对三个数的,假设有很多其它的数,怎么处理呢?比方,4个,5个等等。以下依据高速的排序的启示,介绍一种算法,虽然在处理三个数的时候。比較次数会多些,但,具有非常好的通用性。

思路来自快排的划分部分。快排的划分部分:给定pivot,然后将数据划分为<=pivot和>pivot两部分。这样。三个数字时,须要两次划分:

第一次,用1作为pivot,划分1到最左边。

第二次,用2作为pivot。划分2到左边,则得到总体的排序。

详细代码例如以下:

int partition(vector<int>& data,int provit,int begin,int end)
{
	int i;
	for(i = begin;i <= end;i++)
	{
		if(data[i] == provit)
		{
			swap(data[begin],data[i]);//找到给定的provit,交换到第一个位置
			break;
		}
	}
	if(i == end+1)return begin-1;
	while(begin < end)
	{
		while(begin < end && data[end] > provit ) end --;
		if(begin < end) data[begin++] = data[end];
		while(begin < end && data[begin] <= provit) begin++;
		if(begin < end)data[end--] = data[begin];
	}
	data[begin] = provit;
	return begin;
}
//numbers是已经排好序的可能会出现的数字,如1。2。3,对每个数字进行partition
void SortWithPartition(vector<int>& data,vector<int>& number)
{
	int i,provit,dataLen = data.size(),numberLen = number.size();
	if(dataLen <= 0 || numberLen <= 0)return;
	int begin = 0,end = dataLen-1;
	for(i=0;i<numberLen && begin < end;i++)
	{
		provit = partition(data,number[i],begin,end);
		begin = provit + 1;
	}
}

最巧妙的思路

我们将1,2,3。替换为互质的2,3,5,得到例如以下:

2 1 1 3 3 2
3 2 2 5 5 3

之后,乘起来得到的900.这900里,除以2。有多少个2。就有多少个1;然后除以3,有多少个3,就有多少个3相应的2;然后除以5。有多少个5,就有多少个5相应的3。

这是怎样保证的呢?由于2,3,5是互质的。

例如以下:

被除数 除数 余数 排序结果
900 2 450 0 1
450 2 225 0 1
225 2 112 1 2尝试结束,尝试3
225 3 75 0 2
75 3 25 0 2
25 3 8 1 3尝试结束,尝试5
25 5 5 0 3
5 5 1 0 3
1 5 1 1 所有结束

终于结果为112233.上面的这样的思路。实际上是计数的一种变种。没有直接的技术。那自然就是能够的。

详细代码例如以下:

//numbers是已经排好序的可能会出现的数字。如1。2,3。把每个数映射为素数,该方法的缺陷是可能会出现溢出void SortWithPrimeNum(vector<int>& data,vector<int>& number){	int prime[26] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};//100以内的素数	int dataLen = data.size(),numberLen = number.size();	if(dataLen <= 0 || numberLen <= 0 || numberLen >= 25)return;	map<int,int> hashMap;	int i,j=0,product = 1;	for(i=0;i<numberLen;i++)	{		hashMap[number[i]] = prime[i];//把可能出现的数字映射为素数	}	for(i=0;i<dataLen;i++)	{		product *= hashMap[data[i]];	}	for(i=0;i<numberLen && product != 0;i++)	{		cout << hashMap[number[i]] << endl;		while(product % hashMap[number[i]] == 0)		{			data[j++] = number[i];			product = product / hashMap[number[i]];		}	}}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115925.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 提交本地jar到Maven中央仓库(Windows&码云gitee托管代码)的那些小事

    提交本地jar到Maven中央仓库(Windows&码云gitee托管代码)的那些小事

  • Cocos creator 微信小游戏排行榜「建议收藏」

    Cocos creator 微信小游戏排行榜「建议收藏」Cocoscreator版本:2.0.10主域动态刷新子域首先得知道主域和子域的关系,需要让子域(开放域)里的排行榜信息动态刷新在主域的页面中,需要在主域中的节点上挂载WXSubContextView组件。子域中,可以添加Widget组件、滚动的节点来实现上下或者左右滑动。这里主要记录排行榜的实现。(这里只实现了同玩好友排行榜的功能,同玩群好友可以另实现)实现排行榜步骤一:需要实现…

    2022年10月27日
  • 最全Pycharm教程(17)——Pycharm编辑器功能之自动导入模块

    最全Pycharm教程(17)——Pycharm编辑器功能之自动导入模块  1、导入模块  我们在编程过程中经常会不经意的使用到一些尚未导入的类和模块,在这种情况下Pycharm会帮助我们定位模块文件位置并将其添加到导入列表中,这也就是所谓的自动导入模块功能。  为了研究这个功能,我们借用之前已经编写好的Solver类,输入以下代码:  在输入math.sqrt(d)的时候,Pycharm会弹出一个菜单来提示你导入缺失的模块:  按下Alt+Enter,采取快捷菜单中…

  • MQTT学习笔记(6)搭建本地MQTT服务器

    MQTT学习笔记(6)搭建本地MQTT服务器搭建EMQTT下载地址下载emqttd-windows10-v2.3.11.zip解压后cd到bin目录,执行emqttdconsole执行成功会弹出下面窗口,不成功就关掉cmd重新试下打开浏览器输入http://127.0.0.1:18083默认用户名admin默认密码public进入如下界面框起来的点进去看看就知道了。注意如果你用w…

  • shell批量新建文件

    shell批量新建文件shell批量新建文件,文件名依次为a1,a2……a100#!/bin/bashPath=/home/yifan/maying/shell/case2[-d$Path]||mkdir$Pathint=1while(($int&lt;=100))dofilename="a"$int""touch$Path/$filenamelet"int++"do…

  • win10下安装PyCharm以及激活

    win10下安装PyCharm以及激活【在此之前先安装好python】1.PyCharm是什么?PyCharm是一种PythonIDE,带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具。PyCharm拥有一般IDE具备的功能,比如,调试、语法高亮、Project管理、代码跳转、智能提示、自动完成、单元测试、版本控制另外,PyCharm还提供了一些很好的功能用于Django开发,同时支持Google…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号