图解Java排序算法之快速排序的三数取中法

什么是快速排序

快速排序是一种常见的排序方法，它的特点是在待排序的记录序列中，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分的记录关键字均比另一部分的关键字小。

快速排序的基本流程

快速排序的基本流程如下：

1. 从数列中挑出一个元素，称为“基准”（pivot）。
2. 对数列重新排序，将比基准值小的元素放在基准前面，比基准值大的元素放在基准后面，相同的数可以放在任意一边。
3. 在分成的两个小数列中，分别递归地进行步骤1和步骤2。

在实现快速排序算法时，我们需要选择一个“基准”元素，以便对数列进行分割，进而进行递归排序。如何选择基准元素，对快速排序的效率有着重要的影响。

三数取中法

三数取中法是选择基准元素的一种方法。这种方法的基本思想是从数列的前、中、后三个元素中选出一个中间值作为基准。

三数取中法的具体实现过程如下：

private static int median3(int[] a, int left, int right) {
    int center = (left + right) / 2;
    // 保证 left < center < right
    if (a[left] > a[center]) {
        swap(a, left, center);
    }
    if (a[left] > a[right]) {
        swap(a, left, right);
    }
    if (a[center] > a[right]) {
        swap(a, center, right);
    }
    swap(a, center, right - 1);
    return a[right - 1];
}

其中，median3方法接收三个参数，分别是待排序数组a、待排序数组左边界left、待排序数组右边界right。该方法的返回值为中位数。

三数取中法的优点是能够较好地避免最坏情况的发生，进而提高快速排序的效率。

示例说明

以一个待排序数组为例进行说明。假设该数组为：[5, 4, 3, 2, 1]。这时，我们需要先进行“三数取中”操作，以便选择到一个合适的基准元素。在该数组中，选择left=0和right=4，则center=2。比较a[left]、a[center]和a[right]三个元素的大小关系，并将其按照从小到大的顺序排列，即a[left] <= a[center] <= a[right]。排列后，交换a[center]和a[right-1]位置上的元素，将a[center]作为基准值。此时的待排序数组变为：[3, 4, 1, 2, 5]。

接下来，我们需要将该数组按照基准元素3进行分割，将小于等于3的元素放在基准左侧，大于3的元素放在基准右侧。经过一次分割，数组变为：[1, 2, 3, 4, 5]。此时，数组已经有序，排序完成。