用最less的比较数sorting一个数组
我需要一些帮助，我的CS功课。 我需要编写一个sorting例程，在最差的情况下使用7个比较对一个长度为5的数组进行sorting（由于决策树的高度，我已经certificate需要7个）。
我考虑使用“硬编码”决策树，但这意味着algorithm非常复杂，我的导师暗示，这不是它应该做的方式。
我检查过快排，合并sorting，堆sorting，d堆sorting，插入sorting，selectsorting，都不回答要求，这导致我相信有一个长度为5的数组的特定algorithm的需要。
真的想得到一些正确方向的提示。
是的，它在Knuth第3卷第185页（第5.3.1节）。 这首先是在博士论文中logging的，所以你的教授对你很重要！ 没有真正简单的优雅的方法; 您必须将其作为部分有序的树进行追踪。
这里是在lisp。 testing好（Linux上的SBCL）
(defun small-sort (a) "Sort a vector A of length 5" (if (> (aref a 0) (aref a 1)) (rotatef (aref a 0) (aref a 1))) (if (> (aref a 2) (aref a 3)) (rotatef (aref a 2) (aref a 3))) (if (> (aref a 0) (aref a 2)) (progn (rotatef (aref a 0) (aref a 2)) (rotatef (aref a 1) (aref a 3)))) (if (> (aref a 4) (aref a 2)) (if (> (aref a 4) (aref a 3)) (progn) (rotatef (aref a 3) (aref a 4))) (if (> (aref a 4) (aref a 0)) (rotatef (aref a 2) (aref a 4) (aref a 3)) (rotatef (aref a 0) (aref a 4) (aref a 3) (aref a 2)))) (if (> (aref a 1) (aref a 3)) (if (> (aref a 1) (aref a 4)) (rotatef (aref a 1) (aref a 2) (aref a 3) (aref a 4)) (rotatef (aref a 1) (aref a 2) (aref a 3))) (if (> (aref a 1) (aref a 2)) (rotatef (aref a 1) (aref a 2)) (progn))) a) (defun check-sorted (a) (do ((i 0 (1+ i))) ((>= i (1- (array-dimension a 0)))) ;;(format t "~S ~S~%" (aref ai) (aref a (+ 1 i))) (assert (<= (aref ai) (aref a (+ 1 i)))))) (defun rr () (dotimes (i 100000) (let ((a (make-array 5 :initial-contents (list (random 1.0) (random 1.0) (random 1.0) (random 1.0) (random 1.0) )))) ;;(format t "A=~S~%" a) (let ((res (small-sort a))) (check-sorted res) ;;(format t "Res=~S~%" res) )))) Donald Knuth的“计算机编程的艺术”第3卷有关于这个主题的一节。 我没有和我在一起的书，但是我非常肯定Knuth提出了5个元素的algorithm。 正如你所怀疑的那样，没有一个通用algorithm给出了许多尺寸的最小比较次数，但是在这样的algorithm中有很多常用的技巧。
从模糊的回忆中，我重build了5个元素的algorithm，可以在7个比较中完成。 首先，拿两个单独的对，在里面进行比较，然后比较每对中较小的一对。 然后，比较剩余的一个与这些更大的。 现在根据剩余的元素是小还是大来分为两种情况，但是在所有情况下，仍然有可能在三种比较中完成。
我build议画图来帮助你。 Knuth的照片是这样的：
ØØ---
/
ØØ---
它显示了前三次比较后的结果（从我记得的情况来看，这种图片出现在许多最小比较种类中）。 一条线连接两个我们知道的顺序的元素。 有了这样的图片可以帮助你确定哪些元素进行比较，因为你想做一个比较，给你最大的信息量。
附录：由于实际代码有一个公认的答案，所以我认为完成这些图表没有什么坏处，它们可能是对答案的有益补充。 所以，从上面的一个开始，比较缺less的元素与左上angular的元素。 如果它更大，这将导致
/ - Ø
Ø
/ \ - o
Ø
\ - Ø
现在，比较右上angular的两个大元素，我们结束了
Ø - O - O
/
ØØ---
现在，通过比较右下angular的元素与顶部的中间的元素，然后反对它所属的那一边，我们使用剩余的两个比较正确地放置它。
如果初始比较导致剩余元素变小，则图变成
Ø - O - O
/
ØØ---
现在，比较那些还没有比他们小的两个。 一个选项是上面的最后一个图，可以用剩下的两个比较来解决。 另一种情况是
ØØ---
/
Ø - O - O
在这里，还没有和其他人一起排列的东西，可以通过两次比较来正确放置。
7听起来像它可能是壳sorting以及。
我不认为硬编码的解决scheme应该是复杂的：
- 比较（元素）2和3，并根据需要进行交换
- 比较3和4，并根据需要进行交换
- 比较1和3，如果1less，则比较1和2，否则比较1和4.将1放在正确的插槽中。
- 重复步骤3，除了元素3和5。
这将总是使用7个比较。
编辑：
我不认为这会起作用：第4步被打破，可能需要第8次比较。 考虑：
Index | 1 | 2 | 3 | 4 | 5 | Value | 2 | 3 | 4 | 5 | 1 |
步骤4：
- 比较3和5 == 4比1 ==元素5less于元素3
- 比较2＆5 == 3与1 ==元素5less于元素2
- ??? 需要比较1和5来知道元素5的放置位置。
铲斗sorting可以如下实现为比较algorithm：
拿一个元素。
将它与所有的桶进行比较。
把它放入相匹配的桶中。 < – 比较需要。
如果未find存储桶，请创build一个新的存储桶。
因此，这是我刚刚描述的dynamic桶sortingalgorithm。
我已经在过去的新闻组上发明/描述了这个。
看看桶sorting。
