免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 3180 | 回复: 9

[算法] 出一道题,关于排序 [复制链接]

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2015-09-03 22:02 来自手机 |显示全部楼层
本帖最后由 cjaizss 于 2015-09-03 22:43 编辑

曾想起以前写sed挑战自己能力的时候,有一次遇到数据需要排序,于是创建了以下排序手段,因为在sed中比较容易实现:
对于数组a[1:n]
每一步,如果存在某个i和某个j,使得
0<i<j<=n
ai<aj那么交换ai和aj
直到排序完成
题目:试证明以上算法的合理性,既以上算法必然可以结束。

论坛徽章:
44
15-16赛季CBA联赛之浙江
日期:2021-10-11 02:03:59程序设计版块每日发帖之星
日期:2016-07-02 06:20:0015-16赛季CBA联赛之新疆
日期:2016-04-25 10:55:452016科比退役纪念章
日期:2016-04-23 00:51:2315-16赛季CBA联赛之山东
日期:2016-04-17 12:00:2815-16赛季CBA联赛之福建
日期:2016-04-12 15:21:2915-16赛季CBA联赛之辽宁
日期:2016-03-24 21:38:2715-16赛季CBA联赛之福建
日期:2016-03-18 12:13:4015-16赛季CBA联赛之佛山
日期:2016-02-05 00:55:2015-16赛季CBA联赛之佛山
日期:2016-02-04 21:11:3615-16赛季CBA联赛之天津
日期:2016-11-02 00:33:1215-16赛季CBA联赛之浙江
日期:2017-01-13 01:31:49
发表于 2015-09-03 22:27 |显示全部楼层
看起来你描述的就是选择排序……

这里面的问题就在于“发现如果存在”,如果你发现不了,比如说我每次从序列中随机抽取i和j比较,那这个“算法”就没法保证一定能结束,那它就不是算法。

所以你得说清这个“发现”到底指什么。

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2015-09-03 22:37 |显示全部楼层
本帖最后由 cjaizss 于 2015-09-03 22:40 编辑
windoze 发表于 2015-09-03 22:27
看起来你描述的就是选择排序……

这里面的问题就在于“发现如果存在”,如果你发现不了,比如说我每次从 ...

除了发现两个字之外,其余部分都是标准的数学语言
意思差不多就相当于你所说的“随机”
此算法是必然结束的,可以有严格数学证明
避免误解的话,把“发现”二字去掉

论坛徽章:
44
15-16赛季CBA联赛之浙江
日期:2021-10-11 02:03:59程序设计版块每日发帖之星
日期:2016-07-02 06:20:0015-16赛季CBA联赛之新疆
日期:2016-04-25 10:55:452016科比退役纪念章
日期:2016-04-23 00:51:2315-16赛季CBA联赛之山东
日期:2016-04-17 12:00:2815-16赛季CBA联赛之福建
日期:2016-04-12 15:21:2915-16赛季CBA联赛之辽宁
日期:2016-03-24 21:38:2715-16赛季CBA联赛之福建
日期:2016-03-18 12:13:4015-16赛季CBA联赛之佛山
日期:2016-02-05 00:55:2015-16赛季CBA联赛之佛山
日期:2016-02-04 21:11:3615-16赛季CBA联赛之天津
日期:2016-11-02 00:33:1215-16赛季CBA联赛之浙江
日期:2017-01-13 01:31:49
发表于 2015-09-03 22:58 |显示全部楼层
回复 3# cjaizss

我觉得不一定吧,如果我的随机数列只返回1或者2,那么这个“算法”就永远结束不了。

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2015-09-04 07:46 来自手机 |显示全部楼层
其实题目里没有随机二字,只有“存在”

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2015-09-04 09:20 |显示全部楼层
既不分治,又不穷举,每一步生成 i和j的规则没有给定,题目是残缺的

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2015-09-04 09:43 |显示全部楼层
证明:最坏情怳为 完全逆序, 不符合目的的成员间的关系有 n*(n-1) 组, 这是个有限状态
现在问题化为: 进行一次交换时, 不符合条件的成员关系至少能够减小1.

Case1: a,b间无其它元素, 则不良状态-1, 得证
Case2:  a,b间有任意多个元素, a b交换后, 状态-1
则设 被交换的数字 为 a 和 b ,对于a 和b中间的任意 x   
  case2.1: 变换前 a x为逆序状态, 则状态再-1, 否则状态不变
  case2.2: 变换前 b x为逆序状态, 则状态再-1, 否则状态不变
得证

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2015-09-04 10:09 来自手机 |显示全部楼层
妇科老人正确!过会我再给个不同的证明

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2015-09-05 20:04 |显示全部楼层
虽然不知道你们在说什么,但是我想等着看另一种证法

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2015-09-06 09:36 |显示全部楼层
证明思路大致如下:
假设存在某一个有限长的数组,存在一个符合题意的交换序列无限。
根据有限长的数组的排列是有限多个,可以得出一定存在数组的某种排序在经过了有限次交换之后和原来排列一样。
则某
B1....Bn经过有限次交换之后依然得到
B1....Bn
则1....n存在一个排列
b1....bn
使得
B(b1)>=B(b2)>=...B(bn)
现在我们证明在这有限次的交换中B(b1)不移动位置
因为不存在一个x>1
使得
B(b1)<B(bx)
所以如果移动B(b1),则一定往左移动。
而要移动回来,不仅要往左移动还要往右移动,所以B(b1)不发生移动。

而如果
B(b1)...B(bm)都不移动
则不存在一个x>m+1
使得
B(b(m+1))<B(bx)
所以如果移动B(b(m+1)),则一定往左移动。
所以B(b(m+1))也不移动。
从而,所有的点都不发生移动。

与当初的假设矛盾。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP