- 主题:一段有意思的排序代码
当 i = 1,2,...,n 时，都会在 j = 1 时执行 a[i] < a[1] 比较，从而数组的最小值最终会交换到 a[1].
接下来需要证明 a[k] 的位置最终放置的是第 k 小的值，还没想好怎么证明。
【 在 foliver (Oliver) 的大作中提到: 】
: 把数组从小往大按升序排列。下面是伪代码。
: for i = 1 to n
: do for j = 1 to n
: ...................
--
FROM 103.90.178.*
我对 i 这层循环演算了一下，初步明白怎么回事了。
i = 1 时，内层循环 j = 1 to n 把最大值移到了 a[1].
i > 1 时，可以证明循环开始时最大的数位于 a[i-1] 从而 j 到了 i-1 的时候，会将最大的数移到 a[i]，从而后面的比较 a[i] < a[j] 都为 false. 于是这个两层循环等价于以下的代码。
// i = 1
for j = 1 to n
if a[j] > a[1]
swap a[j],a[1]
for i = 2 to n
for j = 1 to i - 1
if a[j] > a[i]
swap a[j],a[i]
之后只需要研究后面这个算法的性质就行了。
更新：基本搞明白了，这其实就是个插入排序，看我后面的帖子。
【 在 foliver (Oliver) 的大作中提到: 】
: 把数组从小往大按升序排列。下面是伪代码。
: for i = 1 to n
: do for j = 1 to n
: ...................
--
修改:ArchLinux FROM 103.90.178.*
FROM 103.90.178.*
我发现i = 1这个循环把最大数放到a[1]的位置之后，后面这个二重循环实际上就是把a[i]插入到a[1..i-1]的类似插入排序的过程，只是因为代码里用的是swap操作，数据移动的次数可能比教科书上的插入排序算法的插入过程要多。
所以总的算法的实际上就相当于：先把数组的最大数移到最前面，然后做一次插入排序。
【 在 ArchLinux (a lightweight and flexible distribution) 的大作中提到: 】
// i = 1
for j = 1 to n
if a[j] > a[1]
swap a[j],a[1]
for i = 2 to n
for j = 1 to i - 1
if a[j] > a[i]
swap a[j],a[i]
之后只需要研究后面这个算法的性质就行了。
【 在 foliver (Oliver) 的大作中提到: 】
: 把数组从小往大按升序排列。下面是伪代码。
: for i = 1 to n
: do for j = 1 to n
: ...................
--
修改:ArchLinux FROM 103.90.178.*
FROM 103.90.178.*