出一道題，關(guān)于排序

cjaizss

曾想起以前寫sed挑戰(zhàn)自己能力的時候，有一次遇到數(shù)據(jù)需要排序，于是創(chuàng)建了以下排序手段，因為在sed中比較容易實現(xiàn):
對于數(shù)組a[1:n]
每一步，如果存在某個i和某個j，使得
0<i<j<=n
ai<aj那么交換ai和aj
直到排序完成
題目:試證明以上算法的合理性，既以上算法必然可以結(jié)束。

windoze

看起來你描述的就是選擇排序……

這里面的問題就在于“發(fā)現(xiàn)如果存在”，如果你發(fā)現(xiàn)不了，比如說我每次從序列中隨機抽取i和j比較，那這個“算法”就沒法保證一定能結(jié)束，那它就不是算法。

所以你得說清這個“發(fā)現(xiàn)”到底指什么。

cjaizss

windoze 發(fā)表于 2015-09-03 22:27
看起來你描述的就是選擇排序……

這里面的問題就在于“發(fā)現(xiàn)如果存在”，如果你發(fā)現(xiàn)不了，比如說我每次從 ...

除了發(fā)現(xiàn)兩個字之外，其余部分都是標(biāo)準(zhǔn)的數(shù)學(xué)語言
意思差不多就相當(dāng)于你所說的“隨機”
此算法是必然結(jié)束的，可以有嚴(yán)格數(shù)學(xué)證明
避免誤解的話，把“發(fā)現(xiàn)”二字去掉

windoze

回復(fù) 3# cjaizss

我覺得不一定吧，如果我的隨機數(shù)列只返回1或者2，那么這個“算法”就永遠(yuǎn)結(jié)束不了。

cjaizss

其實題目里沒有隨機二字，只有“存在”

cokeboL

既不分治，又不窮舉，每一步生成 i和j的規(guī)則沒有給定，題目是殘缺的

folklore

證明：最壞情怳為 完全逆序， 不符合目的的成員間的關(guān)系有 n*(n-1) 組， 這是個有限狀態(tài)
現(xiàn)在問題化為： 進(jìn)行一次交換時， 不符合條件的成員關(guān)系至少能夠減小1.

Case1： a,b間無其它元素， 則不良狀態(tài)-1， 得證
Case2:  a,b間有任意多個元素， a b交換后， 狀態(tài)-1
則設(shè) 被交換的數(shù)字 為 a 和 b ，對于a 和b中間的任意 x   
  case2.1: 變換前 a x為逆序狀態(tài)， 則狀態(tài)再-1， 否則狀態(tài)不變
  case2.2: 變換前 b x為逆序狀態(tài)， 則狀態(tài)再-1， 否則狀態(tài)不變
得證

cjaizss

婦科老人正確！過會我再給個不同的證明

cokeboL

雖然不知道你們在說什么，但是我想等著看另一種證法

cjaizss

證明思路大致如下：
假設(shè)存在某一個有限長的數(shù)組，存在一個符合題意的交換序列無限。
根據(jù)有限長的數(shù)組的排列是有限多個，可以得出一定存在數(shù)組的某種排序在經(jīng)過了有限次交換之后和原來排列一樣。
則某
B1....Bn經(jīng)過有限次交換之后依然得到
B1....Bn
則1....n存在一個排列
b1....bn
使得
B(b1)>=B(b2)>=...B(bn)
現(xiàn)在我們證明在這有限次的交換中B(b1)不移動位置
因為不存在一個x>1
使得
B(b1)<B(bx)
所以如果移動B(b1),則一定往左移動。
而要移動回來，不僅要往左移動還要往右移動，所以B(b1)不發(fā)生移動。

而如果
B(b1)...B(bm)都不移動
則不存在一個x>m+1
使得
B(b(m+1))<B(bx)
所以如果移動B(b(m+1)),則一定往左移動。
所以B(b(m+1))也不移動。
從而，所有的點都不發(fā)生移動。

與當(dāng)初的假設(shè)矛盾。