java快速排序

Java算法——java快速排序一、快速排序简介二、代码实现三、测试用例总结

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

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

代码如下（示例）：

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

        
        // 方法退出条件,指针相遇或错过
        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));
    }

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

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