以首元素为基准的6元素数组Quicksort最优比较次数解析

问题背景：假设使用Quicksort对包含6个元素的数组进行排序，且以第一个元素作为基准元素，最优情况下的比较次数包含8（5+2+1）的情况。

具体示例数组 #

选择数组：[3, 1, 4, 2, 5, 6]，基准元素为第一个元素3（数组的中位数，即第3小的元素，这是最优划分的前提）。

我们采用Hoare分区法（快速排序中比较次数较少的分区实现）来拆解每一步的比较次数：

第一步：对整个数组进行划分（基准=3）

1. 左指针从索引1开始，右指针从索引5开始：
   • 比较1和3（1<3），左指针移到索引2 → 第1次比较
   • 比较4和3（4>3），左指针停止 → 第2次比较
   • 比较6和3（6>3），右指针移到索引4 → 第3次比较
   • 比较5和3（5>3），右指针移到索引3 → 第4次比较
   • 比较2和3（2<3），右指针停止 → 第5次比较
2. 交换索引2和3的元素，数组变为[3, 1, 2, 4, 5, 6]；继续移动指针后左指针>=右指针，将基准3与右指针位置的2交换，最终数组为[2, 1, 3, 4, 5, 6]。
3. 此步骤共5次比较，得到两个子数组：[2, 1]（长度2）和[4, 5, 6]（长度3）。

第二步：排序子数组[4, 5, 6]（基准=4）

1. 左指针从索引1开始，右指针从索引2开始：
   • 比较5和4（5>4），左指针停止；比较6和4（6>4），右指针移到索引1，左指针>=右指针，基准4位置正确 → 第1次比较
2. 得到子数组[5, 6]，排序时比较6和5（6>5），交换后完成排序 → 第2次比较
3. 此步骤共2次比较。

第三步：排序子数组[2, 1]（基准=2）

1. 比较1和2（1<2），左指针移到索引1，右指针在索引1，左指针>=右指针，将基准2与1交换完成排序 → 第1次比较
2. 此步骤共1次比较。

总比较次数 #

5（整体划分） + 2（[4,5,6]排序） + 1（[2,1]排序） = 8次，完全匹配答案中的8（5+2+1）。

核心要点：必须选择中位数作为基准，让划分后的子数组长度尽可能均衡，同时使用Hoare分区法减少冗余比较，才能达到最少的8次两两比较。

内容的提问来源于stack exchange，提问作者kaviar