快速排序的核心操作就是划分,在(java数据结构与算法)中也单独将划分劈出一个章节来说,现在大家应该已经知道通过设置两个指针分别从数组的左右两侧向中间进行扫描的方式来实现划分操作(此方法就是排序––快速排序(二)中给出的一个初步划分方案,并且那是在特殊序列并选择了特殊轴枢元素情况下才容易让人理解),当随机选择一个不能将整个序列平均划分的时候个人认为该方法不太好理解,现按照自己的理解来写一个正确的快速排序代码,并尝试用该方法过度到通用方法中(这里要感谢我同事给我的帮助,因为根据他给的初步方法才有了下面的内容),该篇先写一个正确的划分代码。

1、假如让我们自己来实现一个划分算法,首先会从已知序列中选择一个元素作为轴枢(注意该选择是随机的,我们的重点先放在如何写一个正确的划分算法上面)。

2、从序列的左边开始扫描(设指针变量为i),如果遇到一个小于等于轴枢元素的数就直接跳过进行下个元素的比较;如果遇到一个大于轴枢的元素就要从下一个元素(设指针变量为j初始值为i+1)开始寻找一个小于等于轴枢的元素并与该元素交换。

3、当变量j到达序列的末尾时说明再也没有小于等于轴枢的元素了表示划分结束或者当变量i到达序列的末尾时说明序列所有的元素都小于等于轴枢元素,所以变量i的本质是左右序列的边界位置(边界位置的元素永远大于轴枢或者由于超过了序列的长度而不存在,或者换个说法i-1位置的元素小于等于轴枢元素),而变量j的本质是用来寻找小于等于轴枢元素的。当划分结束的时候还要将轴枢元素与i-1位置上的元素进行交换!这里假设序列共有元素n个,第一趟排序实际比较次数为n次。这与通常的划分算法(通过左右两边向中间扫描)比较次数一样,只是这里是由左向右的扫描方法,个人认为这种方式更好理解,代码如下:

public int partition(int from, int to) {
        int partPos = from;
        int ltePos = from + 1;
        int pivotPos = -1;
        while (true) {
            int comp = 0;
            while (partPos <= to && (comp = comparePivot(partPos)) <= 0) {
                if (comp == 0) {
                    pivotPos = partPos;
                }
                partPos++;
            }
            ltePos = partPos + 1;
            while (ltePos <= to && comparePivot(ltePos) > 0) {
                ltePos++;
            }
            if (partPos > to || ltePos > to) {
                break;
            }
            swap(partPos, ltePos);
        }
        int actPartPos = partPos - 1;
        swap(pivotPos, actPartPos);
        return actPartPos;
    }

09-14 02:26