912. 排序数组

[webVueBlog]

912. 排序数组

Description

Difficulty: 中等

Related Topics: 数组, 分治, 桶排序, 计数排序, 基数排序, 排序, 堆（优先队列）, 归并排序

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

示例 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 <= 5 * 10⁴
• -5 * 10⁴ <= nums[i] <= 5 * 10⁴

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    // 快速排序
    function quickSort(start, end, arr) {
        if (start < end) {
            let mid = sort(start, end, arr);
            // 注意，一定要是 start mid , mid+1 end 这种组合
            // 否则当首位最大的时候(mid返回0)，将会无限循环
            quickSort(start, mid, arr);
            quickSort(mid+1, end, arr);
        }
        return arr;
    }

    function sort(start, end, arr) {
        // 取基准值
        let base = arr[start];

        let low = start;
        let high = end;

        while(low !== high) {
            // 从后往前，寻找比基准值小的值，赋给low位置(也就是取base值的位置)
            while(arr[high] >= base && high > low) {
                high--;
            }
            arr[low] = arr[high];
            // 从前往后，寻找比基准值大的值，赋给high位置
            while(arr[low] <= base && high > low) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = base;
        return low;
    }
    return quickSort(0, nums.length - 1, nums);
};