具有 6 个元素的数组成对比较的最佳情况，使用快速排序

Question

我正在分析以下问题：

问题5B

假设你使用快速排序对一个有 6 个元素的数组进行排序，并使用第一个元素作为基准。将进行多少次成对比较...

a) ...在最坏的情况下？ 答案：接受15（5+4+3+2+1）和20（6+5+4+3+2）

b) ...在最坏的情况下？ 答案：接受8（5+2+1）、10（6+3+1）和11（6+3+2）

我试图理解答案“8 (5+2+1)”。我无法想象 8 次比较的最佳情况。例如，如果数组是 [4,1,2,3,5,6]（枢轴是 4），它会检查 1-6、2-6、3-6、5-6，然后交换 5 和 4，然后有两个子数组 [1,2,3] 和 [5,6] 有 2 和 1 比较？

有人可以举个例子说明最好的情况是 8 次比较吗？

我尝试了不同的订单并在网上搜索...

Answer 1

让我们开始：

4 6 2 1 3 5

|- - |

这里我使用 - - 来显示接下来要比较的内容，而 | |是为了显示我们试图在枢轴上分割的范围。

对比后1.

4 2 1 3 5 6

|- - |

比较后2.

2 4 1 3 5 6
 |- -    |

比较后3.

2 1 4 3 5 6
   |- -  |

对比后4.

2 1 3 4 5 6
     |- -|

经过比较 5. 我们现在有 2 个范围。

2 1 3 4 5 6

|- - | |- -|

经过比较 6 和 7.

1 2 3 4 5 6
 |- -|

对比后8.

1 2 3 4 5 6

这就是 quicksort 仅通过 8 次比较就对其进行排序的方式。

Answer 2

使用 Lomuto 的 Quicksort 算法，使用最左边的值作为主元值，对于像 [3, 1, 2, 5, 4, 6] 这样的数组，我们可以获得低至 8 次比较。

在第一次迭代中，所有值都将与枢轴 3 进行比较（5 次比较），并且枢轴将被移动：与 2 交换，我们得到：

[2, 1, 3, 5, 4, 6]

更深的运行将有左分区 [2, 1]，其中只需要 1 次比较，枢轴 2 将移动到 1 所在的位置。

右分区 [5, 4, 6] 需要进行 2 次比较，并将枢轴值 5 放在中间。

这给我们留下了大小为 1 的分区，因此不会发生比较。

这里是 Lomuto Quicksort 算法的 JavaScript 实现，它执行上述数组的排序并输出最相关的操作以确认需要 8 次比较：

// Lomuto algorithm, with pivot at left side
function quickSort(arr, low, high) {

    function partition(arr, low, high) {
        let count = 0;
        const pivot = arr[low];
        let i = low;
        for (let j = low + 1; j <= high; j++) {
            count++; // Count next comparison
            console.log("compare", arr[j], "with pivot", pivot);
            if (arr[j] <= pivot) {
                i++;
                console.log("set partition index at", i);
                if (i < j) {
                    console.log("swap index", i, "with index", j);
                    [arr[i], arr[j]] = [arr[j], arr[i]];
                    console.log("swap result: ", ...arr);
                }
            }
        }
        console.log("swap pivot", pivot, "with partition index", i);
        [arr[i], arr[low]] = [arr[low], arr[i]];
        console.log("swap result: ", ...arr);
        return [i, count];
    }
    if (low >= high) return 0;
    
    const [i, count] = partition(arr, low, high);
    return count + quickSort(arr, low, i - 1) + quickSort(arr, i + 1, high);
}

const arr = [3, 1, 2, 5, 4, 6];
console.log("INITIAL:", ...arr);
const count = quickSort(arr, 0, arr.length - 1);
console.log("SORTED:", ...arr);
console.log("COMPARISONS:", count);