Java教程

快速排序实现 (Java)

本文主要是介绍快速排序实现 (Java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

快速排序实现

  • 核心:找到支点,将小于支点的元素放到左侧,大于支点的元素放到右侧
public void quickSort(int []nums, int left, int right){
    if(left < right){
        int i = partition(nums, left, right) ; // 确定支点位置
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }
}

private int partition(int[] nums, int start, int end){
    int random = new Random().nextInt(end - start + 1) + start;
    int p1 = start - 1; // 小于random位置整数的前一个位置
    int p2 = start;     // 当前判断的位置

    swap(nums, random, end);    // 将支点交换到最后一个位置
    while(p2 < end){
        if(nums[p2] < nums[end]){
            p1++;
            swap(nums,p1, p2);
        }
        p2++;
    }
    //将支点放到最后一个小于支点位置的后一个位置
    p1++;
    swap(nums, p1, end);
    return p1;
}

private void swap(int[] nums, int i, int j){
    if(i != j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
这篇关于快速排序实现 (Java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!