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

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

前面的两篇文章分别讲述了基础的排序算法,以及应用更加广泛的 O(nlogn) 的排序算法,今天再来看看几种特殊的线性排序算法,之所以叫线性,是因为他们的主要思想都不是基于数据比较,而且时间复杂度接近 O(n)。

桶排序

桶排序的原理理解起来很简单,首先根据要排序的数据的最大和最小值,划分若干个区间,假设排序数据中的最小值是 1 ,最大值是 25,那么可以划分为 5 个区间,每个区间分别是 0-5,5-10,10-15,15-20,20-25

每个数据区间,一般叫做“桶”,然后可以将数据划分到各个桶内,如下:

划分完成之后,在桶内部分别进行排序(可以选择复杂度为 O(nlogn) 的排序算法),然后再依次将数据从桶内取出,这样整个数据就是有序的了。

桶排序看似简单,但应用场景并不是很多,因为它对于数据的要求比较苛刻,必须能够将数据尽量均匀的分到各个桶中,如果分布不均,那么时间复杂度会受到影响,在极端情况下,如果数据只分到了一个桶内,那么就退化成 O(nlogn) 的复杂度了。

桶排序的一个简单代码示例如下:

// 桶数量,可调整
const bucketNum = 10

// 桶排序
func BucketSort(data []int) {
   if len(data) == 0 {
      return
   }

   // 寻找到最大值和最小值
   min, max := math.MaxInt32, math.MinInt32
   for _, v := range data {
      if v < min {
         min = v
      }
      if v > max {
         max = v
      }
   }
   // 这里可能有整数溢出,根据实际情况再进行调整
   if min < 0 {
      for i := range data {
         data[i] += -min
      }
      max += -min
   }
   if max == 0 {
      return
   }

   // 新建桶并进行划分
   threshold := max / bucketNum
   if max%bucketNum != 0 {
      threshold += 1
   }
   var buckets [bucketNum + 1][]int
   for _, v := range data {
      buckets[v/threshold] = append(buckets[v/threshold], v)
   }

   // 桶内排序并拷贝回原数组
   var k int
   for i := 0; i < bucketNum + 1; i++ {
      sort.Ints(buckets[i])
      for _, v := range buckets[i] {
         if min < 0 {
            v += min
         }
         data[k] = v
         k++
      }
   }
}

计数排序

计数排序可以理解为桶排序的一种特殊情况,例如针对数据最大值并不是很大的情况,假如数据 4 2 2 8 3 3 1 最大值是 8,那么可以直接划分 8 个桶,将数据直接划分到对应的桶内,每个桶内的数据都是一样的,因此桶内数据并不需要排序。

可以参考下图来理解计数排序:

我再以一个简单的例子来讲解下计数排序的代码实现,假如有数据 4 2 2 8 3 3 1 最大值 max 为 8。

新建一个计数数组 count,count 大小为 max + 1,count 存储的是原数组每个值出现的次数,如下:

然后将 count 数组的值进行逐项累加,得到下面的结果:

最后进行最关键的一步,新建一个临时数组 output,遍历原数组,取出值做为 count 数组的下标,然后取出对应的 count 数组的值,将其减 1 做为临时数组的下标,原数组的值就存储在这个位置。

可以通过下面的图进行理解:

理解了这个之后,代码就会比较简单了:

// 计数排序
func CountingSort(data []int) {
   if len(data) <= 1 {
      return
   }

   // 寻找最大值
   max := data[0]
   for _, v := range data {
      if max < v {
         max = v
      }
   }

   // 记录数值出现次数
   count := make([]int, max+1)
   for _, v := range data {
      count[v]++
   }

   // count数组累加
   for i := 1; i < len(count); i++ {
      count[i] += count[i-1]
   }

   temp := make([]int, len(data))
   for _, v := range data {
      temp[count[v]-1] = v
      count[v]--
   }

   copy(data[:], temp[:])
}

基数排序

基数排序比较适用于数值较大或者字符串排序的场景,比如要针对一批手机号进行排序,手机号有 11 位,数值较大,不太适合使用桶排序或者计数排序。

而基数排序就比较适用于这种场景。

手机号码太长,举个简单的例子,假设有数据 121, 432, 564, 23, 1, 45, 788 进行排序,首先取这些数字的个位分别进行排序比较,然后取十位进行比较,因为这些数字最大的就到百位,所以比较到百位就结束了。如下图:

一个简单的代码演示如下:

// 基数排序(只适用于整数)
func RadixSort(data []int) {
   if len(data) <= 1 {
      return
   }

   // 找到数组中最大值
   max := data[0]
   for _, v := range data {
      if max < v {
         max = v
      }
   }

   buckets := make([][]int, 10)
   mod := 1
   for ; max > 0; max /= 10 {
      for _, v := range data {
         buckets[(v/mod)%10] = append(buckets[(v/mod)%10], v)
      }

      count := 0
      for i, buc := range buckets {
         for _, v := range buc {
            data[count] = v
            count++
         }
         buckets[i] = []int{}
      }
      mod *= 10
   }
}

完整代码示例在我的 Github 上可进行查看:https://github.com/roseduan/Go-Algorithm,排序专题到这篇文章就结束了,期待下一篇!

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

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

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

    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语言】排序算法之选择排序

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

    Regan Yue
  • 【C语言】排序算法之冒泡排序

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

    Regan Yue
  • Go之排序算法sort

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

    灰子学技术
  • 线性排序算法-堆排序 (2)

    在学数据结构的时候,链表、堆栈、树三种数据结构印象最深刻。当时理解有误区,堆栈被当成一种结构,可能因为堆栈有同样的特性——只关心堆顶或栈顶的元素。

    birdskyws
  • 线性排序算法(1)

    由于在遍历过程中,当出现前一个元素小于当前元素,提前结束比对,比选择排序算法的比对次数少。

    birdskyws
  • 算法之排序(中)-c语言实现

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

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

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

    信安本原
  • Go语言实现选择法排序

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

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

    李海彬
  • 线性排序算法-归并排序(3)

    举例说明,16个整形数组向下拆分 16-->(8,8)-->(4,4)-->(2,2)(2,2)(2,2)(2,2)->(1,1)(1,1)(1,1)(1,1...

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

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

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

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

    owent
  • 世界上最难学的编程语言,C语言只排第三,第一你绝对想不到!

    本次参与最难学编程语言排名的选手我从以上榜单中筛选了10位大家比较熟知的,他们分别是:Java、C、Python、C++、.NET、JavaScript、PHP...

    小林C语言

扫码关注云+社区

领取腾讯云代金券