Javascript Radix排序

Question

我一直在网上寻找一段时间,我想知道是否有一个通常使用的Radix Sort的'稳定'的事实实现？

基数排序的两个分类是最低有效数字(LSD)基数排序和最高有效数字(MSD)基数排序.

寻找LSD或MSD的示例.

Answer 1

我的版本更冗长,但即使对于大量项目也能快速执行:

      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);          

Answer 2

以下函数对 Uint32 值进行 LSB 基数排序。顺便说一句，它比内置排序功能更快。

它使用类型化数组来提高性能，但如果传递普通数组也同样有效，只要它们仅包含 32 位值即可：

function radixSortUint32(input) {
  const arrayConstr = input.length < (1 << 16) ?
    Uint16Array :
    Uint32Array;
  const numberOfBins = 256 * 4;
  let count = new arrayConstr(numberOfBins);

  let output = new Uint32Array(input.length);

  // count all bytes in one pass
  for (let i = 0; i < input.length; i++) {
    let val = input[i];
    count[val & 0xFF]++;
    count[((val >> 8) & 0xFF) + 256]++;
    count[((val >> 16) & 0xFF) + 512]++;
    count[((val >> 24) & 0xFF) + 768]++;
  }

  // create summed array
  for (let j = 0; j < 4; j++) {
    let t = 0,
      sum = 0,
      offset = j * 256;
    for (let i = 0; i < 256; i++) {
      t = count[i + offset];
      count[i + offset] = sum;
      sum += t;
    }
  }

  for (let i = 0; i < input.length; i++) {
    let val = input[i];
    output[count[val & 0xFF]++] = val;
  }
  for (let i = 0; i < input.length; i++) {
    let val = output[i];
    input[count[((val >> 8) & 0xFF) + 256]++] = val;
  }
  for (let i = 0; i < input.length; i++) {
    let val = input[i];
    output[count[((val >> 16) & 0xFF) + 512]++] = val;
  }
  for (let i = 0; i < input.length; i++) {
    let val = output[i];
    input[count[((val >> 24) & 0xFF) + 768]++] = val;
  }

  return input;
}

以下是如何重新使用上述值Int32：

function radixSortInt32(input) {
  // make use of ArrayBuffer to "reinterpret cast"
  // the Int32Array as a Uint32Array
  let uinput = input.buffer ?
    new Uint32Array(input.buffer):
    Uint32Array.from(input);

  // adjust to positive nrs
  for (let i = 0; i < uinput.length; i++) {
    uinput[i] += 0x80000000;
  }

  // re-use radixSortUint32
  radixSortUint32(uinput);

  // adjust back to signed nrs
  for (let i = 0; i < uinput.length; i++) {
    uinput[i] -= 0x80000000;
  }

  // for plain arrays, fake in-place behaviour
  if (input.buffer === undefined){
    for (let i = 0; i < input.length; i++){
      input[i] = uinput[i];
    }
  }

  return input;
}

还有一个类似的值技巧Float32：

function radixSortFloat32(input) {
  // make use of ArrayBuffer to "reinterpret cast"
  // the Float32Array as a Uint32Array
  let uinput = input.buffer ?
    new Uint32Array(input.buffer) :
    new Uint32Array(Float32Array.from(input).buffer);

  // Similar to radixSortInt32, but uses a more complicated trick
  // See: http://stereopsis.com/radixSort.html
  for (let i = 0; i < uinput.length; i++) {
    if (uinput[i] & 0x80000000) {
      uinput[i] ^= 0xFFFFFFFF;
    } else {
      uinput[i] ^= 0x80000000;
    }
  }

  // re-use radixSortUint32
  radixSortUint32(uinput);

  // adjust back to original floating point nrs
  for (let i = 0; i < uinput.length; i++) {
    if (uinput[i] & 0x80000000) {
      uinput[i] ^= 0x80000000;
    } else {
      uinput[i] ^= 0xFFFFFFFF;
    }
  }

  if (input.buffer === undefined){
    let floatTemp = new Float32Array(uinput.buffer);
    for(let i = 0; i < input.length; i++){
      input[i] = floatTemp[i];
    }
  }

  return input;
}

我制作了一组可与所有 32 位或更少的 TypedArray 一起使用的函数。那是：

• Uint32Array
• Int32数组
• 浮点32数组
• Uint16数组
• Int16数组
• Uint8Array
• 整型8数组
• 您知道所有值都符合这些条件之一的任何普通数组

完整要点在这里。稍后我可能会尝试 Float64，然后我们基本上就会支持所有javascript 数字。

TypedArray 基准测试显示 radix 击败了内置排序函数。

使用普通数组也更快，尽管由于增加的开销而没有那么快