专栏首页roseduan写字的地方Go 语言算法之美—进阶排序

Go 语言算法之美—进阶排序

上一篇文章讲述了几种基础的排序算法,可以回顾一下:Go 语言算法之美—基础排序,这几种算法平均情况下的时间复杂度都是 O(n2),在大规模数据下是非常低效的,所以它们的应用并不多。

这篇文章再来看看几种在实践当中更加常用、也更加复杂一点的排序算法,分别是希尔排序、堆排序、快速排序、归并排序。

1、希尔排序

希尔排序其实是对插入排序的一种优化,回想一下,插入排序的流程是:将数据分为了已排序区间和未排序区间,依次遍历未排序区间的值,将其插入到已排序区间合适的位置。

插入排序的一个最大的缺点是:每次只能移动一位,这样在一些极端的情况下会非常低效;例如数据 2 3 5 7 9 0,如果将 0 移动至元素头部,需要遍历整个数组。

希尔排序的优化点就在于此,它的核心思想是将数据中的元素分为了多个组,每一组分别进行插入排序。

举一个简单的例子:有数据 35 33 42 10 14 19 27 44,首先将数据以其长度的 1/2 (也就是 4)为步长,分为了四个组,分别是 {35,14}、{33,19}、{42,27}、{10,44}。

然后对每一组分别进行插入排序,排序后的结果如下:

然后步长缩小一半,变为 2 ,将数组分为了两个组,分别是 {14,27,35,42}、{19,10,33,44}:

然后再分别对这两个组进行插入排序,结果就是 14 10 27 19 35 33 42 44。

最后,步长再缩小一半,变为 1,将数组分为了一个组(其实就是数组本身),并再进行插入排序,这样希尔排序的流程便完成了。

可以看到,希尔排序将数组分为了多个组,其实是为了尽可能的将数据变得局部有序,代码如下:


func ShellSort(data []int) {
   length := len(data)
   step := length / 2
   for step >= 1 {
      for i := 0; i < length-step; i++ {
         j, k := i+step, data[i+step]
         for ; j > step-1 && data[j-step] > k; j -= step {
            data[j] = data[j-step]
         }
         data[j] = k
      }
      step /= 2
   }
}



希尔排序实际应用并不是很多,它的相关复杂度如下:

Time Complexity

Best

O(nlog n)

Worst

O(n2)

Average

O(nlog n)

Space Complexity

O(1)

Stability

no

2、堆排序

要理解堆排序,必须得先明白什么是二叉堆。二叉堆(以下简称堆)是一种很优雅的数据结构,它是一种特殊的二叉树,满足二叉树的两个特性便可以叫做堆:

  • 是一个完全二叉树
  • 堆中任意一个节点的值都必须大于等于(或者小于等于)其子树中的所有节点值

对于节点大于等于子树中节点值的堆,叫做大顶堆,反之则叫做小顶堆,以下是两个堆的例子:

从定义和上图中可以看到,堆的一个特点是,堆顶元素就是堆中最大(或最小)的元素。

堆其实可以使用数组来存储,堆顶元素就是数组的第一个元素,并且对于任意下标为 i 的节点,其左子节点是 2 * i + 1,右子节点是 2 * i + 2,有了这个对应关系,堆在数组中的存储就是这样的:

理解了什么是堆之后,接下来进入正题,看看如何基于堆实现排序。堆排序的步骤一般有两个,分别是构造堆和排序,下面依次介绍。

构造堆

构造堆指的是将无序的数组构造成堆(这里使用大顶堆进行讲解),使其符合堆的特征,举一个例子,对于一个完全无序的数组,其原始状态和存储结构如下图:

要使其变成大顶堆,我们可以这样做:从第一个非叶子节点开始,依次将其和子节点的值进行比较,如果小于子节点的值,交换节点顺序,然后再依次比较下去,直到叶子节点。

这样就能够始终满足堆的特性,任意节点的值总是大于其子树中所有节点的值。

排序

堆构建完成之后就是排序了,前面提到了堆有一个很重要的特性,那就是堆顶元素就是最大的元素,我们遍历数组的长度,每次都取堆顶的元素(下标为 0 的元素),将其和数组最后的元素交换位置,然后重新将剩下的数据组织成堆,继续取堆顶的最大元素,以此类推。

将两个步骤结合起来,就是堆排序的完整实现了,代码如下:

// 堆排序
func HeapSort(data []int) {
   // 构建堆
   length := len(data)
   for i := (length - 2) / 2; i >= 0; i-- {
      heapify(data, length, i)
   }

   // 排序
   for length > 0 {
      length--
      data[length], data[0] = data[0], data[length]
      heapify(data, length, 0)
   }
}

func heapify(data []int, size, i int) {
   for {
      max := i
      if 2*i+1 < size && data[2*i+1] > data[max] {
         max = 2*i + 1
      }
      if 2*i+2 < size && data[2*i+2] > data[max] {
         max = 2*i + 2
      }
      if i == max {
         break
      }
      data[i], data[max] = data[max], data[i]
      i = max
   }
}

相关复杂度如下:

Time Complexity

Best

O(nlog n)

Worst

O(nlog n)

Average

O(nlog n)

Space Complexity

O(1)

Stability

No

归并排序

归并排序基于分治思想。

分治,顾名思义就是分而治之,它是一种解决问题的思路,将原始问题分解为多个相同或相似的子问题,然后将子问题解决,并将子问题的求得的解进行合并,这样原问题就能够得到解决了。

分治思想是很多复杂算法的基础,例如归并排序、快速排序、二分查找等等。

言归正传,再来看归并排序,它的概念理解起来非常简单,如果我们要对一组数据进行排序,我们可以将这个数组分为两个子数组,子数组再进行分组,这样子数组排序之后,将结果合并起来,就能够得到原始数据排序的结果。

下面这张图展示了将一个问题分解为多个子问题的过程:

子问题得到解决之后,需要将结果合并,合并的过程如下图:

代码实现如下:

//归并排序
func MergeSort(data []int) {
   mergeSortHelper(data, 0, len(data)-1)
}

func mergeSortHelper(data []int, lo, hi int) {
   if lo < hi {
      mid := lo + (hi-lo)/2
      mergeSortHelper(data, lo, mid)
      mergeSortHelper(data, mid+1, hi)
      merge(data, lo, mid, hi)
   }
}

func merge(data []int, lo, mid, hi int) {
   temp := make([]int, hi-lo+1)
   i, j, k := lo, mid+1, 0
   for i <= mid && j <= hi {
      if data[i] < data[j] {
         temp[k] = data[i]
         i++
      } else {
         temp[k] = data[j]
         j++
      }
      k++
   }
   copy(temp[k:], data[i:mid+1])
   copy(temp[k:], data[j:hi+1])
   copy(data[lo:hi+1], temp[:])
}

相关复杂度如下:

Time Complexity

Best

O(n*log n)

Worst

O(n*log n)

Average

O(n*log n)

Space Complexity

O(n)

Stability

Yes

3、快速排序

快速排序通常叫做“快排”,它应该是应用最广泛的一个排序算法了,很多编程语言内置的排序方法,都或多或少使用到了快速排序,因为快速排序的时间复杂度可以达到 O(nlogn),并且是原地排序,前面介绍的几种排序算法都无法将这两个优点结合起来。

快排和归并排序类似,都采用了分治思想,但是它的解决思路却和归并排序不太一样。

如果要排序一个数组,我们可以从数组中选择一个数据,做为分区点(pivot),然后将小于分区点的放到分区点的左侧,大于分区点的放到其右侧,然后对于分区点左右两边的数据,继续采用这种分区的方式,直到数组完全有序。

概念读起来可能有点抽象,这里我画了一张图来帮助你理解整个排序的过程:

上图展示了第一次分区的过程,假设要排序的数组的下标是 p ~ r,我们取数组的最后一个元素 5 做为分区点,然后比 5 小的数字 0 3 1 2 移动到 5 的左边,比 5 大的数字 9 6 8 7 移动到 5 的右边。

然后以数字 5 为分界点,其左边的数字(下标为 p ~ q - 1),以及右边的数字(下标为 q + 1 ~ r),分别再进行同样的分区操作,一直分下去,直到数组完全有序,如下图:

下面的动图展示了快速排序的完整过程(注意动图中是选择第一个元素做为分区点的):

如果使用一个简单的公式来表示快速排序,可以写成这样:

int q = partition(data, p, r);
quick_sort(data, p, r) = quick_sort(data, p, q - 1) + quick_sort(data, q + 1, r);

这里有一个 partition 分区函数,它的作用是选择一个分区点,并且将小于分区点的数据放到其左边,大于分区点的放到其右边,然后返回分区点的下标。

其实这个 partition 分区函数是快速排序实现的关键,那究竟怎么实现这个函数呢?很容易想到的一种方式是:直接遍历一次原数组,依次取出小于和大于分区点的数据,将其各自存放到一个临时数组中,然后再依次拷贝回原数组中,过程如下图:

这样做虽然简单,但是存在一个缺陷,那就是每次分区都会使用额外的存储空间,这会导致快速排序的空间复杂度为 O(n),那么就不是原地排序了。

所以快速排序使用了另一种方式来实现分区,并且没有借助额外的存储空间,它是怎么实现的呢?我还是画了一张图来帮助你理解:

声明了两个指针 i 和 j,从数组的最开始处向后移动,这里的移动规则有两个:

  • 一是如果 j 所在元素大于分区点,那么 j 向后移动一位,i 不变;
  • 二是如果 j 所在元素小于分区点,那么交换 i 和 j 所在元素,然后 i 和 将 j 同时向后移动一位。

终止的条件是 j 移动至数组末尾,然后交换分区点和 i 所在的元素,i 就是分区点的下标。

理解了这个过程之后,再来看快速排序的代码实现,就会非常的简单了,下面是一个示例:

func QuickSort(data []int) {
  quickSortHelper(data, 0, len(data)-1)
}

func quickSortHelper(data []int, lo, hi int) {
  if lo < hi {
    mid := partition(data, lo, hi)
    quickSortHelper(data, lo, mid-1)
    quickSortHelper(data, mid+1, hi)
  }
}

func partition(data []int, lo, hi int) int {
  pivot, i, j := data[hi], lo, lo
  for j < hi {
    if data[j] < pivot {
      data[j], data[i] = data[i], data[j]
      i++
    }
    j++
  }
  data[i], data[hi] = data[hi], data[i]
  return i
}

快速排序相关复杂度如下:

Time Complexity

Best

O(n*log n)

Worst

O(n2)

Average

O(n*log n)

Space Complexity

O(log n)

Stability

No

文中的全部代码可在我的 Github 上查看:https://github.com/roseduan/Go-Algorithm

本文分享自微信公众号 - roseduan写字的地方(rose_duan),作者:roseduan

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-08-04

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Go 语言算法之美—基础排序

    排序是一个十分古老的问题,也是计算机领域很经典的算法问题之一,后续的几篇文章,我将对常见的排序算法进行讲述。

    roseduan
  • Go 语言算法之美—线性排序

    前面的两篇文章分别讲述了基础的排序算法,以及应用更加广泛的 O(nlogn) 的排序算法,今天再来看看几种特殊的线性排序算法,之所以叫线性,是因为他们的主要思想...

    roseduan
  • go语言十大排序算法总结

    选择排序 选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的...

    李海彬
  • Go语言归并排序算法实现

    算法导论的伪代码: MERGE 函数是合并两个已经排好序的序列。 下面的输入参数:A是一个数组,p,q和r是数组下标,满足 p<=q<=r。下面的函数假设子数组...

    李海彬
  • go语言十大排序算法总结

    选择排序 选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的...

    李海彬
  • Go语言归并排序算法实现

    算法导论的伪代码: MERGE 函数是合并两个已经排好序的序列。 下面的输入参数:A是一个数组,p,q和r是数组下标,满足 p<=q<=r。下面的函数假设子数组...

    李海彬
  • 【C语言】排序算法之冒泡排序

    冒泡排序(Bubble Sort):是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复...

    Regan Yue
  • 【C语言】排序算法之选择排序

    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩...

    Regan Yue
  • Go语言入门——进阶语法篇(三)

    Go语言虽然存在指针,但是远比C语言指针简单,且Go语言基本指针不能直接进行指针运算。

    arcticfox
  • Go语言入门——进阶语法篇(四)

    Go语言没有类似Java或Python那种try...catch...机制处理异常,Go的哲学是与众不同的,Go的设计者认为主流的异常处理机制是一种被过度滥用的...

    arcticfox
  • Go之排序算法sort

    Go的pkg提供了一个排序的包sort,用于对slices和用户自定义的类型进行排序操作。原文参考:

    灰子学技术
  • 平均薪资25k!这门编程语言才是未来方向

    近几年,关于 Go 与 Java 还有 c 的对比和讨论愈演愈烈,但不可否认的是,在十年多的时间里,Go 语言发展势头强劲,凭借其简洁、高效的特性,在竞争激烈的...

    芋道源码
  • 算法之排序(中)-c语言实现

    上一篇文章里说了归并排序和快速排序,它们的代码实现是非常相似的,只要理解了其中的具体实现,还是比较容易写出代码的。

    信安本原
  • 算法之排序(上)-c语言实现

    在上一篇文章中,我们说了时间复杂度为 O(n2)的几个排序算法,冒泡排序、插入排序、选择排序,在理解上和实现上都没有太难的地方,这里在实现的时候,没有再自己实现...

    信安本原
  • 【Python进阶】经典排序算法

    优化:某一趟遍历如果没有数据交换,则说明已经排好序了,因此不用再进行迭代了。用一个标记记录这个状态即可。设置标志位flag,如果发生了交换flag设置为true...

    文渊同学
  • Go语言实现选择法排序

    大师级码师
  • 【Go 语言社区】Go语言实现选择法排序实例

    package main import "fmt" func select_sort(a []int) { len := len(a) for i:=0; ...

    李海彬
  • 【从零开始学习Go语言】十.基础算法之冒泡排序

    举个例子说明一下,比如有一个数组:[3 2 1 0],需要将该数组进行升序排序,即排序成:[0 1 2 3]。

    一只特立独行的兔先生
  • C/C++语言常用排序算法

    资料由互联网收集整理,供新手参考学习 这里又生动点的演示:http://www.cnblogs.com/wangfupeng1988/archive/2011...

    owent

扫码关注云+社区

领取腾讯云代金券