Swift刷算法：手撕快排

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