如何按大小对数字进行分组

Question

我有 n 个不同的数字，我想将它们分成 k 组，这样第 1 组中的任何数字都小于第 2 组中的任何数字，以及第 2 组中的任何人都小于第 3 组中的任何人，依此类推，直到 k 组（不必在每个组内对数字进行排序）。我被要求设计一个在 O(n log k) 中运行的算法，但我只能想出 O(n^2) ]个。

我该怎么做？

Answer 1

您可以通过修改桶排序算法来实现此目的，下面我提供了一个 JavaScript 实现，有关源代码的更多详细信息，请参阅 Github。此实现使用 16 个桶，您必须修改它以允许 k 个桶，并且您可以省略桶本身的排序。一种方法是使用 2^p 个桶，其中 p 是满足 2^p < n 的最小整数。该算法将运行 in O(n log k)

// Copyright 2011, Tom Switzer
// Under terms of ISC License: http://www.isc.org/software/license

/**
 * Sorts an array of integers in linear time using bucket sort.
 * This gives a good speed up vs. built-in sort in new JS engines
 * (eg. V8). If a key function is given, then the result of
 * key(a[i]) is used as the integer value to sort on instead a[i].
 *
 * @param a A JavaScript array.
 * @param key A function that maps values of a to integers.
 * @return The array a.
 */
function bsort(a, key) {
  key = key || function(x) {
    return x
  };
  var len = a.length,
    buckets = [],
    i, j, b, d = 0;
  for (; d < 32; d += 4) {
    for (i = 16; i--;)
      buckets[i] = [];
    for (i = len; i--;)
      buckets[(key(a[i]) >> d) & 15].push(a[i]);
    //This implementation uses 16 buckets, you will need to modify this
    for (b = 0; b < 16; b++)
      //The next two lines sort each bucket, you can leave it out
      for (j = buckets[b].length; j--;)
        a[++i] = buckets[b][j];
  }
  return a;
}


var array = [2, 4, 1, 5, 3];

$('#result').text(bsort(array, function(x) {
  return x
}));

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="result"></div>

Answer 2

注意问题陈述是将n个不同个数分成k组。如果存在如下 wiki 链接中所述的重复项，这将变得更加复杂。

任何可以确定复杂度小于 O(n log(k)) 的第 k 个最小元素的过程都可以使用 k-1 次来生成与 k 组之间的边界对应的元素数组。然后可以在数组上进行一次传递，对边界数组进行二进制搜索，将数组分成 k 组，复杂度为 O(n log(k))。但是，似乎至少有一种找到第 k 个最小元素的算法也会对数组进行分区，因此可以单独使用它来创建 k 个组。

使用最坏情况时间为 O(n) 的选择算法进行无序部分排序是可能的。维基链接：

http://en.wikipedia.org/wiki/Selection_algorithm

http://en.wikipedia.org/wiki/Selection_algorithm#Unordered_partial_sorting

http://en.wikipedia.org/wiki/Quickselect

http://en.wikipedia.org/wiki/Median_of_medians

http://en.wikipedia.org/wiki/Soft_heap#Applications

Answer 3

使用带有快速排序分区函数的 K 选择算法 - QuickSelect。
为简单起见，让我们将 K 设为 2 的幂。
在第一阶段我们对 N 个元素进行划分，需要 O(N) ~ p* N 时间，其中 p 是某个常数
在第二阶段，我们递归地对 N/2 个元素进行 2 次分区，需要 2* p* N/2 = p*N 时间。
第三阶段我们对N/4个元素进行4次分区，需要4*pN/4 = pN次。
...
在最后阶段，我们对 N/K 个元素进行 K 分区，需要 K* p* N/K = p*N 时间。

注意有 Log(K) 个阶段，所以总时间是 Log(K) * p * N = O(N*Log(K)

Answer 4

感谢您的所有帮助，基本上是一个快速选择（或任何线性时间排序算法，在线性时间内找到第 k 个统计量就足够了），并且在运行它 k-1 次之后，我们对原始数组进行二进制搜索以将元素分成组，得到 O(nlog k)。

另外，如果不想二分查找的话，在quickselect中，也可以把元素分开，在每个子集中查找统计！ @rcgldr，@MBo 谢谢你的想法！

如何按大小对数字进行分组

How to group numbers by size

sorting

algorithm

complexity-theory