算法:快速排序
算法 About 1,853 words算法演进
以数组中间索引的元素为中轴值,分组左右两边两个数组。
左边数组遍历找到一个大于中轴值的数,右边数组遍历找到一个小于中轴值的数,进行交换,遍历完成,左边数组都是小于中轴值的数,右边数组都是大于中轴值的数,但左右两边的数组内部还不是有序的。
左右两组分别以取中轴值方式进行递归,完成排序。
func QuickSortEvolutionDemo() {
arr := []int{-9, 78, 0, 23, -567, 70}
QuickSortEvolution(arr, 0, len(arr)-1)
// 左边排序
QuickSortEvolution(arr, 0, (0+len(arr)-1)/2-1)
// 右边排序
QuickSortEvolution(arr, (0+len(arr)-1)/2+1, len(arr)-1)
}
func QuickSortEvolution(arr []int, left, right int) {
// 中轴值
var pivot = arr[(left+right)/2]
var l = left // 数组第0位
var r = right // 数组最后一位
for l < r {
for arr[l] < pivot { // 找到中轴左边比中轴值大的,暂停循环
l++ // 往中轴靠近,右移一位
}
for arr[r] > pivot { // 找到中轴右边比中轴值小的,暂停循环
r-- // 往中轴靠近,左移一位
}
if l >= r {
break
}
// 左边的值和右边的值交换
temp := arr[l]
arr[l] = arr[r]
arr[r] = temp
}
}
快速排序代码
func main() {
arr := []int{-9, 78, 0, 23, -567, 70}
QuickSort(arr, 0, len(arr)-1)
log.Println(arr)
}
func QuickSort(arr []int, left, right int) {
// 中轴值
var pivot = arr[(left+right)/2]
var l = left // 数组第0位
var r = right // 数组最后一位
for l < r {
for arr[l] < pivot { // 找到中轴左边比中轴值大的,暂停循环
l++ // 往中轴靠近,右移一位
}
for arr[r] > pivot { // 找到中轴右边比中轴值小的,暂停循环
r-- // 往中轴靠近,左移一位
}
if l >= r {
break
}
// 左边的值和右边的值交换
temp := arr[l]
arr[l] = arr[r]
arr[r] = temp
if arr[l] == pivot {
r--
}
if arr[r] == pivot {
l++
}
}
if l == r {
l++
r--
}
// 左边
if left < r {
QuickSort(arr, left, r)
}
// 右边
if right > l {
QuickSort(arr, l, right)
}
}
Views: 1,913 · Posted: 2021-02-09
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...