题解 | #排序#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        // 快速排序，解题思路：
        // 1.双指针，分别指向left/right
        // 2.取第一个元素值cur，从最右边开始如果大于cur就right--
        // 遇到第一个小于的值就把left 和 right交换
        // 3.继续从左边比较，左边的值是否都小于cur，就left++
        // 遇见大于等于cur的值，就把left和right 交换
        // 当不满足left < right 时候，说明cur就位置他应该存在的位置
        // 然后继续递归  begin，left-1  和  left+1，end
        quickSort(arr, 0, arr.length-1);
        return arr;
    }

    private void quickSort(int[] arr, int begin, int end) {
        if (begin >= end) {
            return;
        }

        int left = begin;
        int right = end;
        int cur = arr[left];

        while (left < right) {

            while (left < right && arr[right] >= cur) {
                right--;
            }

            if (left < right) {
                swap(arr,  left,  right) ;
            }

            while (left < right && arr[left] <= cur) {
                left++;
            }

            if (left < right) {
                swap(arr,  left,  right) ;
            }
        }
        quickSort( arr,  begin, left - 1);
        quickSort( arr, left + 1,  end);
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}