Java算法——java快速排序

一、快速排序简介

示例数组： int[] arr = {-9, 78, 0, 0, 1, 0, 3, -1, 23, -56, 7}
简介：快速排序，基于冒泡排序移动换位思想——通过遍历，判断每个数并放置在数组合适的位置。思路如下：

1. 选定一个基准值pivot（通常指定为数组第一个值），比基准值大的放在右侧，比基准值小的放在左侧
2. 指定左右两个指针分别为left，right ；left < right
3. 指定函数退出条件，即left > right
4. 先从右向左遍历，即右指针向左移动——right–操作，发现比pivot小的值暂停移动
5. 再从左向右遍历，即左指针向右移动——left++操作，发现比pivot大的值暂停移动
6. 交换左右指针发现的两个值的位置
7. 当两指针相遇，即left == right，当前值与pivot交换位置

二、代码实现

代码如下（示例）：

public static void quickSort(int[] array, int low, int high) {

        /**
         * 分析：
         * 1.选定一个基准值，array[low]
         * 2.右指针从右向左遍历high--，查找比基准值小的数据，左指针从左向右low++，查找比基准值大的数据
         * 3.如果指针未相遇，交换左右两值位置，如果指针相遇，则替换基准值的位置
         * 4.左递归，右递归
         */
        // 方法退出条件,指针相遇或错过
        if (low >= high) {
            return;
        }
        // 1. 指定基准值和左右指针记录位置
        int pivot = array[low];
        int l = low;
        int r = high;
        int temp = 0;
        // 2. 遍历条件，左右指针位置
        while (l < r) {
            // 2.1 右侧遍历
            while (l < r && array[r] >= pivot) {
                r--;
            }
            // 2.2 左侧遍历
            while (l < r && array[l] <= pivot) {
                l++;
            }
            // 2.3 l指针还在r指针左侧，尚未相遇
            if (l < r) {
                temp = array[l];
                array[l] = array[r];
                array[r] = temp;
            }
        }
        // 3. 当左右指针相遇，交换基准值位置
        array[low] = array[l];
        array[l] = pivot;
        // 4. 根据条件左侧递归遍历
        if (low < l) {
            quickSort(array, low, l - 1);
        }
        // 5. 根据条件右侧递归遍历
        if (r < high) {
            quickSort(array, r + 1, high);
        }
        
    }

三、测试用例

代码如下（示例）：

public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 0, 1, 0, 3, -1, 23, -56, 7};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

总结

1. 此处用int数组实现，需要理解以下内容
2. 理解左右指针暂停条件，保证基准数左侧都小于等于基准数，保证基准数右侧都大于等于基准数
3. 函数退出条件，遍历操作退出条件
4. 当指针相遇的时候，交换基准值与当前值位置
5. 当指针相遇并交换基准值位置后，此时数组以基准值为界，逻辑上分为左右两个数组；左侧都小于等于基准值，右侧都大于等于基准值；此时使用递归思路，分别操作左右两个逻辑数组；
6. 递归方法的左右指针以及基准值已经变动——通过校正左右指针边界，确保基准值不再次参与排序
7. 理解条件判断的边界，画图辅助

说明：记录仅做参考，有不当之处，请包涵、指正