0

我需要一些帮助在 JavaScript 中实现基数排序算法。

我在网上找到了这个示例，代码如下，但我不明白如何调用该函数，因为它似乎是为该站点量身定制的：

// Radix sort a (base 2)
// Numbers must be in the range 0 to 2**31 - 1
function radixSort() {
  readArray('i');
  var b0 = new obj();  // Bin for 0 digits
  var b1 = new obj();  // Bin for 1 digits

  for (var i=0; i<32; ++i) {
    if (form.step.checked) {  // Single step
      writeArray('i','a');

      if (!confirm("Sort on bit "+i))
        return;    
    }

    var mask = 1<<i;     // Digit (2**i)
    var biggest = 2<<i;  // If all of a is smaller, we're done
    var zeros=0;         // Number of elements in b0, b1
    var ones=0;
    var found=false;     // Any digits past i?

    for (var j=0; j<n; ++j) { // Sort into bins b0, b1
      if ((a[j] & mask) == 0)
        b0[zeros++] = a[j];
      else
        b1[ones++] = a[j];

      if (a[j]>=biggest)  // Any more digits to sort on?
        found=true;
    }

    for (j=0; j<zeros; ++j)  // Concatenate b0, b1 back to a
      a[j]=b0[j];

    for (j=0; j<ones; ++j)
      a[j+zeros]=b1[j];

    form.imoves.value = parseInt(form.imoves.value)+n;

    if (!found)
      break;
  }

  writeArray('i','a');
}
4

4 回答 4

4

术语“基数排序”是一个棘手的问题。实际上有两种不同的类型以类似的方式工作 - MSB（最高有效位）基数和 LSB（最低有效位）基数。（您有时会看到 B 被 D 代替）。以下是两者的实现。

MSB 基数：

//arguments to sort an array:
//arr: array to be sorted
//begin: 0
//end: length of array
//bit: maximum number of bits required to represent numbers in arr
function sort(arr, begin, end, bit)
{
  var i, j, mask;
  i = begin;
  j = end;
  mask = 1 << bit;
  while(i < j)
  {
    while(i < j && !(arr[i] & mask))
    {
      ++i;
    }
    while(i < j && (arr[j - 1] & mask))
    {
      --j;
    }
    if(i < j)
    {
      j--;
      var tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
      i++;
    }
  }
  if(bit && i > begin)
  {
    sort(arr, begin, i, bit - 1);
  }
  if(bit && i < end)
  {
    sort(arr, i, end, bit - 1);
  }
}
sort(arr, 0, arr.length, 32);  //Here I've assumed that the values in arr are integers that fit in 32 bits

LSB 基数：

function insert(arr, i, j)
{
  tmp = arr[i];
  arr.splice(i, 1);
  arr.splice(j, 0, tmp);
}

//arguments to sort an array:
//arr: array to be sorted
function sort(arr)
{
  var bit, end, i, mask;
  bit = 0;
  while(true) 
  {
    mask = 1 << bit;
    i = 0;
    end = arr.length;
    while(i < end)
    {
      if(arr[i] & mask)
      {
        insert(arr, i, arr.length - 1);
        end--;
      }
      else
      {
        i++;
      }
    }
    bit++;
    if(end === arr.length)
    {
      break;
    }
  }
}

我从http://visualsort.appspot.com/中提取了这些算法。然后我在http://jashkenas.github.com/coffee-script/将它们编译为 javascript ，并编写了插入方法/重新格式化以提高可读性。

于 2011-10-29T07:04:05.017 回答
1

您提供的链接不再可用，但我希望我的实现对您或任何感兴趣的人来说尽可能清晰。

我正在实现 CRLS 第三版第 8.2 节中介绍的基数排序版本

让我们从伪代码开始：

计数排序

/**
 * @param k: the max of input, used to create a range for our buckets
 * @param exp: 1, 10, 100, 1000, ... used to calculate the nth digit
 */
Array.prototype.countingSort = function (k, exp) {
    /* eslint consistent-this:0 */
    /* self of course refers to this array */
    const self = this;

    /**
     * let's say the this[i] = 123, if exp is 100 returns 1, if exp 10 returns 2, if exp is 1 returns 3
     * @param i
     * @returns {*}
     */
    function index(i) {
        if (exp)
            return Math.floor(self[i] / exp) % 10;
        return i;
    }

    const LENGTH = this.length;

    /* create an array of zeroes */
    let C = Array.apply(null, new Array(k)).map(() => 0);
    let B = [];

    for (let i = 0; i < LENGTH; i++)
        C[index(i)]++;

    for (let i = 1; i < k; i++)
        C[i] += C[i - 1];

    for (let i = LENGTH - 1; i >= 0; i--) {
        B[--C[index(i)]] = this[i];
    }

    B.forEach((e, i) => {
        self[i] = e
    });
}

这是唯一棘手的部分，其余的非常简单

Array.prototype.radixSort = function () {
    const MAX = Math.max.apply(null, this);

    /* let's say the max is 1926, we should only use exponents 1, 10, 100, 1000 */
    for (let exp = 1; MAX / exp > 1; exp *= 10) {
        this.countingSort(10, exp);
    }
}

现在这是一个如何测试这个方法

let a = [589, 111, 777, 65, 124, 852, 345, 888, 553, 654, 549, 448, 222, 165];
a.radixSort()
console.log(a);

最后，正如书中提到的，这种特殊算法之所以有效，只是因为计数排序是一种就地排序算法，这意味着如果两个元素相同，它们在输入数组中的出现顺序会被保留。

于 2017-08-07T23:38:21.623 回答
0

我的版本更冗长，但对于大型数据集执行非常快：

      var testArray = [ 331, 454, 230, 34, 343, 45, 59, 453, 345, 231, 9 ];

  function radixBucketSort (arr) {
    var idx1, idx2, idx3, len1, len2, radix, radixKey;
    var radices = {}, buckets = {}, num, curr;
    var currLen, radixStr, currBucket;

    len1 = arr.length;
    len2 = 10;  // radix sort uses ten buckets

    // find the relevant radices to process for efficiency        
    for (idx1 = 0;idx1 < len1;idx1++) {
      radices[arr[idx1].toString().length] = 0;
    }

    // loop for each radix. For each radix we put all the items
    // in buckets, and then pull them out of the buckets.
    for (radix in radices) {          
      // put each array item in a bucket based on its radix value
      len1 = arr.length;
      for (idx1 = 0;idx1 < len1;idx1++) {
        curr = arr[idx1];
        // item length is used to find its current radix value
        currLen = curr.toString().length;
        // only put the item in a radix bucket if the item
        // key is as long as the radix
        if (currLen >= radix) {
          // radix starts from beginning of key, so need to
          // adjust to get redix values from start of stringified key
          radixKey = curr.toString()[currLen - radix];
          // create the bucket if it does not already exist
          if (!buckets.hasOwnProperty(radixKey)) {
            buckets[radixKey] = [];
          }
          // put the array value in the bucket
          buckets[radixKey].push(curr);          
        } else {
          if (!buckets.hasOwnProperty('0')) {
            buckets['0'] = [];
          }
          buckets['0'].push(curr);          
        }
      }
      // for current radix, items are in buckets, now put them
      // back in the array based on their buckets
      // this index moves us through the array as we insert items
      idx1 = 0;
      // go through all the buckets
      for (idx2 = 0;idx2 < len2;idx2++) {
        // only process buckets with items
        if (buckets[idx2] != null) {
          currBucket = buckets[idx2];
          // insert all bucket items into array
          len1 = currBucket.length;
          for (idx3 = 0;idx3 < len1;idx3++) {
            arr[idx1++] = currBucket[idx3];
          }
        }
      }
      buckets = {};
    }
  }
  radixBucketSort(testArray);
  console.dir(testArray);
于 2016-08-16T16:23:22.810 回答
0

Radix Sort 是一个很棒的线性时间排序算法。已经为 CPU 和 GPU 完成了许多快速实现。这是我从我的 C++ 实现翻译成 JavaScript 的一个。它与 JavaScript 内置排序相比，对无符号整数数组的排序快 5 到 50 倍

var extractDigit = function( a, bitMask, shiftRightAmount ) {
    var digit = (a & bitMask) >>> shiftRightAmount; // extract the digit we are sorting based on
    return digit;
}
// June 2017 Victor J. Duvanenko High Performance LSD Radix Sort for arrays of unsigned integers
function radixSortLSD(_input_array) {
    var numberOfBins = 256;
    var Log2ofPowerOfTwoRadix = 8;
    var _output_array = new Array(_input_array.length);
    var count = new Array(numberOfBins);
    var _output_array_has_result = false;

    var bitMask = 255;
    var shiftRightAmount = 0;

    var startOfBin = new Array( numberOfBins );
    var endOfBin   = new Array( numberOfBins );

    while( bitMask != 0 )    // end processing digits when all the mask bits have been processed and shifted out, leaving no bits set in the bitMask
    {
        for (var i = 0; i < numberOfBins; i++ )
            count[ i ] = 0;
        for (var _current = 0; _current < _input_array.length; _current++ )    // Scan the array and count the number of times each digit value appears - i.e. size of each bin
            count[ extractDigit( _input_array[ _current ], bitMask, shiftRightAmount ) ]++;

        startOfBin[ 0 ] = endOfBin[ 0 ] = 0;
        for( var i = 1; i < numberOfBins; i++ )
            startOfBin[ i ] = endOfBin[ i ] = startOfBin[ i - 1 ] + count[ i - 1 ];
        for ( var _current = 0; _current < _input_array.length; _current++ )
            _output_array[ endOfBin[ extractDigit( _input_array[ _current ], bitMask, shiftRightAmount ) ]++ ] = _input_array[ _current ];

        bitMask <<= Log2ofPowerOfTwoRadix;
        shiftRightAmount += Log2ofPowerOfTwoRadix;
        _output_array_has_result = !_output_array_has_result;

        var tmp = _input_array, _input_array = _output_array, _output_array = tmp;    // swap input and output arrays
    }
    if ( _output_array_has_result )
        for ( var _current = 0; _current < _input_array.length; _current++ )    // copy from output array into the input array
            _input_array[ _current ] = _output_array[ _current ];

    return _input_array;
}

有关此实现和性能比较的更多详细信息High Performance JavaScript Radix Sort LSD

于 2017-06-18T02:37:46.320 回答