【LeetCode】912. Sort an Array

【Description】
Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Constraints:

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

【Idea】
刷了点分治， 所以用快排来写。
分治的套路：
把当前问题拆成 2* n/2的子问题。结合快排每次遍历在子序列中找一个pivot并按此划分， 使得左边的无序子数组均<pivot， 右边的子数组均> pivot，以上作为子问题的解，不断拆解问题， 直到子数组为空。
其中，由n不断拆半， 拆解层复杂度是logn，子问题中寻找pivot的复杂度是n， 综合是O(nlogn)。（最坏是n2，一颗斜树

衍生一下其他排序：
冒泡： 每次遍历前->后，每两个邻近元素逆序对调，每次遍历完最后一个元素置位，直至不发生对调 || O(n2)
选择：每次遍历前->后，选择最小or最大的元素置位 || O(n2)
归并：将数组对折拆logn次，拆到单元素数组回升，变成两个有序数组的merge问题。变种题一般在merge中的判断上。 O(nlogn)

【Solution】

class Solution:
    def partition(self, nums, left, right):
        pivot = right
        i = left
        for j in range(left, right):
            if nums[j] < nums[right]:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[pivot] = nums[pivot], nums[i]
        return i

    def recursion(self, nums, left, right):
        if left >= right:
            return 
        mid = self.partition(nums, left, right)
        # print(mid)
        self.recursion(nums, left, mid-1)
        self.recursion(nums, mid+1, right)


    def sortArray(self, nums: List[int]) -> List[int]:
        left, right = 0, len(nums)-1
        self.recursion(nums, left, right)
        return nums