912.排序数组 中等

问题：

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

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
解释：请注意，nums 的值不一定唯一。

回答：

方法一：

//快排，分治，找到基准点，分为左右两部分，并依次对两部分进行排序

var sortArray = function(nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
};
var quickSort = function(nums, left, right) {
    let flag = true;
    for (let i = left; i < right; i++) {
        if (nums[i] > nums[i + 1]) {
            flag = false;
            break;
        }
    }
    if (flag) {
        return nums;
    }
    var index = partition(nums, left, right);
    quickSort(nums, left, index - 1);
    quickSort(nums, index + 1, right);
}
var partition = function(nums, left, right) {
    let pivot = left + Math.floor(Math.random() * (right - left + 1));
    //基点元素移到最左侧
    [nums[pivot], nums[left]] = [nums[left], nums[pivot]];
    let i = left + 1;
    let j = right;
    //保证左侧都比基点小，右侧比基点大
    while (true) {
        while (i <= j && nums[i] < nums[left]) {
            i++;
        };
        while (i <= j && nums[j] > nums[left]) {
            j--;
        }
        if (i >= j) {
            break;
        }
        //交换位置
        [nums[i], nums[j]] = [nums[j], nums[i]]
        j--;
        i++;
    }
    //基点元素放回该在的位置
    [nums[left], nums[j]] = [nums[j], nums[left]];
    return j;
}

方法二：

堆排序，构建最大堆，堆顶存放最大元素，然后逐个把堆顶的元素和末尾交换位置，再进行堆的构建，重复直到得到结果

var sortArray = function(nums) {
    let len = nums.length;
    //构建堆，从最后一个非叶子结点开始
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        heapify(nums, len, i);
    }
    for (let i = len - 1; i >= 0; i--) {
        //把最大的值移到末尾
        [nums[0], nums[i]] = [nums[i], nums[0]];
        //剩下的堆，把最大值移到堆顶
        heapify(nums, i, 0);
    }
    return nums;
};

var heapify = function(nums, n, index) {
    let largest = index;
    let left = index * 2 + 1;
    let right = index * 2 + 2;
    if (left < n && nums[largest] < nums[left]) {
        largest = left;
    }
    if (right < n && nums[largest] < nums[right]) {
        largest = right;
    }
    if (largest != index) {
        [nums[largest], nums[index]] = [nums[index], nums[largest]];
        heapify(nums, n, largest)
    }
}