1.4 快速排序
努力学习算法 Let's go
步骤:
从数列中挑出一个元素,称为 “基准”(pivot);
重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;
动图演示:
代码
package main
import (
"fmt"
)
func quickSort(arr []int) []int{
return _quickSort(arr, 0, len(arr)-1)
}
//递归排序
func _quickSort(arr []int, left, right int) []int {
if left < right {
partitionIndex := partition(arr, left, right)
//fmt.Println(arr)
//fmt.Println("partitionIndex", partitionIndex)
_quickSort(arr, left, partitionIndex-1)
_quickSort(arr, partitionIndex+1, right)
}
return arr
}
func partition(arr []int, left, right int) int {
pivot := left //0
index := pivot + 1//1
for i := index; i <= right; i++{ //循环13次
if arr[i] < arr[pivot] { //1 < 99
swap(arr, i, index)
index += 1
}
//fmt.Println(arr)
//fmt.Println(i)
//fmt.Println(index)
}
fmt.Println("pivot",pivot)
fmt.Println("index-1",index-1)
swap(arr, pivot, index-1) // (arr,0,12)
return index-1
}
//交换位置
func swap(arr []int, i, j int){
arr[i], arr[j] = arr[j], arr[i]
}
func main() {
arr := []int{99,1,5,7,9,23,4,78,88,66,54,10,12} //共13个数
quickSort := quickSort(arr)
fmt.Println("quickSort:",quickSort)
}
执行结果
此算法不是很好理解,多打印理解思考
pivot 0
index-1 12
pivot 0
index-1 6
pivot 0
index-1 5
pivot 0
index-1 1
pivot 2
index-1 2
pivot 3
index-1 3
pivot 7
index-1 10
pivot 7
index-1 7
pivot 8
index-1 9
quickSort: [1 4 5 7 9 10 12 23 54 66 78 88 99]
推荐文章: