题14

Q:对 8 个元素的序列进行快速排序, 在最好情况下的关键字比较次数是 ( )
A. 7 B. 8 C. 12 D. 13

A:每个序列有n个元素，就要进行n-1此比较
最好的情况是每次都能将序列分成两个相等的子序列
对于子序列，他的长度是原来是1/2，那么就要进行子序列长度-1次比较，也就是n/2-1次比较

假设我们有以下 8 个元素的数组：
- [5, 2, 9, 3, 7, 6, 1, 8]
我们选择第一个元素 “5” 作为基准元素
快速排序的第一趟目标是：将小于等于 5 的元素放到 5 的左边，大于 5 的元素放到 5 的右边
- 最终，5 会被放到一个特定的位置，这个位置左边所有元素都比它小，右边所有元素都比它大
比较过程：
- 5 vs 2: 5 > 2，2 保持在 5 左边
- 5 vs 9: 5 < 9，9 需要移动到 5 的右边
- 5 vs 3: 5 > 3，3 保持在 5 左边
- 5 vs 7: 5 < 7，7 需要移动到 5 的右边
- 5 vs 6: 5 < 6，6 需要移动到 5 的右边
- 5 vs 1: 5 > 1，1 保持在 5 左边
- 5 vs 8: 5 < 8，8 需要移动到 5 的右边
经过这 7 次比较，我们确定了哪些元素应该放在 5 的左边，哪些元素应该放在 5 的右边
最终结果：
- [2, 3, 1, 5, 9, 7, 6, 8]
关键点：
- 我们并不是要将数组完全排序，只需要将元素相对于基准元素 5 做好划分
- 在这个过程中，需要将基准元素与其他 7 个元素进行比较，才能确定基准元素的最终位置以及其他元素的相对位置
总结：
- 对于 8 个元素的数组，在第一趟快速排序中，我们需要进行 7 次比较才能确定基准元素的最终位置
- 同理，对于 n 个元素的数组，第一趟快速排序需要 n-1 次比较

最好情况：
- 快速排序的最好情况是每次划分都能将数组分成两个长度相等或相差1的子数组。这样可以保证递归树的层数最少，比较次数也最少。
递归过程:
- 第一趟: 8个元素，需要7次比较（与每个元素比较）才能确定基准元素的位置，并将数组划分成两个长度为3和4的子数组。
- 第二趟:
  - 长度为3的子数组需要2次比较完成划分 (与除了基准元素外的元素比较).
  - 长度为4的子数组需要3次比较完成划分。
- 第三趟:
  - 只有一个长度为2的子数组需要划分，需要1次比较。
总比较次数: 7 + 2 + 3 + 1 = 13

YiNotes