快速排序

  1. 算法思想:分治法,比大小再分区。
  2. 过程:
    1. 从数组中选出一个数,作为基准数。
    2. 分区:将比这个数大或等于的数全放到他的右边,小于他的数全放到他的左边。
    3. 再对左右区间重复第二步,直到各区间只有一个数。
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {10, 3, 5, 6, 1, 0, 100, 40, 50, 8};
        System.out.println(Arrays.toString(quickSort(arr, 0, arr.length - 1)));
    }

    private static int[] quickSort(int[] arr, int start, int end) {
        if (start < end) {
            // 获取基准数索引
            int index = getIndex(arr, start, end);
            // 左右递归
            quickSort(arr, start, index - 1);
            quickSort(arr, index + 1, end);

        }
        return arr;
    }

    private static int getIndex(int[] arr, int start, int end) {
        int i = start;
        int j = end;
        // 基准数
        int x = arr[i];
        while (i < j) {
            // 基准数右边排序
            while (i < j && arr[j] >= x) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }

            //基准数左边排序
            while (i < j && arr[i] < x) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }

        // i=j
        return i;
    }

}
Copyright © rootwhois.cn 2021-2022 all right reserved,powered by GitbookFile Modify: 2022-11-26 20:03:31

results matching ""

    No results matching ""