欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速排序原理与代码

程序员文章站 2022-03-24 13:16:12
...

1原理
我们必须首先确定一个基准数,使得序列中比基准数小的数都在左边,比基准数大的数都在右边。如何确定基准数?其实可以任意,不过一般取第一个数或者序列中间位置的数,我们这里取第一个数为基准数

public class QuickSort {
 public static void main(String[] args) {
        int[] nums = {3, 1, 4, 2, 5, 0};
        quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
    public static void quickSort(int[] nums, int start, int end) {//在调用quickSort时,start为0,end为数组长度减一
        int i = start;
        int j = end;
        int temp = nums[start];
        while (i < j) {
            while (i < j && nums[j] >= temp) {
                j--;
            }
            nums[i] = nums[j];
            while (i < j && nums[i] <= temp) {
                i++;
            }
            nums[j] = nums[i];
        }
          nums[i] = temp;//当i==j时,i就是基准数应该摆放的位置
        if (i > start + 1) {
        //为什么要start+1?因为如果是i>start,有可能是i刚好比start大1,此时就没有必要进行快排,因为i和start位置的俩元素必然有序
            quickSort(nums, start, i - 1);
        }
        if (j < end - 1) {//end-1原理同上
            quickSort(nums, j + 1, end);
        }
    }
}
相关标签: java java