912. 排序数组

给你一个整数数组 nums，请你将该数组升序排列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

解决方案

快排。思路参见《啊哈！算法》第1章第3节：最常用的排序——快速排序。

class Solution {

    private int[] array;

    public int[] sortArray(int[] nums) {
        array = nums;
        quickSort(0, nums.length - 1);
        return nums;
    }

    private void quickSort(int begin, int end) {
        if (begin >= end) {
            return ;
        }
        int middle = partition(begin, end);
        quickSort(begin, middle - 1);
        quickSort(middle + 1, end);
    }

    private int partition(int begin, int end) {
        int pivot = array[begin];
        int ptr1 = begin, ptr2 = end;

        while (ptr1 < ptr2) {
            while (ptr1 < ptr2 && array[ptr2] >= pivot) {
                ptr2 -= 1;
            }
            while (ptr1 < ptr2 && array[ptr1] <= pivot) {
                ptr1 += 1;
            }
            if (ptr1 < ptr2) {
                int tmp = array[ptr1];
                array[ptr1] = array[ptr2];
                array[ptr2] = tmp;
            }
        }

        array[begin] = array[ptr1];
        array[ptr1] = pivot;

        return ptr1;
    }

}