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
}