难度：★★★☆☆
类型：数组
方法：二分法

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给你一个整数数组 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 <= 50000
-50000 <= nums[i] <= 50000

解答

排序是算法题中的基础。这里介绍一种常用的快速排序方法。

快速排序的思路很简单，选中一个数字，将所有小于等于这个数字的数字放在这个数字的左边，其他的放在这个数字的右边即可，通过重复的递归可以实现对于左右两边数字的排序。这里给出一种原地排序的代码，是通过交换实现的。

class Solution:
    def sortArray(self, nums):
        def quick_sort(array, l, r):
            if l < r:
                q = partition(array, l, r)
                quick_sort(array, l, q - 1)
                quick_sort(array, q + 1, r)

        def partition(array, l, r):
            x = array[r]
            i = l
            for j in range(l, r):
                if array[j] <= x:
                    array[i], array[j] = array[j], array[i]
                    i += 1
            array[i], array[r] = array[r], array[i]
            return i
        quick_sort(nums, 0, len(nums)-1)
        return nums

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析