介绍
快速排序(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),表示递归调用所使用的栈空间。这是因为每次递归调用时,只需要维护基准元素的位置和递归调用的边界索引,而不需要额外的辅助空间。