我试图编写一个简单的算法来移动枢轴周围的元素,使得枢轴左侧的元素小于枢轴,并且枢轴右侧的元素大于它(快速排序中的相同步骤).我编写了可行的代码,但之后我将算法更改为以下内容,但它无效.

算法的想法很简单.

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 

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

实施中是否存在任何缺陷.逻辑对我来说似乎是正确的.我已经尝试了很长一段时间,但我无法解决它.

解决方法:

检查这个implementation.它完全按照相同的原则工作.尝试比较,看看你哪里出错了.

请注意,如果i <= j并且也从循环中断,则应该交换a [i]和[j]的值.你是在else上做的,这是错误的,因为如果a [i]大于枢轴并且当你到达if时a [j]小于枢轴,那么如果i< = j.