给你一个整数数组 nums，请你将该数组升序排列。
示例：
输入：nums = [5,2,4,3,1]
输出：[1,2,3,4,5]
LeetCode: https://leetcode.cn/problems/sort-an-array/
class Solution {
func sortArray(_ nums: [Int]) -> [Int] {
var nums = nums
func fastsort(_ lo: Int, _ hi: Int) {
// 越界判断
if lo >= hi { return }
// 一般使用第0个值作为基准即可
// 这里随机取值防止极端情况出现O(N^2)复杂度
let mid = Int.random(in: lo ... hi)
// 记录基准值
let pivot = nums[mid]
// 变回熟悉的“一般使用第0个值作为基准即可”的情况
nums[mid] = nums[lo]
var i = lo, j = hi
while i < j {
// 找到右侧小于基准值的位置，填入左侧【坑位i】
while i < j, nums[j] >= pivot { j -= 1 }
nums[i] = nums[j]
// 找到左侧大于基准值的位置，填入右侧【坑位j】
while i < j, nums[i] <= pivot { i += 1 }
nums[j] = nums[i]
}
// i、j 重合，该坑位填入基准值
nums[i] = pivot
// 分别递归排序基准值左、右两侧数组
fastsort(lo, i - 1)
fastsort(i + 1, hi)
}
fastsort(0, nums.count - 1)
return nums
}
}
image.png
