排序算法之三路划分的快速排序

排序算法之三路划分的快速排序

当待排序元素序列中有大量的重复排序码时，简单的快速排序算法的效率将会降到非常之低。一种直接的想法就是将待排序列分成三个子序列：一部分是排序码比基准元素排序码小的；一部分是与基准元素排序码等值的；一部分是比基准元素排序码大的，如下图所示：

图1  快速排序的三路划分
但是，如果我们直接据此思想去编写实现算法的话，会让我们面临很大的困难。与基准元素等值的元素到底有多少？以及如何最快速有效地确定划分的边界？所以，完成这样的三路划分是非常困难的，甚至比两路划分过程更加复杂。
我们可以基于以下的思想实现三路划分：在划分的过程中，扫描时将遇到的左子序列中与基准元素排序码等值的元素放到序列的最左边，将遇到的右子序列中与基准元素排序码等值的元素放到序列的最右边。这样，我们会得到如下所示的序列划分图：

图2  三路划分的实现方法
当两个扫描指针相遇时，排序码相等的元素的确切位置就知道了。然后我们只要将所有排序码与基准元素等值的元素与扫描指针指向的元素开始依次交换，就可以得到三路划分的结果了。
这个方法不仅有效地处理了待排序元素序列中的重复值问题，而且在没有重复值时它也能保持算法原来的性能。其优点是：
第一，如果元素序列中没有重复值，这个方法可以保持算法的效率，因为没有额外的工作要做；
第二，在每次话划分的过程中，都可以将与基准元素排序码相等的元素分割出来，所有拥有相同排序码值的元素不会参加多次划分。
代码

private void quickSort(int[] a, int left, int right) {
    if (right <= left)
        return;

    /*
    * 工作指针
    * p指向序列左边等于pivot元素的位置
    * q指向序列右边等于Pivot元素的位置
    * i指向从左向右扫面时的元素
    * j指向从右向左扫描时的元素
    */
    int p, q, i, j;
    int pivot;// 锚点
    i = p = left;
    j = q = right - 1;
    /*
    * 每次总是取序列最右边的元素为锚点
    */
    pivot = a[right];
    while (true) {
        /*
        * 工作指针i从右向左不断扫描，找小于或者等于锚点元素的元素
        */
        while (i < right && a[i] <= pivot) {
            /*
            * 找到与锚点元素相等的元素将其交换到p所指示的位置
            */
            if (a[i] == pivot) {
                swap(a, i, p);
                p++;
            }
            i++;
        }
        /*
        * 工作指针j从左向右不断扫描，找大于或者等于锚点元素的元素
        */
        while (left <= j && a[j] >= pivot) {
            /*
            * 找到与锚点元素相等的元素将其交换到q所指示的位置
            */
            if (a[j] == pivot) {
                swap(a, j, q);
                q--;
            }
            j--;
        }
        /*
        * 如果两个工作指针i j相遇则一趟遍历结束
        */
        if (i >= j)
            break;

        /*
        * 将左边大于pivot的元素与右边小于pivot元素进行交换
        */
        swap(a, i, j);
        i++;
        j--;
    }
    /*
    * 因为工作指针i指向的是当前需要处理元素的下一个元素
    * 故而需要退回到当前元素的实际位置，然后将等于pivot元素交换到序列中间
    */
    i--;
    p--;
    while (p >= left) {
        swap(a, i, p);
        i--;
        p--;
    }
    /*
    * 因为工作指针j指向的是当前需要处理元素的上一个元素
    * 故而需要退回到当前元素的实际位置，然后将等于pivot元素交换到序列中间
    */
    j++;
    q++;
    while (q <= right) {
        swap(a, j, q);
        j++;
        q++;
    }

    /*
    * 递归遍历左右子序列
    */
    quickSort(a, left, i);
    quickSort(a, j, right);
}

private void quick(int[] a) {
    if (a.length > 0) {
        quickSort(a, 0, a.length - 1);
    }
}

private void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

本文永久更新链接地址：