快速排序(Quick Sort)的核心源码主要包含一个分治算法,具体实现如下:
基准点选择
选择数组最右边的值作为基准点(pivot)。
分区操作
遍历数组,将小于基准点的值移到基准点左边,大于基准点的值移到基准点右边。
返回基准点的新索引。
递归排序
对基准点左右两边的子数组分别进行递归排序。
```go
package main
import "fmt"
func partition(arr []int, left, right int) ([]int, int) {
// 1. 基准点值,取最右边的值
pivot := arr[right]
// 2. 新的基准点索引
p := left
for i := left; i < right; i++ {
if arr[i] < pivot {
arr[i], arr[p] = arr[p], arr[i]
p++
}
}
// 3. 把每一个分治出来的数据,再进行递归
arr[p], arr[right] = arr[right], arr[p]
return arr, p
}
func quickSort(arr []int, left, right int) []int {
if left < right {
p, _ := partition(arr, left, right)
quickSort(arr, left, p-1) // 新基准点p,左边再分区
quickSort(arr, p+1, right) // 新基准点p,右边再分区
}
return arr
}
func main() {
arr := []int{3, 6, 8, 10, 1, 2, 1}
fmt.Println("Before sorting:", arr)
quickSort(arr, 0, len(arr)-1)
fmt.Println("After sorting:", arr)
}
```
建议
快速排序是一种高效的排序算法,适用于大数据集。
在实际应用中,可以根据具体需求选择不同的实现方式,例如对于小数组可以使用插入排序以提高效率。
理解和掌握快速排序的核心思想和实现细节,有助于优化算法性能和提高编程能力。