Quicksort没有完全排序提供的数组

Question

我的Quicksort似乎停止在完全排序数组之前，并且我盲目地盯着代码。

private static <T extends Comparable<T>> void quickSort(T[] array,int min, int max){ 

    int pIndex; 

    if (max-min > 0) { 

     pIndex = partition(array, min, max); 

     quickSort(array, min, pIndex-1); 

     quickSort(array, pIndex+1, max); 

    } 
} 

：设计和使用的数据结构（第3版）

快速排序 -

我根据Java软件结构中的相关章节写的算法分区：

private static <T extends Comparable<T>> int partition(T[] array, int min, int max) { 

    int left, right; 
    T pivot, temp; 
    int middle = (min+max)/2; 

    left = min; 
    right = max; 
    pivot = array[middle]; 

    while (left < right) { 

     while (array[left].compareTo(pivot) <= 0 && left < right) 
     left++; 

     while (array[right].compareTo(pivot) > 0) 
     right--; 

     if (left<right) { 
      temp = array[left]; 
      array[left] = array[right]; 
      array[right] = temp; 
     } 

    } 

    temp = array[min]; 
    array[min] = array[right]; 
    array[right] = temp; 

    return right; 
} 

输入：
包含值的int[10]阵列0至9，混洗。
快速排序功能因此被称为像：quicksort(nums, 0, nums.length-1)

输出（例如）：

0 
2 
1 
3 
7 
4 
5 
6 
8 
9 

正如你所看到的，最终产品似乎在途中稍微有一个良好的最终产品，但它在某个地方过早停止。

更新：
到目前为止提供的答案（删除的文件在内）的无工作。如果没有人能够发现错误，那么是否有人会将我重定向到Java中的泛型算法的良好源代码？

我甚至可耻地试图从上面提到的书中完成Quicksort算法的纯副本，并在编译和运行时产生与上面相同的“几乎正确”的输出。然后我质疑它是否可能是我的输入数据，但不是。它只是一个整数数组，没有重复。这是我理解的有效候选人。

Answer 1

我能够快速排序，使用下面的分区函数对一些测试数组进行排序。

private static <T extends Comparable<T>> int partition(T[] array, int min, int max) { 

    int left, right; 
    T pivot, temp; 
    int middle = (min+max)/2; 

    left = min; 
    right = max ; 
    pivot = array[middle]; 

    while (left < right) { 

     while (array[left].compareTo(pivot) < 0 && left < right) 
      left++; 

     while (array[right].compareTo(pivot) > 0) 
      right--; 

     if (left<right) { 
      temp = array[left]; 
      array[left] = array[right]; 
      array[right] = temp; 
     } 
    } 
    return right; 
} 

我改变的只是第一个compareTo比较小于等于小于等于。这允许枢轴在阵列中移动。但是，这确实意味着数组不可以包含重复项。我也删除了最后一次交换，因为我不知道它在做什么。

问题源于您如何处理数据透视。它实际上并未正确分区阵列。

---

这也适用，并允许重复。

private static <T extends Comparable<T>> int partition(T[] array, int min, int max) { 
    int left, right; 
    T pivot, temp; 
    int middle = (min+max)/2; 

    left = min + 1; 
    right = max ; 
    pivot = array[middle]; 

    // move partition element to min index 
    temp = array[min]; 
    array[min] = array[middle]; 
    array[middle] = temp; 

    while (left < right) { 

     while (array[left].compareTo(pivot) <= 0 && left < right) 
      left++; 

     while (array[right].compareTo(pivot) > 0) 
      right--; 

     if (left<right) { 
      temp = array[left]; 
      array[left] = array[right]; 
      array[right] = temp; 
     } 

    } 

    // move partition element to partition index 
    temp = array[min]; 
    array[min] = array[right]; 
    array[right] = temp; 
    return right; 
} 

我抬头看了一本书的副本。评论告诉你最后一次交换试图做什么。这使得我在求解中添加交换的修复将分区元素移动到min索引是正确的修复。

Answer 2

while (array[left].compareTo(pivot) <= 0 && left < right) 
    left++; 

while (array[right].compareTo(pivot) > 0) 
    right--; 

这些循环通常写：

while (array[left++].compareTo(pivot) <= 0 && left < right) 
    ; 

while (array[right--].compareTo(pivot) > 0) 
    ; 

的想法是停在第一个元素不此分区属于。