[Go版]算法通关村第十关青铜——快速排序

快速排序(quickSort)

快速排序(quickSort)的核心思想是:选择一个基准元素,然后将数组划分为两部分,一部分小于基准,一部分大于基准,然后对这两部分分别递归排序。

速度测试:800万数据排序仅需3秒

  • 选择排序法:8万数据耗时11、12秒
  • 插入排序法:8万数据耗时4、5秒
  • 快速排序法:8万、80万数据耗时0秒,800万数据耗时3秒

思路分析:二分查找 + 左右双指针 + 递归

  1. 确定数组二分查找的范围start、end,确定一个要比较的值midVal,使用左右双指针left、right找到要替换的位置进行替换
  2. 比较替换完一个for循环之后,将得到数组的left左边都是比midVal小的值,right右边都是比midVal大的值。(接下来就类似二叉树的前序遍历,分别递归其左子树和右子树)
  3. 再确定二分查找的范围:此时应该缩小至start 到 rightleft 到 end两个区间范围。继续上述1、2、3步骤递归调用排序即可。

复杂度:平均时间复杂度 O ( n l o g n ) O(nlog n) O(nlogn)、平均空间复杂度 O ( l o g n ) O(log n) O(logn)

  • 时间复杂度: 快速排序的平均时间复杂度为 O ( n l o g n ) O(nlog n) O(nlogn),其中 n 是待排序数组的长度。

    • 最好情况下,每次分区都能将数组划分为近似相等的两部分,时间复杂度最小。
    • 最坏情况下,每次分区都只能将数组划分为一个元素和 n-1 个元素,此时时间复杂度为 O ( n 2 ) O(n^2) O(n2)
    • 但是由于快速排序具有较好的平均情况时间复杂度,实际应用中通常表现良好。
  • 空间复杂度: 快速排序的空间复杂度主要取决于递归调用栈的深度。

    • 最好和平均情况下,快速排序的递归调用栈深度为 O ( l o g n ) O(log n) O(logn),因此空间复杂度为 O ( l o g n ) O(log n) O(logn)
    • 最坏情况下,递归调用栈深度为 O ( n ) O(n) O(n),空间复杂度为 O ( n ) O(n) O(n)
    • 另外,快速排序是一种原地排序算法,它不需要额外的存储空间来存储临时数组,所以除了递归调用栈外,不需要额外的空间。

题目链接:LeetCode-912. 排序数组

写法1-Go代码

func sortArray(nums []int) []int {
    length := len(nums)
    if length == 0 || length == 1 {
        return nums
    }
    sortArr(nums, 0, length-1)
    return nums
}

func sortArr(nums []int, left int, right int) {
    if left >= right {
        return
    }
    start, end := left, right
    mid := (right-left)>>1+left
    midVal := nums[mid]
    for left <= right {
        for left<=right && nums[left] < midVal {
            left++
        }
        for left<=right && nums[right] > midVal {
            right--
        }
        if left<=right {
            nums[left], nums[right] = nums[right], nums[left]
            left++
            right--
        }
    }
    sortArr(nums, start, right)
    sortArr(nums, left, end)
}

写法2-Go代码

func sortArray(nums []int) []int {
    length := len(nums)
    if length == 0 || length == 1 {
        return nums
    }
    sortArr(nums, 0, length-1)
    return nums
}
func sortArr(nums []int, start int, end int) {
    if start >= end {
        return
    }
    left, right := start, end
    midVal := nums[left]
    for left < right {
        // 从右边找到一个 <midVal的值
        for left<right && nums[right] > midVal {
            right--
        }
        // 将右边小的值赋给左边left位置,left指针走一步
        if left < right {
            nums[left] = nums[right]
            left++
        }
        // 从左边找到一个 >midVal的值
        for left<right && nums[left] < midVal {
            left++
        }
        // 将左边大的值赋给右边Right位置,Right指针走一步
        if left < right {
            nums[right] = nums[left]
            right--
        }
        
    }
    nums[left] = midVal
    sortArr(nums, start, left-1)
    sortArr(nums, left+1, end)
}