算法:快速排序
算法 大约 1853 字算法演进
以数组中间索引的元素为中轴值,分组左右两边两个数组。
左边数组遍历找到一个大于中轴值的数,右边数组遍历找到一个小于中轴值的数,进行交换,遍历完成,左边数组都是小于中轴值的数,右边数组都是大于中轴值的数,但左右两边的数组内部还不是有序的。
左右两组分别以取中轴值方式进行递归,完成排序。
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)
}
}
阅读 36 · 发布于 2021-02-09
————        END        ————
扫描下方二维码关注公众号和小程序↓↓↓

昵称:
随便看看
换一批
-
PostgreSQL 查看时区阅读 161
-
Android WebView设置参考阅读 1567
-
走进Rust:Crate、模板阅读 321
-
Spring Boot使用Jackson注解阅读 81
-
MongoDB批量更新和删除字段阅读 346
-
Gradle分析依赖关系阅读 1174
-
Golang flag使用阅读 170
-
Element UI DatePicker时间跨度限制在同一个月内阅读 272
-
Spring Boot RabbitMQ Execution of Rabbit message listener failed阅读 289
-
Spring Boot解决CORS跨域问题阅读 1282