1.4 快速排序

未匹配的标注

努力学习算法 Let's go

步骤:

  1. 从数列中挑出一个元素,称为 “基准”(pivot);

  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

动图演示:

quicksort

代码

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]

参考LeetCode《代码随想录》及网上资料,code已测试,有问题可评论。保持好的状态,坚持学习,滴水穿石!

本文章首发在 LearnKu.com 网站上。

上一篇 下一篇
zhaocrazy
讨论数量: 0
发起讨论 只看当前版本


暂无话题~