algorithm - 如果在 Hoare 快速排序中比较的元素相同怎么办？

Question

考虑一个未排序的列表 9,3,5,3,9，其中 5 是主元。当比较索引 0 和索引 4 处的元素时，它们的值彼此相等，并且都大于基准值。在这种情况下会发生什么？它们不能互换，因为“小于”部分仍然有 9。是刚搬到另一边的 9 之一。 3 也是如此。他们会怎样？

Answer 1

这些元素不会相互比较。在 Hoare 分区方案中，数组从左侧扫描第一个元素 > pivot，然后从右侧扫描第一个元素 < pivot。这意味着第一次交换将是数组 [0] = 9 和数组 [3] = 3。之后不再发生交换。根据 Hoare 分区的实现和数据模式，主元可以作为左分区的最后一个元素或右分区的第一个元素结束。等于 pivot 的元素留在左分区或右分区中，并在以后的递归中处理。