专栏首页陌无崖知识分享Go寻找数组中最小的k个数——全部排序和部分排序

Go寻找数组中最小的k个数——全部排序和部分排序

作者 | 陌无崖

转载请联系授权

导语

今天分享的是数组中寻找k个最小数的解题思路,分别是全部排序和部分排序,一起来看看吧~

题目要求

有n个整数,请找出其中最小的k个数,要求时间复杂度尽可能的低。

解法一:利用全部排序

对于这种方法,我们只需要对我们的数组进行排序,然后取出前k个数就行了。那么对于全部排序,为了更加迅速我们使用快速排序的方法,因为快速排序的时间复杂度为O(nlogn),因此对于在n远大于k的情况下,此方法的时间复杂度为O(nlogn) + O(k) = O(nlogn),下面我们开始分析快速排序.

快速排序的思想

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序列。

听起来有点晦涩难懂,简单来说就是对于一个数组,我们随便找一个数字,将这个数字和其它数字进行比较,比它大的放右边,比它小的放左边。然后就分成了两个数组,通过同样的方法将其余的两个数组进行找数字,排序,每个数组又得到两个数组,一直循环通过以上的方式,最终一定会出现只包含两个数字的数组,因为已经排好序,并且小的一直放在右边,大的一直在左边,规并之后就是一个排好序的数组。

如果还不太明白,可以看下面的一张图篇:

排序流程

(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。

(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理

(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

代码分析

(1)首先需要定义一个基准数key

(2)为了保证比较的时候不超过或者不低于基准数的小标,需要定义指针p指向基准数,每次交换后,改变p

(3)为了遍历数组,我们也需要定义两个指针 i,j 指向首尾

完整排序代码

// 利用去全排序进行寻找最小的k个数
func FindNumBySort(data []int, k int) (result []int) {
  if len(data) != 0 {
    // 对数组进行快速排序
    QuickSelect(data, 0, len(data)-1)
    // 返回前k个数
    return data[0:k]
  }
  return result
}
func QuickSelect(data []int, left, right int) {
  // 指向基准数
  p := left
  // i,j分别代表了需要进行一趟排序的数组的首尾
  i := left
  j := right
  // 定义我们的基准数,每次将数组的第一个值当作基准数比较
  key := data[i]
  for i <= j {
        // 如果右边的数字大于基准数,不需要进行改变
    for key <= data[j] && j >= p {
      j--
    }
    if p <= j {
      data[i], data[j] = data[j], data[i]
      p = j
        }
        // 如果左边的数字小于基准数,不需要进行改变
    for i <= p && key >= data[i] {
      i++
    }
    if i <= p {
      data[i], data[j] = data[j], data[i]
      p = i
    }
  }
  // 如果左边仍然有可排序的数组,继续递归
  if p-left > 1 {
    QuickSelect(data, left, p-1)
    }
    // 如果右边仍然有可排序的数组,继续递归
  if right-p > 1 {
    QuickSelect(data, p+1, right)
  }

解法二:部分排序

对于题目的要求中,仔细分析其实我们没有必要对我们的数组进行排序,输出的k个数可以是无序的,因此我们只需要对部分元素进行排序,可以用如下的思路,我们可以选择前k个数默认为最小的k个数,存到数组temp中,然后求出temp数组中的最大值,用这个值去和其它的数比较,如果发现有比这个数小的,就进行交换,然后求出再次求出temp数组的最大值,按照这样的方式,我们仍然可以求出最小的k个数。求最大值我们可以根据选择排序或者交换排序求出最大值。时间复杂度为O(k),因为总共需要 比较遍历后面的n-k个数,因此时间复杂度是O(K) + (n-k)O(k) = O(nk)

选择排序的思想

第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

选择排序代码分析

(1)首先我们可以默认第一个数为最小的数,让它去和后面的数进行比较,在比较的过程中,逐渐去寻找最小的数,记录下标

(2)找到最小的数后,我们就可以让该数和第一个数进行位置交换

(3)同样我们假设第二数是第二小的数,按照 上面的方式比较,求出第二个数字

(4)和第二个数进行交换

.....

选择排序求出最大值

有了上面的分析,我们很容易可以写出求出最大值的代码,就是遍历数组,不停的比较,因为,我们只需要求出最大值,因此我们不需要进行排序

// 利用部分排序寻找最小的k个数
func FindNumByPartSort(data []int, k int) (result []int) {
  // 默认前k个数为最小
  result = data[0:k]

  for i := k; i < len(data); i++ {
    // 找到最大值的坐标
        max := select_sort(result)
        // 比较
    if result[max] > data[i] {
            // 交换
      result[max], data[i] = data[i], result[max]
    }
  }

  return result
}
func select_sort(data []int) (max int) {
  max = 0
  for i := 1; i < len(data); i++ {
    if data[i] > data[max] {
      max = i
    }
  }
  return max
}

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 30天习惯养成

    今天是第五天了,越来越能体会到什么是“路漫漫”了,对于今天,可以用一句话概括,一上午画图,一下午敲键盘。

    陌无崖
  • 分布式自增数据库ID

    今天在写项目的时候学习了一个用代码编写的自增的数据库ID,其实是一个ID缓冲池。使用了golang中chan类型。

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

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

    陌无崖
  • 深入理解排序算法

    [本篇博文会对常见的排序算法进行分析与总结,并会在最后提供几道相关的一线互联网企业面试/笔试题来巩固所学及帮助我们查漏补缺。项目地址:https://githu...

    sunsky
  • 排序在数据分析中有多重要?

    说不会对数据排序的举手,所有的手都放下了。拿到数据,谁还不会排序吗?就连你在打牌时都在排序。 ? 可是这一小小的操作,在数据分析中到底有...

    CDA数据分析师
  • 排序在数据分析中有多重要?

    说不会对数据排序的举手,所有的手都放下了。拿到数据,谁还不会排序吗?就连你在打牌时都在排序。 ? 可是这一小小的操作,在数据分析中到底有多重要,有人知道吗?我们...

    小莹莹
  • 字符串排序----高位优先的字符串排序

    SuperHeroes
  • 排序算法图解(插入、选择、冒泡、快速、合并、希尔等等)

    老梁
  • C++|计数排序[7]

    外排序 :由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

    Rare0716
  • 排序算法之冒泡、插入、快排和选择排序

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

    海仔

扫码关注云+社区

领取腾讯云代金券