【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
image.png
