Java中的Inplace Quicksort

Z时代
2024-01-10
分类：问答

为了刷新一些Java，我尝试实现一种可以对整数数组进行排序的quicksort（inplace）算法。以下是到目前为止的代码。您可以通过拨打电话sort(a,0,a.length-1)。

如果两个“指针”均指向i,j与支点值相同的数组条目，则该代码显然会失败（陷入无限循环）。枢轴元素v始终是当前分区的最右边（索引最大的分区）。

但是我无法弄清楚如何避免这种情况，有人看到解决方案了吗？

static void sort(int a[], int left, int right)   {
    if (right > left){
        int i=left, j=right-1, tmp;
        int v = a[right]; //pivot
        int counter = 0;
        do {
            while(a[i]<v)i++;
            while(j>0 && a[j]>v)j--;
            if( i < j){
                tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        } while(i < j);
        tmp = a[right];
        a[right] = a[i];
        a[i] = tmp;
        sort(a,left,i-1);
        sort(a,i+1,right);
    }
}

回答：

这应该可以工作（ ~~稍后将检查正确性~~ ，！）：

编辑：我以前在错误检查中犯了一个错误。我忘了增加2个条件，这是修改后的代码。

public static void main (String[] args) throws java.lang.Exception
{
    int b[] = {10, 9, 8, 7, 7, 7, 7, 3, 2, 1};
    sort(b,0,b.length-1);
    System.out.println(Arrays.toString(b));
}
static void sort(int a[], int left, int right)   {  
   if (right > left){
    int i=left, j=right, tmp;    
    //we want j to be right, not right-1 since that leaves out a number during recursion
    int v = a[right]; //pivot
    do {
        while(a[i]<v)
          i++;
        while(a[j]>v) 
        //no need to check for 0, the right condition for recursion is the 2 if statements below.
          j--;
        if( i <= j){            //your code was i<j
           tmp = a[i];
           a[i] = a[j];
           a[j] = tmp;
           i++;            
           j--;
           //we need to +/- both i,j, else it will stick at 0 or be same number
        }
   } while(i <= j);           //your code was i<j, hence infinite loop on 0 case
    //you had a swap here, I don't think it's needed.
    //this is the 2 conditions we need to avoid infinite loops
    // check if left < j, if it isn't, it's already sorted. Done
    if(left < j)  sort(a,left,j);
    //check if i is less than right, if it isn't it's already sorted. Done
    // here i is now the 'middle index', the slice for divide and conquer.
    if(i < right) sort(a,i,right);
  }

}

IDEOne在线编译器中的此代码

我们确保如果i / j的值与数据透视表相同，我们也将交换该值，并中断递归。

另外，在伪代码中检查了长度，就好像我们已经对它排序的数组只有一项（

）一样，我以为我们需要这样做，但是由于您传入了索引和整个数组，而不是子数组，我们只增加i和j，这样算法就不会停留在0（它们完成了排序），但仍然继续对数组1进行排序：:)

另外，我们必须添加2个条件来检查数组是否已针对递归调用进行排序。没有它，我们将永远永远对已经排序的数组进行排序，从而导致另一个无限循环。看看我如何添加检查是否小于j和小于i。同样，在传入i和j的那一点上，i有效地是我们分割以进行分而治之的中间索引，而j将是恰好在中间值之前的值。

它的伪代码来自RosettaCode：

function quicksort(array)
    if length(array) > 1
        pivot := select any element of array
        left := first index of array
        right := last index of array
        while left ≤ right
            while array[left] < pivot
                left := left + 1
            while array[right] > pivot
                right := right - 1
            if left ≤ right
                swap array[left] with array[right]
                left := left + 1
                right := right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)