介绍

快速排序（Quick Sort）是一种常用的高效排序算法，它的基本思想是通过选择一个基准元素，将数组分割成两个子数组，其中一个子数组的所有元素都小于基准元素，另一个子数组的所有元素都大于基准元素。然后递归地对这两个子数组进行排序，最终达到整个数组有序的目的。

快速排序的具体步骤如下：

随机选择数组中的一个数 A，以这个数为基准（一般是第一个）
其他数字跟这个数进行比较，比这个数小的放在其左边，大的放到其右边
经过一次循环之后，A 左边为小于 A 的，右边为大于 A 的
这时候将左边和右边的数再递归上面的过程

代码示例

package main

import "fmt"

func quickSort(arr []int) []int {
    length := len(arr)
    if length < 2 {
        return arr
    }

    middle := arr[0]
    var left []int
    var right []int

    for i := 1; i < length; i++ {
        if middle < arr[i] {
            right = append(right, []int{arr[i]}...)
        } else {
            left = append(left, []int{arr[i]}...)
        }
    }

    middleNum := []int{middle}
    left = quickSort(left)
    right = quickSort(right)

    result := append(append(left, middleNum...), right...)
    return result
}

func main() {
    values := []int{3, 2, 1, 4, 6, 5}
    result := quickSort(values)
    fmt.Printf("Sorted Array: %v\n", result)
}

代码解释

判断数组的长度是否等于1，如果为1表示数组就一个元素，直接返回原数组。否则将数组的第一个值当做中间数。
创建两个空切片分别存储小于中间值和大于中间值的元素。通过遍历数组，将元素根据大小分别放入left和right数组。这里使用了临时切片[]int{arr[i]}，用于将单个元素arr[i]封装为切片，然后使用...运算符将临时切片的元素逐个追加到right切片的末尾。
创建一个只包含中间值的切片。
递归调用quickSort函数。在每次递归调用中，我们将左侧子数组作为参数传递给quickSort函数，以便对其进行排序。递归调用会重复这个过程，直到子数组的长度为0或1，即已经有序，不再需要继续排序。
append(left, middleNum...)表示将切片middleNum中的元素逐个追加到left切片的末尾。这样可以将左侧子数组和中间值拼接在一起。然后，append(append(left, middleNum...), right...) 表示将上一步中得到的结果切片再与右侧子数组right进行拼接。同样使用append函数，将左侧子数组、中间值和右侧子数组依次拼接在一起，形成最终的排序结果result。

上面的代码在每次递归调用时，都会创建新的left和right数组，这会导致额外的内存开销。可以优化为使用索引划分子数组而不是创建新的切片。

优化代码示例

package main

import (
    "fmt"
)

func quickSorted(nums []int, left, right int) {
    if left >= right {
        return
    }
    i, j := left, right
    // i从左边开始遍历，j从右边开始遍历。
    p := nums[i]
    // 设置基准数
    for i < j {
        for i < j && nums[i] < p {
            // 寻找一个比基准数大的数
            i++
        }
        for i < j && nums[j] > p {
            // 寻找一个比基准数小的数
            j--
        }
        nums[i], nums[j] = nums[j], nums[i]
        fmt.Println(nums)
        // 替换这两个数
    }
    nums[i] = p
    // 如果i和j相遇，就将基准数和i下标的值进行替换

    quickSorted(nums, left, i-1)
    quickSorted(nums, i+1, right)
}

func main() {
    a := []int{6, 5, 3, 1, 2, 4}
    quickSorted(a, 0, len(a)-1)
    fmt.Println(a)
}

[4 5 3 1 2 6]
[4 5 3 1 2 6]
[2 5 3 1 4 6]
[2 4 3 1 5 6]
[2 1 3 4 5 6]
[2 1 3 4 5 6]
[1 2 3 4 5 6]
[1 2 3 4 5 6]
[1 2 3 4 5 6]

代码解释

quickSorted 函数接受一个整数切片 nums、左边界 left 和右边界 right 作为参数。
首先，函数检查左边界是否大于等于右边界，如果是，则返回，表示已经完成排序。
接下来，函数使用两个指针 i 和 j 分别指向左边界和右边界。
选取 nums[i] 作为基准数 p。
然后，使用两个循环来寻找比基准数大和小的数，并进行交换。第一个循环从左边开始，找到第一个大于等于基准数的数；第二个循环从右边开始，找到第一个小于等于基准数的数。交换这两个数的位置，使得左边的数都小于等于基准数，右边的数都大于等于基准数。
在交换过程中，通过 fmt.Println(nums) 将每次交换后的数组打印出来，以便观察排序的过程。
当 i 和 j 相遇时，将基准数 p 放入正确的位置 nums[i]。
然后，递归调用 quickSorted 函数对基准数左边和右边的子数组进行排序。
最后，在 main 函数中，创建一个整数切片 a，并调用 quickSorted 函数对其进行排序。排序完成后，打印最终的排序结果。

复杂度

快速排序的时间复杂度为 O(n log n)，空间复杂度为 O(log n)。

在最坏情况下，快速排序的时间复杂度为O(n^2)。每次选择的基准元素都是当前子数组中的最小或最大元素，导致划分不平衡，递归树退化为一个单支树。这种情况通常发生在输入数组已经有序或近乎有序的情况下。
在最好情况下，快速排序的时间复杂度为O(n log n)。在每次划分都能将待排序数组均匀地划分为两个子数组的情况下，也就是说，每次选择的基准元素恰好是当前子数组的中位数。在这种情况下，递归树的高度为 log n，每层的比较次数为 n，因此总体的时间复杂度为 O(n log n)。
在平均情况下，快速排序的时间复杂度为 O(n log n)。这是因为快速排序采用分治的策略，每次划分都将待排序数组分为两部分，并通过递归地对子数组进行排序。在平均情况下，每次划分的基准元素都能大致均匀地将数组划分为两部分，因此递归树的高度大致为 log n，每层的比较次数为 n。因此，总体的时间复杂度为 O(n log n)。
快速排序的空间复杂度为 O(log n)，表示递归调用所使用的栈空间。这是因为每次递归调用时，只需要维护基准元素的位置和递归调用的边界索引，而不需要额外的辅助空间。

介绍

代码示例

代码解释

优化代码示例

代码解释

复杂度

相关文章