duangsuse::Echo

#bin 然后为了证明我不比 drakeet 差，只是缺少拿来实践的时间，我分析一下这篇文章《5分钟学会十进制转换成二进制的快速口算方法 & Java输出二进制的代码》，然后就睡觉。当然，至于 Android 那一套，比如异步、Timer、MessageDriven、Android XML、Android Widgets、Resources、Android Gradle Build 集成、库打包、封装、Android Layouts、Views、Paint、Android Layout Animat…

最后一句（我懒得再看 drakeet 的博客和文章什么的了，怕又引起撕逼，虽然我对技术还是很客气的... 而且现在我不虚，除了要和我谈 Monad 和范畴论图论线性代数什么的）：
我才知道 drakeet 使用的排序算法是从大学的时候改的... 而且他还学过 Objc 和 iOS 开发...

https://blog.csdn.net/drakeet/article/details/12948029 👈 here, 《还是用csdn吧》

那么我这周最后谈一下这个博文最后提的问题，太久流于一个话题对我来说也不好。

我发现，其实酷安开发者们大学生也不少。by_syk 应该也是大学生吧

NSNumber *temp = [[NSNumber alloc] init];

//「从小到大」排序
for (NSInteger i = 0; i < aHundredArray.count - 1; i++) {
    for (NSInteger j = i+1; j > aHundredArray.count; j++) {
        
        if (aHundredArray[j] < aHundredArray[j-1]) {
            temp = aHundredArray[j-1];
            aHundredArray[j-1] = aHundredArray[j];
            aHundredArray[j] = temp;
        }
    }
}

---------------------
作者：drakeet

我们用伪代码描述一下，反正我们不再乎是 Objc、Swift 还是 C++ 是吧？因为交换排序本来就应该是任何正常编程语言都能写的，Haskell 靠 forM_, (!!) 都能写（或许吧）

var ary[n]
predicate x y = not $ x `lessThan` y

for i in ary.indicesWithoutLast |>
  local suc_i = i +1 — next item index
  if (ary[i] `predicate` ary[suc_i]) swap(ary, i, suc_i)

怎么样，好看吧？这是个『不能使用』的交换排序算法，交换比较谓词函数为 (not · lessThan)，换句话说，我们认为列表应该是 [a(<b), b (<c), c] 才对，否则就交换索引致使它成那样。

那么不对在哪里？假设我们有一个列表

[1, 3, 4] 排序结果显然是正确的，因为它不需要消除任何逆序对
[4, 1, 3] 在 i = 0 的时候，我们消除了一个逆序对 [4, 1] 成 [1, 4]，然后 i = 1 结束循环时 [4, 3] 也被消除，得到有序列表

那么这个算法（我写的，不是原算法...）其实就是简单交换排序... 是没问题的（迫真，其实有问题... 比如 [4, 1, 3, 2] 就不能排序，因为它不足以把 2 交换到顶部，至于数据模式，就是 [d, a, b, c], a > b, a > c, d > a, 算法输出只能是 [a, b, c, d]... 好吧我输了，我这么抽象的时候找不出不能排序的... 但我觉得不对，肯定有无法交换到『前面』的模式的）

那么问题来了，到底为啥一半有序一半无序？因为我开始看错了...

for (NSInteger i = 0; i < aHundredArray.count - 1; i++)
for (NSInteger j = i+1; j > aHundredArray.count; j++)

什么魔性循环... 比如对于输入 [4, 3, 2, 1], for
count = 4
i = 0
j = 1 — j 不可能 greaterThan count，因为所有 i 循环中的 j (aka. succ i) 在 range bound (0:(count-1)-1+1) 内，(count - 1) 不可能 greaterThan count，j++ 为死代码, 第二个循环不存在,, 看来我上面的是对的
swap([4,3,2,1], 0, 1)
i = 1
j = 2
swap([3,4,2,1], 1, 2)
i = 3
j = 4
swap([3,2,4,1], 3, 4)
(endfor)

result = [3, 2, 1, 4]

这就是所谓的『排了一半』，我们注意到 3 和 2 是逆序的，因为我们在交换 &2 和 &1 的时候没有考虑到前面有个 3 打破了期望的偏序关系（只知 3 > 2 不知 3 > 1，何况知道手也短无事可做）。

然后你们看到了，后来 drakeet 也在 LayoutFormatter 里觉悟了原来交换步长只有 1 啊！逆序对只是个 pair，更大的逆序是无法靠交换相邻项消除的，所以用了一个 for (i = 0; i < j - 1; i++), 完美

49 viewsduangsuse ¯\_(ツ)_/¯ |学渣 | 我爱学习 | ∈ [E²PROM, 范畴论], edited 04:32

duangsuse::Echo via @vote

🎉 那么看完了以上两条消息，不会觉得我智商不如 drakeet 了吧？
anonymous poll

🐱 – 4
👍👍👍👍👍👍👍 100%

👥 4 people voted so far.

43 viewsduangsuse ¯\_(ツ)_/¯ |学渣 | 我爱学习 | ∈ [E²PROM, 范畴论], 04:43