用最少的比较次数对数组进行排序

Question

我需要帮助完成计算机科学作业。我需要编写一个排序函数，用于对长度为5的数组进行排序，在最坏情况下使用7次比较（因为决策树的高度已经被证明需要7次比较）。

我考虑过使用'硬编码'的决策树，但这意味着算法非常复杂，我的导师暗示这不是正确的做法。

我已经检查了快速排序、归并排序、堆排序、d-ary堆排序、插入排序、选择排序，都不能满足要求，这让我相信需要一个特定的算法来处理长度为5的数组。

真的想得到一些指向正确方向的提示。

- CS n00b

---

证明至少需要7次比较有一个更简单的方法。5个元素有(5!) = 120种排列方式，而进行7次比较则有(2 ** 7) = 128种不同的结果。 - Mark Byers

+1，对于一个表述清晰、明确问题、展示你已经做了什么以及最重要的——提到这是作业的好问题。 - MAK

http://www.drdobbs.com/sorting-networks/184402663 看起来需要9次比较...可能是因为它太老了？ - Janus Troelsen

参见：固定长度为6的整型数组的最快排序 - Janus Troelsen

在线整数序列百科全书中的A036604序列显示，对于排序5个元素，最少需要7次比较。(链接见此答案)。 - Jonathan Leffler

Answer 1

唐纳德·克努斯的The Art of Computer Programming，第3卷有一节专门介绍这个主题。我没有带着书在身边，但我相当确定Knuth给出了5个元素的算法。正如你所怀疑的那样，对于许多尺寸并没有提供最少比较的通用算法，但是在这种算法中使用了许多常见技巧。

从模糊的记忆中，我重构了5个元素的算法，并且可以做到7次比较。首先，取两个不同的对，比较它们内部，并比较每对中较小的那一个。然后，将剩余的一个与这些较大的元素进行比较。现在根据剩余元素是较小还是较大，分为两种情况，但在所有情况下都可以以仍然可用的三个比较完成。

我建议画图来帮助你。Knuth的图片大致是这样的:

   o---o
  /
 o---o

这显示了我们已经知道顺序的两个元素之间的连接线。拥有这样的图片可以帮助您确定要与哪些元素进行比较，因为您想进行一次能够提供最大信息量的比较。

添加说明：由于已经有一个带有实际代码的已接受答案，我想完成这些图表并且它们可能是答案的有用补充。所以，从上面开始，并将缺失的元素与左上角的元素进行比较。如果它更大，那么结果将是

    /--o
   o
  / \--o
 o
  \--o

现在，比较右上角两个大元素，我们得到：

   o---o---o
  /
 o---o

现在，通过首先将右下角的元素与顶部的中间元素进行比较，然后再将其与其属于的一侧进行比较，使用剩余的两个比较正确地放置它。

如果初始比较导致剩余元素较小，则图表变为：

 o---o---o
    /
   o---o

现在，比较两者，它们都没有比它们更小的。一种选择是上面的最后一个图表，可以使用剩余的两个比较来解决。另一种情况是

       o---o
      /
 o---o---o

这里再次，还没有与其他人序列化的那个可以通过两次比较正确地放置。

- JaakkoK

---

这就是应该的答案。它被称为 福特-约翰逊算法。 - Mohammad Jafar Mashhadi

Answer 2

是的，它在Knuth第3卷185页（第5.3.1节）中。这是首次记录在博士论文中，所以你的教授对你要求相当严格！没有真正简单优雅的方法；你必须将其作为部分有序树来跟踪。

下面是lisp代码。已经在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 a i) (aref a (+ 1 i)))  
    (assert (<= (aref a i) (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)  
        ))))  

- Tim J

---

不是那么难...同样的问题在我的算法课上向我提出。 - Chip Uni

你能为给定的数组长度生成排序函数吗？ - Janus Troelsen

我按照Knuth的描述重新实现了Ford-Johnson算法，并针对5个元素编写了您特定的函数。使用此算法对[0, 1, 2, 3, 4]的每个排列进行排序需要840次比较，而使用Ford-Johnson算法仅需要832次比较。我担心您的实现与Knuth所描述的不完全相同。 - Morwenn

这并不难也不罕见，我的教授在一次10分钟的测试中把它作为了一个选择题，只有两个问题。 - Yash Kumar Verma

@Morwenn，确实，以下8个序列似乎只需要6次比较；其他所有序列都需要7次。
升序时为：[0,3,1,2,4]， [0,3,2,1,4]， [1,2,0,3,4]， [1,2,3,0,4]， [2,1,0,3,4]， [2,1,3,0,4]， [3,0,1,2,4]， [3,0,2,1,4]
降序时为：[1,4,2,3,0]， [1,4,3,2,0]， [2,3,1,4,0]， [2,3,4,1,0]， [3,2,1,4,0]， [3,2,4,1,0]， [4,1,2,3,0]， [4,1,3,2,0]
5! * 7 = 340 - 8 = 832。 - Christopher Galpin

Answer 3

我认为硬编码的解决方案不需要太复杂：

1. 比较第2和第3个元素，如果需要则交换
2. 比较第3和第4个元素，如果需要则交换
3. 比较第1和第3个元素，如果第1个元素较小，则比较第1和第2个元素，否则比较第1和第4个元素。将第1个元素放入正确的位置。
4. 重复步骤3，但使用第3和第5个元素。

这将始终使用7次比较。

编辑：

我认为这不会起作用：步骤4是错误的，可能需要第8次比较。考虑：

Index | 1 | 2 | 3 | 4 | 5 |
Value | 2 | 3 | 4 | 5 | 1 |

步骤4：

1. 比较3和5 == 4与1 == 元素5小于元素3
2. 比较2和5 == 3与1 == 元素5小于元素2
3. ??? 需要比较1和5才能知道将元素5放在哪里。

- Douglas Leeder

---

1和5哪个更大？ - Mark Byers

Answer 4

看一下桶排序。

- monksy

---

桶排序不是一种比较排序，虽然它确实满足需要少于7次比较的条件，但我怀疑他的作业不会接受它作为正确答案。 - Mark Byers

是的，它不是一种比较排序，但需求文档哪里说必须使用比较排序呢？ - monksy

他说他需要找到一个“在最坏情况下使用7次比较”的算法。桶排序无法满足这一要求。 - Mark Byers

你仍然可以计算桶排序的比较次数。它从未说过必须使用比较排序算法。 - monksy

嗯，我不确定我能否使用非比较排序，但无论如何，考虑到数组中的元素可以是任何类型，有可能所有元素都会落入同一个桶中（哈希冲突），导致下一次排序将采用上述提到的那些耗时过长的方法之一... - CS n00b

Answer 5

7听起来也可能是shell类型的。

- GrayWizardx

---

嗯，刚刚实现了它，需要8次比较来处理5,4,3,2,1。 - CS n00b

Answer 6

桶排序可以实现为以下比较算法：

取一个元素。

将其与所有桶进行比较。

将其放入匹配的桶中。 <- 需要比较。

如果找不到桶，则创建一个新桶。

因此，这是一种动态桶排序算法，我刚刚描述了它。

我以前在新闻组中已经发明/描述了这个算法。

- oOo

---

这不是一种比较排序算法，当输入不包含重复元素时也不会使用更少的比较。 - Navin

与所有的钱相比，它并不需要比较吗？ - Yash Kumar Verma