Go语言如何提高快排的效率

快排利用分治的思想,这里数组/切片分为两个部分,左边比哨兵小,右边比哨兵大,然后递归执行快排函数,这里有个很重要的因素是如果递归调用的时候用协程执行,左半部分数组和右半部分的数组分别传入作参数,所以不用考虑数据的同步问题。效果就像是一个协程调2个,两个调4个,4个调8个。时间复杂度会明显降低。 使用线程快排和使用协程快排会有什么区别,由于系统限制,线程的创建是有限的,当数组长度一旦很大,速度回明显降低,但是协程不会,测试了一个100w的随机数数组,排序的时间也只是在10ms左右。测试如下:

package main
import "math/rand"
import "fmt"
import "time"
func quickSort(values []int,left,right int){
    temp:=values[left]
    p:=left
    i,j:=left,right
    for i<=j{
        for j>=p && values[j]>=temp{
            j--
        }
        if j>=p{
            values[p]=values[j]
            p=j
        }
        for i<=p && values[i]<=temp{
            i++
        }
        if i<=p{
            values[p]=values[i]
            p=i
        }
    }
    values[p]=temp
    if p-left>1{
        quickSort(values,left,p-1)
                //go quickSort(values,left,p-1)
    }
    if right-p>1{
        quickSort(values,p+1,right)
        //go quickSort(values,p+1,right)
    }
}
func QuickSort(values []int){
    quickSort(values,0,len(values)-1)
}
func main(){
        ceshi :=make([]int,10000)
        for i:=0 ; i<100; i++ {
                ceshi[i]=rand.Intn(100)
        }
        start_time :=time.Now()
        QuickSort(ceshi)
        end_time :=time.Since(start_time)
        fmt.Println("after sort",ceshi)
        fmt.Println("count time ",end_time)
}

原文发布于微信公众号 - Golang语言社区(Golangweb)

原文发表时间:2017-07-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

技术 | Python从零开始系列连载(十八)

但是有一种情况是递归时不断调用自身,达到不了最简单的情况(例如俄罗斯套娃一层层打开到最内层的),所以一直找不到递归的出口。

1193
来自专栏工科狗和生物喵

【计算机本科补全计划】C++牛客网试题习题解析

正文之前 一大早醒来,外面淅淅沥沥的雨绵绵的下着,床铺真的舒服,但是我也不能就在床上刷微博看小说吧,所以想起了昨晚下载的牛客网的APP,赶紧掏出我的大宝贝---...

3857
来自专栏C语言及其他语言

[每日一题]数据的插入与重排

炎炎夏日,热浪滚滚,动都不想动的时候不妨来一道C语言的题冷静冷静 题目描述 已有一个已排好的9个元素的数组,今输入一个数要求按原来排序的规律将它插入数组中。 ...

3665
来自专栏CodingToDie

Python学习(十):有趣的字符串

第10 章 Python 字符串 学的到东西的事情是锻炼,学不到的是磨练 Table of Contents 字符串更新 转义字符 原始字符串 运算 连接 重复...

4187
来自专栏JackieZheng

初探JavaScript(四)——作用域链和声明提前

前言:最近恰逢毕业季,千千万万的学生党开始步入社会,告别象牙塔似的学校生活。往往在人生的各个拐点的时候,情感丰富,感触颇深,各种对过去的美好的总结,对未来的展望...

2005
来自专栏写代码的海盗

分水岭 golang入坑系列

第三式开篇语有些负面, 所以这里就不贴了。有兴趣的自己可以去看看 https://andy-zhangtao.gitbooks.io/golang/conten...

3904
来自专栏小樱的经验随笔

【Java学习笔记之十三】初探Java面向对象的过程及代码实现

理解Java面向对象的重要知识点: 一、 类,对象 类?首先举一个例子:小李设计了一张汽车设计图,然后交给生产车间来生产汽车,有黑色的、红色的、白色的... ...

3396
来自专栏青玉伏案

代码重构(二):类重构规则

在上篇博客《代码重构(一):函数重构规则(Swift版)》中,详细的介绍了函数的重构规则,其中主要包括:Extract Method, Inline Metho...

22510
来自专栏玄魂工作室

Python黑帽编程2.1 Python编程哲学

本节的内容有些趣味性,涉及到很多人为什么会选择Python,为什么会喜欢这门语言。我带大家膜拜下Python作者的Python之禅,然后再来了解下Python的...

3147
来自专栏java一日一条

关于 Java 对象序列化您不知道的 5 件事

数年前,当和一个软件团队一起用 Java 语言编写一个应用程序时,我体会到比一般程序员多知道一点关于 Java 对象序列化的知识所带来的好处。

671

扫码关注云+社区

领取腾讯云代金券