1. 什么是快速排序？
快速排序是由英国计算机科学家托尼·霍尔在1960年代初发明的一种排序算法。它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。
2. 快速排序的工作原理
2.1 选择基准
在数组中选择一个元素作为"基准"。
2.2 分割
重新排列数组，使得比基准小的元素在基准之前，比基准大的元素在基准之后。这一步完成后，基准就处于数组的中间位置。
2.3 递归排序
递归地将基准前后的子数组排序。
3. 快速排序的代码实现
代码语言：javascript复制
package qk
import (
"math/rand"
)
func Quicksort(arr []int) []int {
if len(arr) < 2 {
return arr
}
left, right := 0, len(arr)-1
pivot := rand.Intn(len(arr))
arr[pivot], arr[right] = arr[right], arr[pivot]
for i := range arr {
if arr[i] < arr[right] {
arr[i], arr[left] = arr[left], arr[i]
left
}
}
arr[left], arr[right] = arr[right], arr[left]
Quicksort(arr[:left])
Quicksort(arr[left 1:])
return arr
}
单元测试和基准测试：
package qk
import (
"math/rand"
"reflect"
"sort"
"testing"
)
func TestQuicksort(t *testing.T) {
type args struct {
arr []int
}
tests := []struct {
name string
args args
want []int
}{
// TODO: Add test cases.
{name: "empty array", args: args{arr: []int{}}, want: []int{}},
{name: "already sorted array", args: args{arr: []int{1, 2, 3, 4, 5}}, want: []int{1, 2, 3, 4, 5}},
{name: "reverse sorted array", args: args{arr: []int{5, 4, 3, 2, 1}}, want: []int{1, 2, 3, 4, 5}},
{name: "random array", args: args{arr: rand.Perm(100)}, want: func() []int {
arr := rand.Perm(100)
sort.Ints(arr)
return arr
}()},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
if got := Quicksort(tt.args.arr); !reflect.DeepEqual(got, tt.want) {
t.Errorf("Quicksort() = %v, want %v", got, tt.want)
}
})
}
}
func BenchmarkQuicksort(b *testing.B) {
for i := 0; i < b.N; i {
arr := rand.Perm(1000)
Quicksort(arr)
}
}
基准测试效果：
goos: windows
goarch: amd64
pkg: github.com/xilu0/uml/20230812
cpu: AMD Ryzen 7 6800H with Radeon Graphics
BenchmarkQuicksort-16 10497 112277 ns/op
PASS
4. 快速排序的性能
- 时间复杂度：平均时间复杂度为O(n log n)，最坏情况为O(n^2)。
- 空间复杂度：O(log n)，用于递归调用的堆栈空间。
5. 快速排序的优缺点
- 优点：排序速度快，平均性能好。
- 缺点：不稳定，最坏情况性能较差。
总结
快速排序是一种非常高效和广泛应用的排序算法。通过理解其分而治之的策略和递归实现，我们可以更深入地了解计算机科学中的一些基本概念和技巧。
不管是学习算法还是在实际项目中选择合适的排序算法，了解快速排序的内部工作原理都是非常有用的。希望这篇文章能够帮助你掌握快速排序的精髓，并将其应用到你的编程实践中。
