NOTE
3.14 快速排序
1. 快速排序 采用了分而治之的思想，就是说把一个大的问题分成小的问题，然后递归求解 快速排序想选取一个pivot，比他小的移动到左边，比他大的移动到右边， 对左边的小数组和右边的小数组做同样的处理 如果说归并排序的关键在于合并，那么快速排序的关键在于拆分 2. 效率 - 稳定性：不稳定 - 原地排
这是历史学习笔记，可能存在过时或不完整的理解。
1. 快速排序
采用了分而治之的思想，就是说把一个大的问题分成小的问题，然后递归求解 快速排序想选取一个pivot，比他小的移动到左边，比他大的移动到右边， 对左边的小数组和右边的小数组做同样的处理 如果说归并排序的关键在于合并，那么快速排序的关键在于拆分
2. 效率
- 稳定性：不稳定
- 原地排序：是
- 复杂度
- 时间：平均O（nlogn），最坏O（n²）
- 空间：O（logn）
3. 过程
4. 实现
4.1. 单路快排
//O(NlogN)
func QuickSort(data []model.Comparable) {
quickSort(data, 0, len(data)-1)
}
func quickSort(data []model.Comparable, left int, right int) {
if left >= right {
return
}
p := partition(data, left, right)
quickSort(data, left, p-1)
quickSort(data, p+1, right)
}
func partition(data []model.Comparable, left int, right int) int {
//data[left+1...j] < v; data[j+1...i] >= v
j := left
for i := left + 1; i <= right; i++ {
if data[i].CompareTo(data[left]) < 0 {
j++
util.Swap(data, i, j)
}
}
util.Swap(data, left, j)
return j
}4.1.1. 测试
func TestQuickSort(t *testing.T) {
e1 := model.NewElement(1)
e2 := model.NewElement(2)
e3 := model.NewElement(3)
data := []model.Comparable{e2, e1, e3}
fmt.Println(data)
QuickSort(data)
fmt.Println(data)
}4.1.2. 优化
- 对于有序数组每次只会拆分一个，效率下降到O(N²)
- 添加随机化
func partition(data []model.Comparable, left int, right int) int {
//生成[l, r]之间的随机索引
p := left + util.RandInt(0, right-left)
util.Swap(data, left, p)
//data[left+1...j] < v; data[j+1...i] >= v
j := left
for i := left + 1; i <= right; i++ {
if data[i].CompareTo(data[left]) < 0 {
j++
util.Swap(data, i, j)
}
}
util.Swap(data, left, j)
return j
}4.2. 双路排序
//O(NlogN)
func QuickSort2(data []model.Comparable) {
quickSort2(data, 0, len(data)-1)
}
func quickSort2(data []model.Comparable, left int, right int) {
if left >= right {
return
}
p := partition2(data, left, right)
quickSort2(data, left, p-1)
quickSort2(data, p+1, right)
}
func partition2(data []model.Comparable, left int, right int) int {
//生成[l, r]之间的随机索引
p := left + util.RandInt(0, right-left)
util.Swap(data, left, p)
//data[left+1...j] <= v; data[j+1...i] >= v
i := left + 1
j := right
for {
for i <= j && data[i].CompareTo(data[left]) < 0 {
i++
}
for j >= i && data[j].CompareTo(data[left]) > 0 {
j--
}
if i >= j {
break
}
util.Swap(data, i, j)
i++
j--
}
util.Swap(data, left, j)
return j
}4.2.1. 测试
func TestQuickSort2(t *testing.T) {
e1 := model.NewElement(1)
e2 := model.NewElement(2)
e3 := model.NewElement(3)
data := []model.Comparable{e2, e1, e3}
fmt.Println(data)
QuickSort2(data)
fmt.Println(data)
}4.3. 三路排序
//O(NlogN)
func QuickSort3(data []model.Comparable) {
quickSort3(data, 0, len(data)-1)
}
func quickSort3(data []model.Comparable, left int, right int) {
if left >= right {
return
}
//生成[l, r]之间的随机索引
p := left + util.RandInt(0, right-left)
util.Swap(data, left, p)
// data[l+1, lt] < v, data[lt+1, i-1] == v, data[gt, r] > v
lt := left
i := left + 1
gt := right + 1
for i < gt {
if data[i].CompareTo(data[left]) < 0 {
lt++
util.Swap(data, i, lt)
i++
} else if data[i].CompareTo(data[left]) > 0 {
gt--
util.Swap(data, i, gt)
} else {
i++
}
}
util.Swap(data, left, lt)
quickSort3(data, left, lt-1)
quickSort3(data, gt, right)
}
4.3.1. 测试
func TestQuickSort3(t *testing.T) {
e1 := model.NewElement(1)
e2 := model.NewElement(2)
e3 := model.NewElement(3)
data := []model.Comparable{e2, e1, e3}
fmt.Println(data)
QuickSort3(data)
fmt.Println(data)
}4.4. 常见的实现
package sort
import (
"my_algorithm/model"
)
//O(NlogN)
func QuickSort2Again(data []model.Comparable) {
quickSort2Again(data, 0, len(data)-1)
}
func quickSort2Again(data []model.Comparable, left int, right int) {
if left >= right {
return
}
p := partition2Again(data, left, right)
quickSort2Again(data, left, p-1)
quickSort2Again(data, p+1, right)
}
func partition2Again(data []model.Comparable, left int, right int) int {
pivot := data[left]
for left < right {
for left < right && data[right].CompareTo(pivot) >= 0 {
right--
}
data[left] = data[right]
for left < right && data[left].CompareTo(pivot) <= 0 {
left++
}
data[right] = data[left]
}
data[left] = pivot
return right
}
4.4.1. 测试
func TestQuickSort2Again(t *testing.T) {
e1 := model.NewElement(1)
e2 := model.NewElement(2)
e3 := model.NewElement(3)
data := []model.Comparable{e2, e1, e1, e3}
fmt.Println(data)
QuickSort2Again(data)
fmt.Println(data)
}