Java – 算法 – 快速排序

简介

快速排序指的是，开始先从0拿出一个初始索引值，指定 start 索引和 end 索引值，并对0索引进行对比，若start索引值比 初始索引值 大，那么start记录索引位置，end索引值若比 初始索引值 小，也记录索引值，此时 start 索引记录的是比 初始索引值 的值，end 索引值是记录比 初始索引值 小的值，然后start 和 end 索引值位置互换，最终如果 start 索引等于 end 索引，说明他们达到了数组中心，此时，中心值和 初始索引值 位置互换，即位初始索引值所处的数组位置。

快整排序原理

快整排序实现

        // 随机定义一个数组
        int[] arr = {5, 7, 9, 65, 53, 2, 654, 4327, 929, 33, 67, 14, 666, 12};

        // 使用快速排序进行数组排序

        int start = 0;
        int end = arr.length - 1;

        quickSort(arr, start, end);


        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }


    }

    private static void quickSort(int[] arr, int i, int j) {
        int index = arr[i];
        int start = i;
        int end = j;

        // 递归算法，如果两个索引超出了，就直接停止
        if (end < start) {
            return;
        }

        while (start != end) {

            // 结尾开始向前遍历对比
            while (true) {
                // 如果结尾找到比 index 值小的，就记录 end索引值
                if (arr[end] < index || end <= start) {
                    break;
                }
                end--;
            }

            // 开始索引向后遍历对比
            while (true) {
                if (arr[start] > index || start >= end) {
                    break;
                }
                start++;
            }

            // start 和 end 互换位置
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;

        }

        // 当start 和 end 都到达中间索引时，对初始值和中间值互换
        // 此时 该原始值的索引位置就应该中间值
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;

        // 对左边的组，进行递归调用，位置从 0 开始，结束在中间左边
        quickSort(arr, i, start - 1);
        // 对右边的组，进行递归调用，位置从 中间右边开始，结束在数组结尾
        quickSort(arr, start + 1, j);
        // 注意，此时start 和 end 在同一位置，所以end 和start 用那个都行
    }