题目

快速排序

讲解

讲解

讲解

class Solution {
    public int[] sortArray(int[] nums) {
        sort(0,nums.length,nums);
        return nums;
    }

    public void sort(int begin, int end, int[] nums) {
        if (end - begin < 2) return;
        int pivot = pivotIndex(begin,end,nums);
        sort(begin,pivot,nums);
        sort(pivot + 1,end,nums);
    }

    private int pivotIndex(int begin, int end, int[] nums) {

        // 随机选择一个元素跟begin位置进行交换 (降低出现最坏排序的概率)
        swap(begin, begin + (int)(Math.random() * (end - begin)),nums);
        int pivot = nums[begin];
        end--;
        while (begin < end) {
            while (begin < end) {
                if (nums[end] <= pivot) {
                    nums[begin++] = nums[end];
                    break;
                } else {
                    end--;
                }
            } 
            while (begin < end) {
                if (nums[begin] >= pivot) {
                    nums[end--] = nums[begin];
                    break;
                } else {
                    begin++;
                }
            }   
        }
        nums[begin] = pivot;
        return begin;
    }

   private void swap(int i1, int i2,int[] nums) {
        int tmp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = tmp;
    }

}