java—如何修改快速排序以使枢轴位于正确的位置

ycl3bljg  于 2021-07-09  发布在  Java
关注(0)|答案(1)|浏览(428)

考虑如下数组,

int[] a = {100, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 16};

考虑到中间元素总是作为轴心。

pivot = 10

标准的快速排序算法如下所示

public void quickSort(int[] a, int low, int high) {
        if (a == null || a.length == 0)
                return;

        if (low >= high)
                return;

        int pivotIndex = partition( a, low, high );
        quickSort(a, low, pivotIndex-1);
        quickSort(a, pivotIndex, high);
    }

    public int partition ( int[] a, int low, int high )
    {
        // pick the pivot
        int middle = low + (high - low) / 2;
        int pivot = a[middle];

        while (low <= high) {
            while (a[low] < pivot) {
                    low++;
            }

            while (a[high] > pivot) {
                    high--;
            }

            if (low <= high) {
                    swap( a, low, high );
                    low++;
                    high--;
            }
        }

        return low;
    }

完成while循环的一次迭代后(以10为中心),数组如下所示

high          low 
  10 1 2 3 4 5 100 11 12 13 14 15 16

如您所见,pivot元素位于索引0处,这不是10的正确位置。
我的问题是,如何修改上述算法,以便在每次迭代结束时,pivot元素都位于正确的位置,并且在不考虑pivot的情况下继续在左半部分和右半部分递归

vwoqyblh

vwoqyblh1#

如果目标是让pivot值在开始时处于正确的位置,那么代码可以对数组进行一次扫描,检查值是否小于、等于或大于pivot,例如生成三个计数:ltpivot=#elements<pivot value,eqpivot=#elements==pivot,gtpivot=#elements>pivot value(扫描只需要生成两个计数,第三个计数是(高+1-低-(计数的2))。然后所有的pivot值都应该移动到索引位置low+ltpivot到low+ltpivot+eqpivot-1。这可以通过另一个过程来完成,以将枢轴值交换到位。然后可以执行第三步,将小于或大于pivot的元素交换到pivot的左侧或右侧。
问题是,这种方法比标准快速排序慢,需要对阵列进行3次扫描,而标准快速排序只能进行一次扫描。标准的快速排序只会正确放置一个pivot元素,而将其他元素==pivot分散放置,但在典型情况下,这不是问题(标准快速排序的最坏情况之一是所有值都相同)。

相关问题