快速排序問題

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 Quicksort，並查看它實現的典型方式。在這樣的版本，則得到：

- >功能partition（這需要您的陣列，選擇一個樞軸，然後返回一個索引，在該您的樞軸所有元素< =樞軸之後插入是其左側和所有元素>樞軸在它的右邊）。

- >功能quicksort它將被遞歸地調用來對部分數組進行排序，在樞軸的左邊和樞軸的右邊進行排序。

Lomuto Quicksort通常被認爲比由C.A.R.設計的原版更容易理解。霍爾。但是，您也可以嘗試使用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); 
}