java 中的快速排序分区失败

Question

我知道有很多关于快速排序的内容，但我只是用它来学习如何编写算法代码，从您所看到的情况来看，我显然不会。


    public static int[] partition(int [] arr, int startNumber, int endNumber) {
        
        //highIndex is the second last element, lowIndex the first, pivot the last.
        
        int highIndex = endNumber -2;
        int pivot = arr [endNumber -1];
        int lowIndex = startNumber;
        
        
        // I don't want the loop to initiate when the element from the left aligns with the element from the right
        // thus it should stop when arr[highIndex] equals arr[lowIndex].
        while (highIndex > lowIndex) {
            
            
            // the index increases as we go from the left to right without the element being greater than the pivot
            // or the index equal or greater to the index from the right
            while (arr[lowIndex] <= pivot && highIndex > lowIndex) {
                lowIndex++;
            }
            
            while (arr[highIndex] > pivot && highIndex > lowIndex) {
                highIndex--;
            }
            
            // interchanging the elements which are greater and less than the pivot. 
            
             int temp = arr[highIndex];
             arr[highIndex] = arr[lowIndex];
             arr[lowIndex] = temp;
            
        }
        
        //changing the pivot with the element arr[highIndex]. But arr[highIndex] should be equal to arr[lowIndex]
        // at this point so it shouldn't matter if I'm changing with low or high. 
        int temp2= arr[highIndex];
        pivot = arr[highIndex];
        arr[highIndex] = temp2;
    
        
        return arr;
        
        
    }
    
    public static void main(String[] args) {
        
        int [] arr2 = {21, 24, 13, 25, 27, 5, 2, 20, 6, 23};  
        
        System.out.println( Arrays.toString(arr2));
        
        partition(arr2,0, arr2.length);
        
        System.out.println(Arrays.toString(arr2));
        
    }

此代码生成： [21, 24, 13, 25, 27, 5, 2, 20, 6, 23] [21, 6, 13, 20, 2, 27, 5, 25, 24, 23]

枢轴没有改变位置。我正在尝试以 23 作为基准对其进行分区。

Answer 1

您的代码至少有 1 个问题：

在最后一部分，在主 while 外部 (highIndex > lowIndex)，当你认为你替换了 pivot，实际上你没有，但是你分配给了 temp2 和 pivot 变量arr[highIndex] 中的内容以及分配给 arr[highIndex] = temp2（本身）之后的内容。我相信这是一个粗心的错误，正确的代码是：
```
  int temp2= arr[highIndex];
  arr[highIndex] = pivot;
  arr[endNumber-1] = temp2;
```

此修复后，您需要实施算法的最后一部分。

java 中的快速排序分区失败

Failed partitioning for quicksort in java

java

quicksort

partition