leetcode:排序数组

题目描述

给你一个整数数组 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]

题目地址：912. 排序数组

解题思路

  这道题目直接告诉你了要排序，关键是选中什么样的排序算法？题目的限制条件是有两个，第一是元素个数不超过 10k，这个不算大。 另外一个是数组中的每一项范围都是-50k到50k（包含左右区间）。

快速排序和归并排序都是分支思想来进行排序的算法， 并且二者都非常流行。 快速排序的核心点在于选择轴元素。

每次我们将数组分成两部分，一部分是比 pivot（轴元素）大的，另一部分是不比 pivot 大的。 我们不断重复这个过程， 直到问题的规模缩小的寻常（即只有一个元素的情况）。

快排的核心点在于如何选择轴元素，一般而言，选择轴元素有三种策略：

• 数组最左边的元素
• 数组最右边的元素
• 数组中间的元素（我采用的是这种，大家可以尝试下别的）
• 数组随机一项元素

代码:

var sortArray = function (nums) {

    const counts = Array(50000 * 2 + 1).fill(0);
    const res = [];
    for (const num of nums) counts[50000 + num] += 1;
        for (let i in counts) {
            while (counts[i]--) {
            res.push(i - 50000);
        }
    }
    return res;
};

总结：

快速排序的主要思想是通过划分将待排序的序列分成前后两部分，其中前一部分的数据都比后一部分的数据要小，然后再递归调用函数对两部分的序列分别进行快速排序，以此使整个序列达到有序。