package main
import (
"fmt"
)
func main() {
var arr = []int{9, 4, 7, 6, 8, 3, 2, 5, 1}
fmt.Println("before", arr)
quickSort(arr, 0, len(arr)-1)
fmt.Println("after ", arr)
}
/*****************************************************************************
* \author
* \date
* \brief 递归快排
* \param[in] arr:待排序切片 startIndex,endIndex:起始,结束索引
* \param[out]
* \return 输入返回值描述
* \ingroup 输入所属组
* \remarks
*****************************************************************************/
func quickSort(arr []int, startIndex, endIndex int) {
// 递归结束条件:startIndex大等于endIndex的时候
if startIndex >= endIndex {
return
}
// 得到基准元素位置
var pivotIndex = partition(arr, startIndex, endIndex)
// 根据基准元素,分成两部分递归排序(分治法)
quickSort(arr, startIndex, pivotIndex-1)
quickSort(arr, pivotIndex+1, endIndex)
return
}
func partition(arr []int, startIndex, endIndex int) int {
// 取第一个位置的元素作为基准元素
var pivot = arr[startIndex]
var left = startIndex // 0
var right = endIndex // 8
for left != right {
//控制right指针比较并左移
for left < right && arr[right] > pivot {
right--
}
//控制right指针比较并右移
for left < right && arr[left] <= pivot {
left++
}
//交换left和right指向的元素
if left < right {
arr[left], arr[right] = arr[right], arr[left]
}
}
//pivot和指针重合点交换
arr[left], arr[startIndex] = arr[startIndex], arr[left]
return left
}
2022.6.8
/ 热度:792
/ 分类:
golang
发表评论: