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

Question

我实现了如下快速排序。在 partition 逻辑中，我到处都看到了两个指针（通过指针，我不希望指的是 C/C++ 指针，而是要遍历的简单变量），一个从头开始遍历数组（寻找大于枢轴的元素），从尾端开始遍历数组（寻找小于枢轴的元素）。

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

为了简单起见，我只使用了单指针并开始遍历元素，从开始到比我的枢轴元素所在的结束少一步。我假设我的枢轴位置在开始处，所以我保留了另一个变量来存储我的枢轴索引。如果我发现任何元素小于我的枢轴元素，那么我会在我假定的枢轴索引和我当前遍历的索引之间进行交换，并将我的枢轴索引增加 1。在循环结束时，我已经为我的枢轴准备好了位置，我 return。

我只是想知道如果我的方法比传递给Partition逻辑的数组从两端遍历的方法有缺点[左边遍历找大元素右边找小元素然后交换both ，继续这个直到左右遍历指针相互交叉。

请帮忙。感谢和问候

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;
    }

}

（该程序与我在 http://krishnalearnings.blogspot.in/2015/07/implementation-in-java-for-quicksort.html 中发布的程序相同，但现在我脑子里有这种困惑，我想纠正自己和我发布的内容）

Answer 1

你的pivot-index是第二个指针，所以算法具有相同的基本属性。但是请注意，它可能不太稳定：刚好超过枢轴索引的值可能会被交换，即使它小于枢轴，而传统算法会将其保留在原位。

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

Quick sort Partition Logic using single traversal pointer versus two left and right pointer

java

algorithm

quicksort

partition