冒泡排序、归并排序、快速排序(2)

// 快速排序
    public static void quickSort (int[] arr, int left, int right) {
        // 先将异常情况处理掉
        if (arr == null || arr.length < 2) {
            return;
        }
        if (right <= left) {
            return;
        }
        if (right - left == 1 && arr[left] <= arr[right]) {
            return;
        }
        // 取第一个数为基准数(基数取哪个都行，此处是为了方便)
        int index = arr[left];
        int i = left + 1; // 左指针
        int j = right; // 右指针
        while (i < j && i < right && j > left) { // 设置指针的移动边界
            while (arr[j] > index && j > left) {j--;} // 找到从右边数第一个比index小的数
            while (arr[i] < index && i < right) {i++;} // 找到从左边数第一个比index大的数
            if (i < j) { // 交换这两个数  如果i == j，说明二者定位到了同一个位置，则不用交换；如果i > j，说明二者已经相遇然后背向而行了，也不交换
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 执行完上面循环后，arr已经是左边比index小，右边比index大的数组了，只是基准数仍在基准位置left处，需放到它应该在的位置
        if (j != left && arr[j] != arr[left]) {
            // j最后停留位置的数，肯定是一个小于等于index的值，所以如果不是同一个位置的话，直接将二者调换一下位置即可
            int temp = arr[j];
            arr[j] = arr[left];
            arr[left] = temp;
        }
        quickSort(arr, left, j-1); // 将基准数左边排序
        quickSort(arr, j+1, right); // 将基准数右边排序
    }

Linux公社的RSS地址：https://www.linuxidc.com/rssFeed.aspx