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

Question

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

我该怎么做？

Answer 1

您可以通过修改桶排序算法来实现此目的，下面我包含了一个 JavaScript 实现，请参阅 Github有关源代码的更多详细信息。此实现使用 16 个桶，您必须修改它以允许 k桶，你可以省略桶本身的排序。一种方法是使用 2^p buckets 其中 p 是满足 2^p < n 的最小整数.该算法将在 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>