专栏首页陌无崖知识分享【go】剑指offer:常见排序算法

【go】剑指offer:常见排序算法

作者 | 陌无崖

转载请联系授权

冒泡排序

冒泡排序是比较简单的排序算法,它的关键思想是移动指针不断的进行两两比较,将最大的数字不断的进行更换位置,直至到最后,即完成一趟比较,都会寻找到最大的数字,且最大的数字会跑到末尾。

理解了上面的基本思想接着我们来想一想我们的代码思路,首先我们需要进行刚开始两个位置的比较,然后且需要比较到原始数据的最后一个位置。然后我们需要仍然从初始位置进行两两比较,然后应该比较到原始数据的倒数第2个位置。

现在我们模拟一下代码思路

//定义i来控制我们的比较一趟(冒出最大)的次数
//数据长度为len(data),需要比较len(data)-1次
i < len(data)-1
//定义一个j代表我们的比较位置
//比较结束位置用len(data)-1-i

代码如下

func bubbleSort(data []int) {
  // 外循环控制次数
  for i := 0; i < len(data)-1; i++ {
    //内循环进行比较
    for j := 0; j < len(data)-1-i; j++ {
      // fmt.Println(data[j], "与", data[j+1], "作比较")
      if data[j] > data[j+1] {
        data[j], data[j+1] = data[j+1], data[j]
      }
    }
  }
  fmt.Println(data)
}

时间复杂度:

外循环为n次,内循环总共为(1+2+3+4+..n)次,由此可知时间复杂度为O(n^2)

选择排序

对于选择排序,比较符合思考的逻辑,它的思想为每次从原始序列中找到最小放到初始位置,然后从剩余的未排序的中序列中找到最小的数字,排列到已排序的末尾。

这个思想相对简单,我们直接来看代码思路

//首先我们需要从初始位置开始寻找最小的数字,
// 然后移动初始位置,因此定义i来表示第一次比较的位置
for i :=0 ;i < len(data);i++{}
//在循环中我们需要将data[i]不断的与其之后的数字进行比较,
// 因此定义j来表示后面的数组的位置
for j := i + 1; j < len(data); j++{}
//开始比较data[i] 与 data[j]

代码如下:

func Select_Sort(data []int) {
  for i := 0; i < len(data); i++ {
    for j := i + 1; j < len(data); j++ {
      if data[i] > data[j] {
        data[i], data[j] = data[j], data[i]
      }
    }
  }
  fmt.Println(data)
}

时间复杂度:

由于外循环n次内循环总共为(1+2+3+4+ ...n),因此时间复杂度仍然为O(n^2)

插入排序

插入排序是一个不断插入数字来保证顺序不变的算法,即将一个数字插入到一个已经排好的序列。这一点可以类比扑克牌抓牌,每次抓牌都是从桌面上的牌抓起插入到自己手中的牌中,自己的手中的牌一直都将是有序的序列.

那么我们如何来保证我们的有序呢?我们不防也默认不知序列中的数字的排序情况,我们拿出一个数字,然后将下一数字拿出插入到第一个数字的之前或之后,保证有序,然后我们拿第三个数字,通过第三个数字和第二数字、第一个数字比较,一旦发现该数字比比较的数字小,以此来确定位置。然后将较大的数字整体往后移动。因此我们在移动数字之前我们的原始序列应该扩充一个位置。

看一下代码思路

//因为第一个数字就是有序,因此我们拿数字可以从第二个位置,令 i = 1
for i := 1; i < len(data); i++ {}
//我们需要将拿起的数字从后往前的进行比较,因此,我们令j = i
for j := i; j > 0; j-- {}
//前面的思想说我们需要一个扩展我们的数组,
// 为了更加简单,我们可以在原始数组上进行修改,只需要比较的时候,
// 不断更替位置,一直到比较结束的终止条件
if data[j] > data[j-1] {
    data[j], data[j-1] = data[j-1], data[j]
}

代码如下

// 直接插入排序简单写法
func Insert_Sort(data []int) {
  // 外循环控制待插入的数字
  for i := 1; i < len(data); i++ {
    for j := i; j > 0; j-- {
      if data[j] > data[j-1] {
        data[j], data[j-1] = data[j-1], data[j]
      }
    }
  }
}

那么我们如何使用扩展数组的方式进行插入排序呢?也很简单,首先我们需要不断的从我们的原始序列中取出数字,然后通过一个插入排序的函数即可,在插入排序中,我么的原始数组是有序的,我们需要对数组的长度增1,我们可以将待插入的数字先暂时放到尾,然后开始比较寻找位置。代码如下

func direct_insert(data []int, key int) {
  // 获取已经排好序列的数组的长度
  length := len(data)
  data = append(data, key)
  // 定义尾指针
  tail := length - 1
  // 定义result的末尾
  right := length

  for tail >= 0 && data[tail] > key {

    data[tail], data[right] = data[right], data[tail]
    tail--
    right--

  }
}

传入原始数组的待插入的方式如下:

for i := 0; i < len(data); i++ {
      Birary_Serect_Sort(data[:i], data[i])
}

时间复杂度

对于坏的比较次数就是原始数组是逆序的,对于第n个数,我们需要比较n-1次,因此时间复杂度仍然为O(n^2),但是不固定,适用于较少的数据,性能稳定。

快速排序

快速排序从名称上就很明显这是一个快速的排序方法,它采用了折半的思想,在一个序列中,随机选出其中的一个数字,将这个数字和整个序列进行比较,将比这个数字大的放右边,比数字小的放左边,因此原始的序列分成了两个序列,然后再在各自的序列按照同样的方法,分成两个序列。以此递归。

接着我们来看代码思路

1、从数列中挑出一个元素,称为 "基准"(pivot);

2、重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

3、递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

代码如下:

func Quick_Sort(data []int,left,right int){
  // 定义基准数的位置
  p := left
  i,j :=left,right
  for i<=j{
    if data[p] <=data[j] && p <=j{
      j--
    }
    if p <= j{
      data[p],data[j] = data[j],data[p]
      p = j
    }
    if data[p]>=data[i] && j <=p{
      i++
    }
    if p >=i{
      data[p],data[i] = data[i],data[p]
      p = i
    }
  }
  if (p-left)>1{
    Quick_Sort(data,left,p-1)
  }
  if (right-p)>1{
    Quick_Sort(data,p+1,right)
  }
}

本文分享自微信公众号 - golang技术杂文(gh_ebbdb61f463e),作者:无崖子天下无敌

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

原始发表时间:2019-12-27

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • go实现利用最大堆寻找最小k个数

    昨天分享了寻找最小k个数的算法是,那么有没有更为迅速的方法呢?今天就来分享关于如何使用最大堆进行解决。

    陌无崖
  • 寻找和为定值的两个数

    输入一个整数数组和一个整数,在数组中查找一对数,满足他们的和正好是输入的那个整数,如果有多对数的和等于输入的整数,则全部输出,要求输出的结果中不应该出现重复,如...

    陌无崖
  • 【go】剑指offer:不同程序员遇到相同的题

    该题可以说是初级程序员的水平,然而却有很多程序员的解决思路并不是完美。现在一起看看不同程序员的解决思路吧~

    陌无崖
  • 使用脚手架应用做单元测试

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    Jerry Wang
  • [半zz]迅雷笔试题

    用户1130771
  • go实现利用最大堆寻找最小k个数

    昨天分享了寻找最小k个数的算法是,那么有没有更为迅速的方法呢?今天就来分享关于如何使用最大堆进行解决。

    陌无崖
  • 通过空气质量指数AQI学习统计分析并进行预测(上)

    AQI(空气质量指数),用来衡量空气清洁或者污染的程度。值越小,表示空气质量越好。近年来,因为环境问题,空气质量也越来越受到人们的重视。

    朱小五
  • 使用 Python 实现几种常见的排序算法

    冒泡排序是最为基础的排序算法,其核心思想就是相邻元素两两比较,把较大的元素放到后面,在一轮比较完成之后,最大的元素就位于最后一个位置了,就好像是气泡,慢慢的浮出...

    周萝卜
  • 讲讲切比雪夫定理

    前面讲了大数定理,讲了中心极限定理,有读者留言让讲讲切比雪夫定理,安排。这一篇就来讲讲切比雪夫定理。

    张俊红
  • C++ string实现

    作为C++从业者,我相信都会被考察过实现简单的string类,包括构造、析构、拷贝构造以及赋值拷贝等,因为这能够很好的考察面试者的C++基本功。借看《剑指off...

    evenleo

扫码关注云+社区

领取腾讯云代金券