long龙8国际中文网

一个关于 编程问题的解答网站.

有 Java 编程相关的问题?

你可以在下面搜索框中键入要查询的问题!

使用单遍历指针与两个左右指针的java快速排序分区逻辑

我已经实现了如下的快速排序。在分区逻辑中,我在任何地方都看到了两个指针(通过指针我不希望指的是C/C++指针,但要遍历的简单变量),一个从开始遍历数组(查找大于pivot的元素),另一个从结束遍历数组(查找小于pivot的元素)

两个指针遍历的元素之和为N,即传递给分区逻辑的数组部分的大小

为了方便起见,我只使用了一个指针,开始遍历元素,从开始到距离轴元素所在的末端少一步。我假设我的轴心位置在起始位置,所以我保留另一个变量来存储轴心索引。如果我发现任何元素小于我的pivot元素,那么我在假设的pivot索引和当前遍历的索引之间进行交换,并将pivot-index增加1。在循环结束时,我准备好了旋转的位置,然后返回

我只想知道,与从两端遍历传递给分区逻辑的数组的方法相比,我的方法是否有缺点[在左遍历中找到较大的元素,在右遍历中找到较小的元素,然后交换这两个元素,继续这样做,直到左遍历指针和右遍历指针相互交叉]

请帮忙。 谢谢&;问候

package com.algorithm.sorting;

public class QuickSort {

    public static void main(String[] args) {
            int a[] = { 5, 33, 45454, 43254, 2, 67, 8, 78, 8, 8, 8, 85654, 5, 4, -1, -1, 1, 234, 24, 43, 4, -7, 45, 4, -5,
                            544, 9, 8, 7, 6, 5, 4, 3, 2, 11, 2, 3, 4, 5, 6, 7, 8, 9 };
            quicksort(a);
            for (Integer i : a) {
                    System.out.println(i);
            }
    }

    public static void quicksort(int[] array) {
            quicksort(array, 0, array.length - 1);
    }

    private static void quicksort(int[] array, int start, int end) {
            if (start < end) {
                    int pivotIndex = partition(array, start, end);
                    quicksort(array, start, pivotIndex - 1);
                    quicksort(array, pivotIndex + 1, end);
            }
    }

    private static int partition(int[] array, int start, int end) {
            int pIndex = start;
            int mid = start + ((end - start) / 2);
            int temp = array[mid];
            array[mid] = array[end];
            array[end] = temp;

            int pivot = array[end];

            for (int i = start; i <= end - 1; i++) {
                    if (array[i] < pivot) {

                            temp = array[i];
                            array[i] = array[pIndex];
                            array[pIndex] = temp;
                            pIndex++;
                    }
            }
            array[end] = array[pIndex];
            array[pIndex] = pivot;
            return pIndex;
    }

}

(该程序与我在中发布的程序相同,但现在我头脑中有了这种困惑,我希望纠正我自己和我发布的内容)


共 (1) 个答案

  1. # 1 楼答案

    pivot index是第二个指针,因此该算法具有相同的基本属性。但是,请注意,它可能不太稳定:刚刚超过枢轴索引的值可能会被交换,即使它小于枢轴,而传统算法会保留它