题解 | #排序#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }

    // 快速排序
    public void quickSort(int[] arr, int start, int end) {
        // 指向同一个数字不用排序
        if (start >= end) {
            return;
        }
        // 以第一个数字为基准
        int tmp = arr[start];
        // 从左往右找的指针
        int i = start;
        // 从右往左找的指针
        int j = end;
        // 这一轮是否交换数字
        boolean isSwap = false;
        while (i < j) {
            // 新的一轮查找
            isSwap = false;
            // 从右往左找不大于基准数的坐标
            while (i < j && arr[j] > tmp) {
                j--;
            }
            // 从左往右找小于基准数的坐标
            while (i < j && arr[i] <= tmp) {
                i++;
            }
            // 指针没有碰头
            if (i < j) {
                // 交换两个数字,这里不能用基准数，基准数还有用
                int swapTmp = arr[i];
                arr[i] = arr[j];
                arr[j] = swapTmp;
                isSwap = true;
            }
        }
        // 与基准数交换
        if (!isSwap) {
            arr[start] = arr[j];
            arr[j] = tmp;
        }
        // 基准数左边都是小于等于基准数的
        quickSort(arr, start, j - 1);
        // 基准数右边都是大于基准数的
        quickSort(arr, j + 1, end);
    }
}