快速排序故障

Question

我正在快速地工作，但出于某种原因，我最终还是遇到了同样的问题。不知何故，即使我复制/粘贴应该工作的快速排序代码，我也总是在数组中的某个位置得到一个0的值。

public class quicksort {
public int[] x;
public quicksort(int a[]){
    x=a;
    procedure(0, x.length-1);
}
public void procedure(int left, int right){
    int index=left;
    int smaller=left+1;//going to sort everything but the first element (the pivot or index)
    int larger=right;
    int divider=x[index];

    while (smaller <= larger){
        for (int z=0; z<x.length-1;z++){//display the array at each pass
        System.out.print(x[z]+" ,");
    }
    System.out.println("|| "+smaller+" "+divider+" " +larger+" ||");

    while(x[larger] > divider ){ //stops at smaller then divider coming from the right
        larger--;
    }
    while(x[smaller] < divider){//stops at bigger then divider coming from the left
        smaller++;
    }

    if (smaller<=larger){//swaps two elements 
        swap(smaller, larger);
        smaller++;
        larger--;
    }
}

index= smaller + insert(left, smaller);//moves index to its final spot in the array 
//recursive call, split the array by the position of index and sort each
if (index < right-1)
    procedure(index+1, right);
if (index > left+1)
    procedure(left, index-1);
}   

public void swap(int z, int y){//swaps values between 2 array indexes
int temp;
temp =x[z];
x[z]=x[y];
x[y]=temp;
}

public int insert(int z, int y){//inserts a value from one index to the another index in the array, adjusts array as neccessary
    int it=0;
    if (x[z]>x[y]){ //if values are the same => easy swap
        swap(z,y);
        it=0;
    } else if (x[z] <= x[y]){         //if trying to insert to a bigger value 
        for (int f =z; f>y-1;f++)    //will swap values from the position z to 
            swap(f, f+1);             //position y (only works if z<y)
        it=-1;
    }
    return it;
    }
    }

我知道我也在重复递归调用，但首先我想知道为什么没有相应地进行交换。那里的输出只是为了让我能够在while循环上每次传递之后看到数组发生了什么。这是一个10整数数组的示例调试。

24 ,37 ,8 ,41 ,76 ,36 ,1 ,73 ,20 ,|| 1 24 9 ||
24 ,0 ,8 ,41 ,76 ,36 ,1 ,73 ,20 ,|| 2 24 8 ||
24 ,0 ,8 ,20 ,76 ,36 ,1 ,73 ,41 ,|| 4 24 7 ||
24 ,0 ,8 ,20 ,1 ,36 ,76 ,73 ,41 ,|| 5 24 5 ||

Answer 1

首先，对于快速排序，这段代码看起来非常复杂。看起来您想要实现Lomuto版本，但是代码中至少有一些不寻常的东西。

为了自己实现一个快速排序，我强烈建议阅读关于Lomuto的文章，看看它的典型实现方式。在这样的版本中，您可以得到：

->函数partition (它接受数组，选择一个枢轴，然后返回一个索引，在该索引中，在所有元素<=枢轴向左，所有元素>支点位于其右侧之后，就插入了这个索引)。

->函数quicksort，它将被递归地调用来对部分数组、枢轴的左边和枢轴的右侧进行排序。

洛穆托快速排序通常被认为比原来的更容易理解，由C.A.R.Hoare设计。但是，您也可以尝试使用Hoare的快速排序来获得更小的代码。

void quickSort(int left, int right, int tab[]){
     int i = left;
     int j = right;
     int buffer;
     int pivot = tab[(i+j)/2];

     do{
         while (tab[i] < pivot) i++;
         while (tab[j] > pivot) j--;
         if (i <= j){
                   buffer = tab[i];        //swap.
                   tab[i] = tab[j];
                   tab[j] = buffer;
                   i++;
                   j--;
         }
     }
     while (i <= j);

     if (left < j) qs(left, j, tab);
     if (i < right) qs(i, right, tab);
}