具有重复值的快速排序

Question

我有用于QuickSort的这个Java代码，如果没有重复项，则工作，但如果存在任何重复项，则QuickSort失败。例如，如果我想要QuickSort {5,3,3,1,7}我的代码将输出{1,3,3,7,5}，而我似乎无法弄清楚为什么会出现这种情况。

public static void quickSort(Integer[] nums) { 
    quickSort(nums, 0, nums.length-1); 
} 

private static void quickSort(Integer[] ary, int lo, int hi) { 
    //pick num @ lo to be pivot 
    int pivot = lo; 
    int i = lo+1; 
    int j = hi; 


    if(lo==hi) { 
     return; 
    } 

    while(i <j) { 

     if(ary[i].compareTo(ary[pivot]) <=0 ) { 
      i++; 

     } 
     else if(ary[j].compareTo(ary[pivot]) >=0) { 
      j--; 
     } 
     else { 
      int temp = ary[i]; 
      ary[i] = ary[j]; 
      ary[j] = temp; 

     } 

    } 
    if(i == hi && j == hi) { 
     if(ary[pivot].compareTo(hi) > 0) { 
      int temp = ary[pivot]; 
      ary[pivot] = ary[hi]; 
      ary[hi] = temp; 
      pivot = hi; 

     } 
     else { 
      int temp1 = ary[pivot]; 
      ary[pivot] = ary[i-1]; 
      ary[i-1] = temp1; 
      pivot = i-1; 

     } 

    } 
    if(lo < pivot -1) { 
     quickSort(ary, lo, pivot-1); 
    } 

    if(pivot +1 < hi) { 
     quickSort(ary, pivot+1, hi); 
    } 

} 

如果有人能告诉我什么，我做错了，那将不胜感激！

Answer 1

嗨，我已经修改了你的代码，请检查相应的注解

private static void quickSort(Integer[] ary, int lo, int hi) { 
//pick num @ lo to be pivot 
int pivot = lo; 
int i = lo+1; 
int j = hi; 

if(lo==hi) { 
    return; 
} 

//while(i <j) { 
for(;;){//change from while to infinite for 
    while(ary[i].compareTo(ary[pivot]) <=0 && i<hi) {//changed from if to while with boundary conditions 
     i++; 

    } 
    while(ary[j].compareTo(ary[pivot]) >0 && j>lo) { //change from if to while with boundary conditions and it is not >=0 only > 
     j--; 
    } 
    if(i<j){ //changed from else to if 
     int temp = ary[i]; 
     ary[i] = ary[j]; 
     ary[j] = temp; 

    }else{//added else block 
     break; 
    } 
} 
//you didn't handled i>j condition properly i.e when i>j you need to swap pivot and i-1 
int temp1 = ary[pivot]; 
    ary[pivot] = ary[i-1]; 
    ary[i-1] = temp1; 
    pivot = i-1; 
//Not required 
/*if(i == hi && j == hi) { 
    if(ary[pivot].compareTo(hi) > 0) { 
     int temp = ary[pivot]; 
     ary[pivot] = ary[hi]; 
     ary[hi] = temp; 
     pivot = hi; 

    } 
    else { 
     int temp1 = ary[pivot]; 
     ary[pivot] = ary[i-1]; 
     ary[i-1] = temp1; 
     pivot = i-1; 

    } 

}*/ 

if(lo < pivot -1) { 
    quickSort(ary, lo, pivot-1); 
} 

if(pivot +1 < hi) { 
    quickSort(ary, pivot+1, hi); 
} 
} 

感谢

Answer 2

如果你想快速使用该网站的算法。

Quicksort

它为我和解释是相当不错的，我认为。