使用golang实现的快速排序 -买球官网平台

0顶
0踩

使用golang实现的快速排序

2014-09-10 14:04 by 见习编辑 u012797015 评论(1) 有8303人浏览

一、舞动的快速排序 

 

在实现排序算法前,先让我们来欣赏一段关于快速排序的视频,本段视频展示了快速排序的原理,如果没有看懂,请看完本文后再回头来看一下,应该就明白了吧。 o(∩_∩)o~ 


二、快速排序实现 

 

2.1 快速排序基础版 

 

通过下面一组数据,将最左边的数设定为轴,并记录其值为 s。 

(注意:*表示要交换的数,[]表示轴)  

  • [41] 24 76* 11 45 64 21 69 19 36* 
  • [41] 24 36 11 45* 64 21 69 19* 76 
  • [41] 24 36 11 19 64* 21* 69 45 76 
  • [41] 24 36 11 19 21 64 69 45 76 
  • 21 24 36 11 19 [41] 64 69 45 76 

回圈处理:

  1. 令索引 i 从数列左方往右方找,直到找到大于 s 的数 
  2. 令索引 j 从数列右方往左方找,直到找到小于 s 的数 
  3. 如果 i >= j,则离开回圈 
  4. 如果 i < j,则交换索引i与j两处的值 
  5. 将左侧的轴与 j 进行交换 
  6. 对轴左边进行递回 
  7. 对轴右边进行递回 

透过以上演算法,则轴左边的值都会小于s,轴右边的值都会大于s,如此再对轴左右两边进行递回,就可以对完成排序的目的。在上面的例子中,41左边的值都比它小,而右边的值都比它大,如此左右再进行递回至排序完成。  

具体代码如下: 



 

2.2 快速排序升级版 

 

在快速排序法基础版中,每次将最左边的元素设为轴,而之前曾经说过,快速排序法的加速在于轴的选择,在这个例子中,只将轴设定为中间的元素,依这个元素作基准进行比较,这可以增加快速排序法的效率。 

在这个例子中,取中间的元素s作比较,同样的先得右找比s大的索引 i,然后找比s小的索引 j,只要两边的索引还没有交会,就交换 i 与 j 的元素值,这次不用再进行轴的交换了,因为在寻找交换的过程中,轴位置的元素也会参与交换的动作,例如: 

 

41 24 76 11 45 64 21 69 19 36  

首先left为0,right为9,(left right)/2 = 4(取整数的商),所以轴为索引4的位置,比较的元素是45,您往右找比45大的,往左找比45小的进行交换: 

  • 41 24 76* 11 [45] 64 21 69 19 *36 
  • 41 24 36 11 45* 64 21 69 19* 76 
  • 41 24 36 11 19 64* 21* 69 45 76 
  • [41 24 36 11 19 21] [64 69 45 76] 

完成以上之后,再初别对左边括号与右边括号的部份进行递回,如此就可以完成排序的目的。  

具体代码如下: 

 

 

2.3 快速排序最终版 

 

先说明这个快速排序法的概念,它以最右边的值s作比较的标准,将整个数列分为三个部份,一个是小于s的部份,一个是大于s的部份,一个是未处理的部份,如下所示 :  




在排序的过程中,i 与 j 都会不断的往右进行比较与交换,最后数列会变为以下的状态: 



 

然后将s的值置于中间,接下来就以相同的步骤会左右两边的数列进行排序的动作,如下所示:  


整个演算的过程,直接摘录书中的虚拟码来作说明:



   

一个实际例子的演算如下所示:


具体代码如下: 



 

  • 大小: 138.3 kb
  • 大小: 338.8 kb
  • 大小: 40.9 kb
  • 大小: 4.5 kb
  • 大小: 4.6 kb
  • 大小: 3.7 kb
  • 大小: 12 kb
  • 大小: 24.1 kb
  • 大小: 42.4 kb
来自:
0
0
评论 共 1 条 请登录后发表评论
1 楼 2014-09-13 14:25
什么叫“回圈处理”?
在天朝,叫“循环处理”好吗?

发表评论

您还没有登录,请您登录后再发表评论

相关推荐

  • 快速排序 该软件包提供了的实验性实现。 有关文档,请参见 。

  • 当本次排序完成后,关键字将会移至正确的位置,数组被分为两个更小的子数组,以子数组为初始数组,接着重复以上操作。 二、代码 package main import "fmt" func quicksort(data []int, low int, high int) { if ...

  • golang算法实现 golang 实现一个快排 提示:写完文章后,目录可以自动生成,如何生成可参考右边的帮助文档 概要golang算法实现思想实现 思想 大而化小, 分而治之 将列表看成, 左边, 中值, 右边, 三部分, 使用...

  • 快速排序 先确定一个关键字。这里的关键字可以是数组任意一个 这里我设关键字下标为key, 是排序数组第一个数。 //关键字下标 key:=left 代码如下 找到 在mid左边 且arr[left] > arr[mid] 的对应left 找到...

  • 快速排序算法 golang实现 文章目录快速排序算法 golang实现算法描述算法步骤代码 算法描述 算法描述:是对插入算法的一种优化,利用对问题的二分化,实现递归完成快速排序 ,在所有算法中二分化是最常用的方式,...

  • 代码即思想。有空在补全思想吧。。 package main import ( "fmt" ) func main() { arr := []int{4, 3, 1, 5, 6} fmt.printf("arr is %v", quicksort(arr)) } func quicksort(arr []int) []int { ... retu...

  • 快速排序是一种分治策略的排序算法,是由英国计算机科学家 tony hoare 发明的, 该算法被发布在 1961 年的 communications of the acm 国际计算机学会月刊。 注: acm = association for computing machinery,国际...

  • golang 实现归并排序 分治法 归并排序是分治法的一种应用,分治法的核心思想是“分而治之”,就是把一个问题分化成若干个子可以用相同的方法去解决的小问题,再把子问题一层一层继续分化成粒度更小的子问题,直到...

  • 一、冒泡排序 //冒泡 func bubblesort(arry []int)[]int{ if arry == nil{ return nil } for i:=0;i<len(arry)-1;i { for j:=0;j<len(arry)-i-1;j { if arry[j]>arry[j 1]{ arry[j],arry...

  • 归并排序 // 归并排序 // 主要是merge func mergesort(arr []int) { arrlen := len(arr) if arrlen <= 1 { return } mergesort(arr, 0, arrlen-1) } func mergesort(arr []int, start, end int) { if ...

  • 快速排序的原理就不介绍了。在网上看到一个有趣的视频,大家可以看看,非常详细且有趣。我们公司大量用了golang做的电销系统,本文借鉴某电销系统的网站 代码:https://play.golang.org/p/fw5gtzrpj0 package main...

  • 事实上,快速排序通常明显比其他ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性...

  • 文章目录golang实现经典排序算法【二】堆排序归并排序递归版本迭代版本快速排序递归版本迭代版本补充heap在标准包的使用sort包中的快速排序实现 堆排序 首先构建大顶堆,然后交换堆顶, func main() { s := []int{1...

  • 关于快速排序的讲解在本人博文快速排序详解中,这里只展示golang的代码实现: package main import "fmt" func quicksort(arr []int, start, end int) { if start < end { i, j := start, end key := arr...

  • 1.冒泡排序 //冒泡排序本质就是做双重循环把每一个数与前面的数做对比并且换位 func bubblesort(arr []int) []int{ if len(arr) == 1{ return arr } for i:=0;i<len(arr);i { for j:=0;j<len...

  • 冒泡排序(bubble sort),是一种计算机科学领域的较简单的排序算法。 快速排序又称为划分交换排序

global site tag (gtag.js) - google analytics