[golang] 数据结构-快速排序

NicoChen · · 378 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

快速排序是个非常经典、高效、常用的排序算法。很多语言标准库里的排序算法都有用到它。

原理
快排原理其实比较简单,就是将原本很大的数组拆成小数组去解决问题。
要拆就得找个拆的位置。如果吧这个位置称为支点,那么快速排序问题就变成了不断的去找到拆分的支点元素位置。
通常找支点就是以某个元素为标准,分别从最右侧元素向左找到比指定元素小的位置,再从最左侧开始向右找比指定元素大的位置。如果两个位置不相同就交换两个位置,在继续分表从两头相向寻找。找到合适的位置就是我们需要的支点。支点两边的元素再各自重复上面的操作,直到分拆出来的子数组只剩一个元素。分拆结束,顺序也就拍好了。
那么问题来了,以哪个元素为标准去比较呢?比如可以选第一个元素。

复杂度
理想情况下找到的支点可以把数组拆分成左右长度相近的子数组,此时时间复杂度为O(n*logn)
而最差情况则是每次找到的支点元素都在某一次,导致另一侧完全浪费,寻找支点的过程也浪费。这个时候用时会达到O(n^2)。
由于会打乱相同元素原有的顺序,所以快排也是一个不稳定排序。所以常用在普通类型数据的排序中。

代码实现

package main

import (
    "time"
    "fmt"
    "math/rand"
)

func main() {
    var length = 10
    var list []int

    // 以时间戳为种子生成随机数,保证每次运行数据不重复
    r := rand.New(rand.NewSource(time.Now().UnixNano()))
    for i := 0; i < length; i++ {
        list = append(list, int(r.Intn(50)))
    }
    fmt.Println(list)

    quickSort(list, 0, length-1)

    fmt.Println(list)
}

func quickSort(list []int, start, end int) {
    // 只剩一个元素时就返回了
    if start >= end {
        return
    }

    // 标记最左侧元素作为参考
    tmp := list[start]
    // 两个游标分别从两端相向移动,寻找合适的"支点"
    left := start
    right := end
    for left != right {
        // 右边的游标向左移动,直到找到比参考的元素值小的
        for list[right] >= tmp && left < right {
            right--
        }
        // 左侧游标向右移动,直到找到比参考元素值大的
        for list[left] <= tmp && left < right {
            left++
        }

        // 如果找到的两个游标位置不统一,就游标位置元素的值,并继续下一轮寻找
        // 此时交换的左右位置的值,右侧一定不大于左侧。可能相等但也会交换位置,所以才叫不稳定的排序算法
        if left < right {
            list[left], list[right] = list[right], list[left]
            fmt.Println(list)
        }
    }

    // 这时的left位置已经是我们要找的支点了,交换位置
    list[start], list[left] = list[left], tmp

    // 按支点位置吧原数列分成两段,再各自逐步缩小范围排序
    quickSort(list, start, left-1)
    quickSort(list, left+1, end)
}

运行结果
[golang] 数据结构-快速排序

杂谈
遇到最差情况时,上面算法的性能就比较糟糕了,和普通的插入排序差不多。所以为了避免选了个糟糕的支点,可以选择数组中间元素作为对比的标准,或是选3个元素,取中间大小的元素作为参考项。这时可以在一定程度上优化性能。不过最快情况的场景是在太少见,基本可以忽略掉。
还有个可优化的点,就是在数据量很少时,快排并不能体现速度优势,反而在二十几个元素以内的排序中比插入排序还慢。所以可以在递归循环里加个判断,如果一侧的元素数量小于某个值(比如20)时直接使用插入排序。


欢迎关注我们的微信公众号,每天学习Go知识

本文来自:51CTO博客

感谢作者:NicoChen

查看原文:[golang] 数据结构-快速排序

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:muxilin131420 备注:入群;或加QQ群:815126783

378 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传