快速排序分区调整

Question

但我想弄清楚我该怎么做，所以我可以选择我想要的任何轴心点，例如在这个整数列表中，8、7、1、9、11、5、6，我希望选择键 6 作为我代码中的轴心点。或者如果我想选择 9 或其他。我怎么能把它写到我的代码中？非常感谢任何帮助。

package quicksort;

public class quicky {
    private static void quicksort(int[] arr, int left, int right) {
        int index = partition(arr, left, right);
    
        if(left < index - 1)
            quicksort(arr, left, index - 1);
        if(index < right)
            quicksort(arr, index, right);
    }
    private static int partition (int[] arr, int left, int right) {
        int pivot = arr[(left + right) / 2];
        while(left<= right) {
            while(arr[left] < pivot) left++;
            while(arr[right]> pivot) right--;
        
            if(left<= right) {
                int tmp = arr[left];
                arr[left] =arr[right];
                arr[right] = tmp;
            
                left++;
                right--;
            }
        }
        return left;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] array = new int [] { 8, 7, 1, 9, 11, 5, 6};
        quicksort(array, 0 , array.length-1);
        for(int i = 0; i <array.length; i++)
            System.out.print(array[i]+ " ");        
        }        
    }
}

Answer 1

在你的代码中

private static int partition (int[] arr, int left, int right) {
/*
Here in below code only you need to make your changes and that needs to be through out the same as you are calling this from quicksort also you need to make use of the left and right for that, as everytime you will be passing that otherwise it will be static value. 

like you can do 
int pivot = arr[left] // for left most as pivot, if you want the last one then have arr[right] as pivot, right now you have mid element as pivot.
*/        
int pivot = arr[(left + right) / 2];
        

        while(left<= right) {
            while(arr[left] < pivot) left++;
            while(arr[right]> pivot) right--;
        
            if(left<= right) {
                int tmp = arr[left];
                arr[left] =arr[right];
                arr[right] = tmp;
            
                left++;
                right--;
            }
        }
        return left;
    }

Answer 2

简单方法：

检查数组中是否存在值。
如果是，则将值与默认枢轴索引中的值交换。
使用相同的代码/lomuto 分区继续。

快速排序分区调整

Quick sort partition tweak

java

arrays

algorithm

sorting

quicksort