912. 排序数组

发表于： 分类于：
字数： 640 阅读：≈ 2分钟 浏览：

https://leetcode.cn/problems/sort-an-array/

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

解题思路

  1. 排序题，快排

代码 

// 快速排序
func quickSort(nums []int) {
    // 递归终止条件
    if len(nums) < 2 {
        return
    }
    // 随机选择基准值
    pivotIndex := rand.Intn(len(nums))
    pivot := nums[pivotIndex]
    // 分区
    left, right := 0, len(nums)-1
    for left <= right {
        for nums[left] < pivot {
            left++
        }
        for nums[right] > pivot {
            right--
        }
        if left <= right {
            nums[left], nums[right] = nums[right], nums[left]
            left++
            right--
        }
    }
    // 递归
    quickSort(nums[:right+1])
    quickSort(nums[left:])

    return
}

快排太常见了，但是好久没碰，我实际码代码的时候遇到了不少问题，正好整理一下。

  1. 快排的核心思想就是把无序的序列根据一个基准值分成2份无序的序列，宏观上，两份序列有序。再对这两份无序的序列做同样的处理。
  2. 有一些边界情况需要考虑：
    1. 有相同值，这个时候，为了确保相同值之间的值能参与排序，需要跳过相同的值或者交换相同的值；
    2. 为了防止死循环，在分成2份序列的时候，不能出现某个序列为空的情况。如 [1,6]，6为基准值，他可能会分成 [1,6] 和 []，然后陷入死循环；
    3. left 和 right 每一轮交换后，可能会有3种情况
      1. 基准值和另一个可以交换的值。这种情况，基准值会变化位置。这个时候，left 和 right 都可能指向基准值。
        • right 指向基准值左边的一个值，left 指向基准值
        • right 指向基准值，left 指向基准值右边的一个值
      2. 只有一个基准值。这个时候 left 和 right 在基准值两侧
      3. 没有基准值。基准值提前被交换掉了，right 指向一个比基准值小的值，left 指向一个比基准值大的值，且相邻
    4. 每轮交换后，left 和 right 终态一定是 left 在 right 右边
    5. 根据2、3和4，下一轮的分组应该取 [0:right] 和 [left:len-1]