超级苦工
阅读 69
经典排序算法总结与Go实现

学习Go语言第二周,本周任务尝试实现七大经典排序算法以及分析算法复杂度、优劣及应用场景等,七大经典算法分别为冒泡排序,插入排序,选择排序,希尔排序,归并排序,快速排序,堆排序。

冒泡排序

  • 思路

正如“冒泡”二字,我的理解是重复依次比较相邻的两个数,大的数放在后面,小的数放在前面,一直重复到没有任何一对数字需要交换位置为止。就像冒泡一样,大的数不断浮上来。

  • 伪代码
do
  swapped = false
  for i = 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap(leftElement, rightElement)
      swapped = true; swapCounter++
while swapped
  • Go实现
func Bubble_Sort(arr []int) {
    swapped := true
    len := len(arr)
    for swapped {
        swapped = false
        for i := 0; i < len-1; i++ {
            if arr[i] > arr[i+1] {
                arr[i], arr[i+1] = arr[i+1], arr[i] 
                swapped = true
            }
        }
    }
}

选择排序

  • 思路

先假设第一个元素为最小值,然后与剩余的 len-1 个元素依次进行比较,标记最小数的位置,如果有更小的数,则在进行下一轮遍历比较之前交换位置。

  • 伪代码
repeat (numOfElements - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position
  • Go实现
func Selection_Sort(arr []int) {
    len := len(arr)
    for i := 0; i < len-1; i++ {
        min := i
        for j := i+1; j < len; j++ {
            if arr[j] < arr[min] {
                min = j
            }
        }
        arr[min], arr[i] = arr[i], arr[min]
    }
}

插入排序

  • 思路
    这个排序感觉和选择排序的思路有点相似的。首先1个长度的数组肯定是有序的,假设数组的长度为n,第一位是有序的,然后从第二位开始在已排序序列中从后向前扫描,找到相应位置并插入。

  • 伪代码

mark first element as sorted
for each unsorted element X
  'extract' the element X
  for j = lastSortedIndex down to 0
    if current element j > X
      move sorted element to the right by 1
    break loop and insert X here
  • Go实现
func Insertion_Sort(arr []int) {
    len := len(arr)
    for i := 0; i < len; i++ {
        selected := arr[i]
        for j := i-1; j >= 0; j-- {
            if arr[j] > selected {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            } else {
                arr[j+1] = selected
                break
            }
        }
    }
}

归并排序

  • 思路

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组,再合并数组。先考虑合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。再考虑递归分解,基本思路是将数组分解成left和right,如果这两个数组内部数据是有序的,那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的?可以再二分,直至分解出的小组只含有一个元素时为止,此时认为该小组内部已有序。然后合并排序相邻二个小组即可。(摘抄)

  • 伪代码
split each element into partitions of size 1
recursively merge adjancent partitions
  for i = leftPartStartIndex to rightPartLastIndex inclusive
    if leftPartHeadValue <= rightPartHeadValue
      copy leftPartHeadValue
    else: copy rightPartHeadValue; Increase InvIdx
copy elements back to original array
  • Go实现
func Merge_Sort(arr []int) []int{
    if len(arr) <= 1 {
        return arr
    }
    var middle int = len(arr)/2
    left := Merge_Sort(arr[:middle])
    right := Merge_Sort(arr[middle:])
    return merge(left, right)
}

func merge(a, b []int) []int {
    alen, blen := len(a), len(b)
    var z []int = make([]int, alen + blen)
    k := 0//数组切片z的下标 
    i, j := 0, 0//a、b起始下标均未0
    for i < alen && j < blen  {
        if a[i] < b[j] {
            z[k] = a[i] 
            i++ 
        } else { 
            z[k] = b[j] 
            j++ 
        } 
        k++ 
    }
    for i != alen {
        z[k] = a[i] 
        k++ 
        i++ 
    } 
    for j != blen { 
        z[k] = b[j] 
        k++ 
        j++ 
    } 
    return z 
}

快速排序

  • 思路

快速排序可能是当前应用最广泛的排序算法。快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。快速排序引人注目的特点包括它是原地排序(只需要一个很小的辅助栈)。
该方法的基本思想是:1.先从数列中取出一个数作为基准数。2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。3.再对左右区间重复第二步,直到各区间只有一个数。

  • 伪代码
for each (unsorted) partition
set first element as pivot
  storeIndex = pivotIndex + 1
  for i = pivotIndex + 1 to rightmostIndex
    if element[i] < element[pivot]
      swap(i, storeIndex); storeIndex++
  swap(pivot, storeIndex - 1)
  • Go实现
func Quick_Sort(arr []int) {
    sort(arr, 0, len(arr)-1)
}
func sort(arr []int, left int, right int) {
    if right <= left {
        return
    }
    p := partition(arr, left, right)//快速排序切分
    sort(arr, left, p-1)
    sort(arr, p+1, right)
}
func partition(arr []int, left int, right int) int {
    pivot := arr[left]
    i, j := left, right+1
    for true {
        for i++; arr[i] < pivot; i++ {
            if i==right {
                break
            }
        }
        for j--; pivot < arr[j]; j-- {
            if j==left {
                break
            }
        }
        if i>=j {
            break
        }
        arr[i], arr[j] = arr[j], arr[i]
    }
    arr[left], arr[j] = arr[j], arr[left] 
    return j
}

希尔排序

  • 思路

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。希尔排序是基于插入排序的以下两点性质而提出改进方法的:1. 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率2. 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

  • Go实现
func Shell_Sort(arr []int) {
    N := len(arr)
    var gap int = N/2    //初始步长
    for gap > 0 {
        for i := gap; i < N; i++ {    //每一列进行插入排序 , 从gap 到 n-1
            temp := arr[i]
            j := i
            for j>=gap && arr[j-gap]>temp {    //插入排序
                arr[j] = arr[j-gap]
                j = j-gap
            }
            arr[j] = temp
        }
        gap = gap/2    //重新设置步长
    }
}

堆排序

堆排序是一种选择排序,其时间复杂度为O(nlogn)

  • 堆的定义

n个元素的序列{k1,k2,…,kn}当且仅当满足下列关系之一时,称之为堆。  情形1:ki <= k2i 且ki <= k2i+1 (最小化堆或小顶堆)  情形2:ki >= k2i 且ki >= k2i+1 (最大化堆或大顶堆)  其中i=1,2,…,n/2向下取整;
若将和此序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。
例如,下列两个序列为堆,对应的完全二叉树如图:


完全二叉树.png

若在输出堆顶的最小值之后,使得剩余n-1个元素的序列重又建成一个堆,则得到n个元素的次小值。如此反复执行,便能得到一个有序序列,这个过程称之为堆排序。堆排序(Heap Sort)只需要一个记录元素大小的辅助空间(供交换用),每个待排序的记录仅占有一个存储空间。

  • 堆的存储

一般用数组来表示堆,若根结点存在序号0处, i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2i+1和2i+2。(注:如果根结点是从1开始,则左右孩子结点分别是2i和2i+1。)如第0个结点左右子结点下标分别为1和2。如最大化堆如下:左图为其存储结构,右图为其逻辑结构。


最大化堆.png
  • 堆的排序实现

  • 构造最大堆(Build_Max_Heap):若数组下标范围为0~n,考虑到单独一个元素是大根堆,则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始,向前依次构造大根堆,这样就能保证,构造到某个节点时,它的左右子树都已经是大根堆。2. 堆排序(HeapSort):由于堆是用数组模拟的。得到一个大根堆后,数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点,并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换,再对heap[0...n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换,再对heap[0...n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间,故操作完后整个数组就是有序的了。3. 最大堆调整(Max_Heapify):该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整,使得子节点永远小于父节点 。

  • Go实现

func Heap_Sort(arr []int) {
    N := len(arr)
    var first int = N/2    //最后一个非叶子节点
    for start := first; start > -1; start-- {    //构造大根堆
        max_heapify(arr, start, N-1)
    }
    for end := N-1; end > 0; end-- {    //堆排,将大根堆转换成有序数组
        arr[end],arr[0] = arr[0],arr[end]
        max_heapify(arr, 0, end-1)
    }
}
func max_heapify(arr []int, start int, end int) {
    root := start
    for true {
        child := root*2 + 1    //调整节点的子节点
        if child > end {
            break
        }
        if child + 1 <= end && arr[child] < arr[child+1] {
            child = child + 1    //取较大的子节点
        }
        if arr[root] < arr[child] {
            arr[root], arr[child] = arr[child], arr[root]    //较大的子节点成为父节点
            root = child
        } else {
            break
        }
    }
}

七种经典排序算法指标对比


指标.png

参考资料

可视化排序动态图](https://visualgo.net/en/sorting))
经典排序算法总结与实现 (Python实现)
堆排序 Heap Sort
算法(中文版•第4版)

评论
相关推荐
asdfasfdfd

asdfasdfsafd...

asdfafsdfsad

function sdf(){ echo &quot;sdffsdfds&quot;; }...

阿萨德飞

sdflkllsfdkj nihao...

【Golang+mysql】记一次mysql数据库迁移(一)

【Golang+mysql】记一次mysql数据库迁移(一) 文章地址:https://github.com/stayfoo/stayfoo-hub 一、准备 目标: 腾讯云 CVM 自建 mysql...

米粒社区系统什么部署?

发现现在一些功能还没开发或上线,不过感觉这个社区系统很强大,期待期待...

不错的网站

ceshi ceshi...

[译]想成为一个出色的Web工程师?学Golang而非Node.js。

原文: https://medium.com/codezillas/want-to-be-a-best-web-developer-learn-golang-not-node-js-69b4166d1...

跟我一起学习gRPC

扫描二维码,点击源码阅读菜单,跟我一起学习gRPC...

这个项目还会更新吗

这个项目github上1年多没有更新了...

golang123报错问题

报图上错误,怎么解...

【开源】gnet: 一个轻量级且高性能的 Golang 网络库

Github 主页 https://github.com/panjf2000/gnet 简介 gnet 是一个基于 Event-Loop 事件驱动的高性能和轻量级网络库。这个库直接使用 epoll 和...

t2

tttttttttttttttttttttttt...

test

123456789...

读 "优雅关闭的 Go Web 服务器"

读 &quot;优雅关闭的 Go Web 服务器&quot; GitHub 仓库:https://github.com/stayfoo/stayfoo-hub 文章《优雅的关闭 Go Web 服务器》...

golang123监控安装配置

有问题同学将golang123的源码中的statsD安装配置成功的,分享一下配置过程呗。...

Golang Modules官方包管理

1 设置环境变量 GO111MODULE=auto2 初始化项目 go mod init my_project3 针对国外无法访问的包设置代理 GOPROXY=https://goproxy.io其他...

猎豹移动,直播业务,招聘 Golang 工程师【北京】

我的微信是 legenove, 邮箱是 liuguoyang@cmcm.com 我是这个团队的 leader,直接给自己团队招聘。 职位要求: 1.熟练掌握 Golang 语言,并有 2 年以上中大型...

部署后登录 Request failed with status code 404

Request failed with status code 404 怎么解决...

[深圳 梦享网路 ] Golang开发工程师招聘

岗位介绍 ** 如有意向:请联系: 陈小姐:TEL:18620870779 邮箱:chenpeiwen@clickwifi.net ** 办公地点:深圳市南山区软件产业基地科园路中科纳能大厦A栋403...

golang + qt5 开发的百度网盘不限速客户端

百度网不限速客户端,使用golang + qt5 开发,跨平台。代码注释详细,并有附有开发文档,gopher们快来支持下吧 官网: https://github.com/peterq/pan-ligh...