java - 在 Pivot 上对数组进行分区

Question

我正在尝试编写一个简单的算法来围绕枢轴移动元素，使得枢轴左侧的元素小于枢轴，而枢轴右侧的元素大于它(快速排序中的相同步骤).我编写了有效的代码，但之后我将算法更改为以下，但它不起作用。

算法的思路很简单。

Have two pointers, one at the beginning of the array and one at the end of array. If the elements pointed by i are lesser than pivot, keep skipping it until we find a greater element; and keep decrementing j until we find an element greater than the smaller element. [It is a common algorithm]

现在是代码

private  static void sortByPivot(int[] a)
{

    Random r = new Random();
    int index = r.nextInt(a.length);
    int pivot = a[index];

    System.out.println("pivot = " + pivot);

    int i =0 , j = a.length -1;

    while(true)
        {

            while(a[i] <= pivot) i++;

            while( j >0 && a[j] >= pivot) j--;

            if(i <= j)
            {
                break;
            }
            else{
                swap(a,i,j);
               }

        }

        swap(a,i,index); //swap the pivot and the i
}

交换例程:

private static void swap(int[] a, int i , int j)
{
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

当我用下面的数组运行它时

  int[] a = {46,3,8,4,2,6,244,76} 

当枢轴被选为 4 时 输出是

         4 3 8 46 2 6 244 76 

对于边缘中的其他一些枢轴，我得到一个空指针异常。

执行中是否存在缺陷。这个逻辑对我来说似乎是正确的。我已经尝试了一段时间，但我无法修复它。

Answer 1

检查这个implementation .它的工作原理完全相同。试着比较一下，看看哪里出了问题。

请注意，您应该交换 a[i] 的值和 a[j]如果i <= j并且也打破了循环。你是在 else 上做的，这是错误的，因为如果 a[i]大于枢轴和a[j]当你到达 if 时小于枢轴，那么它们应该被交换 if i <= j .