免规则采集器列表算法( 程序bug也能负负得正吗？还真可以吗?)

　　免规则采集器列表算法(

程序bug也能负负得正吗？还真可以吗?)

　　

　　程序错误可以是消极的还是积极的？

　　真的没问题。

　　

　　比如程序员们那么熟悉的排序算法，居然可以通过两个“bug”来修正，真是不可思议。

　　请看这位程序员写的升序数组排序代码：

　　for i = 1 to n dofor j = 1 to n doif A[i] < A[j] thenswap A[i] and A[j]

　　今天这串代码在黑客新闻论坛上突然火了起来，引来了大批程序员围观。

　　

　　乍一看这段代码，你的反应是什么？是不是觉得这个程序员水平太差了，连基本的冒泡算法都写得不好：

　　不等号的方向错了，二级循环指标j的范围也错了。

　　简而言之，这段代码“绝对不可能正确”。

　　

　　△冒泡算法

　　但是如果你真的运行它，你会发现结果真的是按升序排列的。

　　让我们看看正确的冒泡算法代码是什么样的：

　　for i = 1 to n dofor j = i + 1 to n doif A[i] > A[j] thenswap A[i] and A[j]

　　后者的区别在于j=i+1和A[i]&gt;A[j]，这两个过程有很大的不同。

　　然而，我想告诉你一个令人难以置信的事实。事实上，第一串代码是正确的，可以严格证明。

　　那么它是如何实现正确排序的呢？

　　为什么我能打对？

　　仔细想想，其实很容易理解。因为这个算法的交换操作比冒泡排序多一半，所以它恰好能够将降序编程为升序。

　　不过作者还是给出了严谨的证明。

　　我们将 Pᵢ 定义为经过 i 次 (1 ≤ i ≤ n) 外循环后获得的数组。

　　如果算法正确，则前 i 项已经是升序排列，即 A[1] ≤ A[2] ≤... ≤ A[i]。

　　证明算法正确实际上就是证明 Pₙ 对任何 n 都成立。

　　根据数学归纳法，我们只需要证明 P₁ 为真，假设 Pᵢ 为真，然后证明 Pi+1 也为真，即可证明命题。

　　P₁显然是正确的，这一步和普通的降序冒泡算法没什么区别。在第一个外循环之后，A[1] 是整个数组的最大元素。

　　然后我们假设 Pᵢ 成立，然后证明 Pi+1 成立。

　　我们首先定义一个序数 k：

　　首先假设A[k]（k在1和i之间）满足最小数A[k]&gt;A[i+1]，那么A[k−1]≤A[i+1](k≠ 1）。

　　如果 A[i+1]≥A[i]，那么这样的 k 不存在，我们让 k=i+1。

　　考虑以下三种情况：

　　1、1 ≤ j ≤ k−1

　　由于 A[i+1]&gt;A[j]，没有发生元素交换。

　　2、 k ≤ j ≤ i（如果k=i+1，这一步不存在）

　　由于A[j]&gt;A[i+1]，每次比较后都会有元素交换。

　　我们用A[]和A′[]来表示交换前后的元素，所以

　　A'[i+1] = A[k], A'[k]=A[i+1]

　　经过一系列的交换，最后把最大的元素放到了A[i+1]的位置，原来的A[i+1]变成了最大的元素，A[k]以原来的A之间的大小插入[k] 和 A[k-1] 之间的元素。

　　3、i+1 ≤ j ≤ n

　　由于最大的元素已经交换为前i+1个元素，所以在这个过程中没有元素交换。

　　最后，Pₙ是执行升序算法后的结果。

　　由于内循环和外循环的作用域没有区别，这可以说是“最简单”的排序算法。

　　从代码上看，它与冒泡算法非常相似，但从证明过程可以看出，这实际上是一种插入算法。

　　

　　△插入算法算法复杂度

　　显然，算法总是会比较n²次，然后计算算法的交换次数。

　　可以证明，交换后最多有I+2(n-1)，至少有n-1。

　　其中I为初始数的倒数，最大值为n(n-1)/2

　　因此，整个算法的复杂度为 O(n²)。

　　从证明过程可以看出，除了i=1的循环外，其余循环中j=i-1之后的部分是完全无效的，所以这部分可以省略，得到一个简化的算法。

　　for i = 2 to n dofor j = 1 to i − 1 doif A[i] < A[j] thenswap A[i] and A[j]

　　该算法减少了比较和交换的次数，但算法复杂度仍然是O(n²)。

　　网友：这个算法我见过

　　这种排序算法比最简单的冒泡算法还要简单，很快就在黑客新闻上引起了网友的关注。

　　许多人觉得它“非常熟悉”。

　　有网友说，他曾经在奥林匹克数学竞赛中看到一位同学使用了一种很奇怪的排序算法。它可以运行但效率非常低，更像是一种插入排序。

　　如果我没记错的话，他使用了这个算法。

　　

　　其实关于这个算法的讨论已经很久了，人们从2014年就开始发帖了，这次作者把论文上传到了arXiv，引起了广泛的热议。

　　

　　甚至还有乌龙事件。

　　一位网友看了一眼论文，认为算法和他10年前提出的算法一样。

　　留言网友的算法：

　　

　　乍一看，这两种算法的代码确实非常相似，原理上也确实有些相似。

　　它们看起来都像冒泡排序，但实际上更接近选择排序。

　　但很快有人指出了真相：在这个算法中j=i+1到n，当A[i]&gt;A[j]时交换。

　　在作者提出的算法中，j=1到n，A[i]

　　相比这两种算法，之前网友提出的算法更容易理解为什么能跑。

　　

　　当然，也有歪楼。有些人嘲笑他们在第一次学习编程时编写了这个算法。

　　我 100% 肯定，我在刚开始学习编程并想找到最短的排序方法时写的。

　　

　　

　　但是当涉及到实际应用时，该算法所需的计算时间太长了。

　　有些人认为这个算法之前已经被发现了很多次，但那些人根本没有打算使用它。

　　

　　还有人提出，这种排序不像睡眠排序那么简单。

　　

　　休眠排序就是构造n个线程，使线程对应n个排序。

　　例如，对于像 [4,2,3,5,9] 这样的一组数字，会创建 5 个线程，每个线程休眠 4s、2s、3s、5s、9s。这些线程唤醒后，只需报告它们对应的编号即可。这样，当所有线程都唤醒时，排序就结束了。

　　但是和作者提出的算法一样，睡眠排序由于多线程的问题，在实际实现中存在困难。

　　另外，这位网友还说他见过这个算法：

　　我确定我以前见过这个算法。它没有名字吗？

　　很快有人建议——

　　如果它没有名字，我建议称之为“面试排序”。

　　

　　参考链接：

　　[1]

　　[2]

　　

　　1.STM32U5，意法半导体全新超低功耗MCU旗舰版

　　2.【Arm-2D界面设计实例】从不规则图标的显示入手

　　3.STM8CubeMX和STM32CubeMX的功能一样吗？

　　4.这九种情况尽量不要连接MCU项目~

　　5. 偷偷把室友的STM32换成GD32后。. .

　　6.打开苹果A15芯片看die layout！

　　

　　免责声明：本文为网络转载，版权归原作者所有。如果您涉及作品的版权，请联系我们，我们将根据您提供的版权证明材料确认版权，并支付作者报酬或删除内容。