出一道题，关于排序

cjaizss

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

windoze

看起来你描述的就是选择排序……

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

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

cjaizss

windoze 发表于 2015-09-03 22:27
看起来你描述的就是选择排序……

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

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

windoze

回复 3# cjaizss

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

cjaizss

其实题目里没有随机二字，只有“存在”

cokeboL

既不分治，又不穷举，每一步生成 i和j的规则没有给定，题目是残缺的

folklore

证明：最坏情怳为 完全逆序， 不符合目的的成员间的关系有 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， 否则状态不变
得证

cjaizss

妇科老人正确！过会我再给个不同的证明

cokeboL

虽然不知道你们在说什么，但是我想等着看另一种证法

cjaizss

证明思路大致如下：
假设存在某一个有限长的数组，存在一个符合题意的交换序列无限。
根据有限长的数组的排列是有限多个，可以得出一定存在数组的某种排序在经过了有限次交换之后和原来排列一样。
则某
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))也不移动。
从而，所有的点都不发生移动。

与当初的假设矛盾。