Javascript Radix Sort

Question

我一直在網上尋找一段時間，我想知道是否有一個'穩定的'事實上實際的​​基數排序通常使用？

基數排序的兩種分類是最低有效數字（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

的Javascript LSD排序：

var counter = [[]]; 
function sortLSD(array, maxDigitSymbols) { 
    var mod = 10; 
    var dev = 1; 
    for (var i = 0; i < maxDigitSymbols; i++, dev *= 10, mod *= 10) { 
     for (var j = 0; j < array.length; j++) { 
      var bucket = parseInt((array[j] % mod)/dev); 
      if (counter[bucket] == null) { 
       counter[bucket] = []; 
      } 
      counter[bucket].push(array[j]); 
     } 
     var pos = 0; 
     for (var j = 0; j < counter.length; j++) { 
      var value = null ; 
      if (counter[j] != null) { 
       while ((value = counter[j].shift()) != null) { 
        array[pos++] = value; 
       } 
      } 
     } 
    } 
    return array; 
} 
var test = [22, 1,2,9,3,2,5,14,66]; 
console.log(sortLSD(test, 2)); 

Answer 3

下面的代碼，你可以通過數組大量的項目。

var counter = [[]]; // Radix sort Array container to hold arrays from 0th digit to 9th digits 
 
    function radixSortLSD(array) { 
 
     var max = 0, mod = 10,dev = 1; //max 
 
     for(var i=0;i<array.length;i++){ 
 
      if(array[i] >max){ 
 
       max = array[i]; 
 
      } 
 
     } 
 
     // determine the large item length 
 
     var maxDigitLength = (max+'').length; 
 
     for (var i = 0; i < maxDigitLength; i++, dev *= 10, mod *= 10) { 
 
      for(var j = 0; j < array.length; j++) { 
 
       var bucket = Math.floor((array[j] % mod)/dev);// Formula to get the significant digit 
 
       if(counter[bucket]==undefined) { 
 
        counter[bucket] = []; 
 
       } 
 
       counter[bucket].push(array[j]); 
 
      } 
 
      var pos = 0; 
 
      for(var j = 0; j < counter.length; j++) { 
 
       var value = undefined; 
 
       if(counter[j]!=undefined) { 
 
        while ((value = counter[j].shift()) != undefined) { 
 
         array[pos++] = value; 
 
        } 
 
       } 
 
      } 
 
     } 
 
     console.log("ARRAY: "+array); 
 
    }; 
 
var sampleArray = [1,121,99553435535353534,345,0]; 
 
radixSortLSD(sampleArray);

Answer 4

基數排序是一個美妙線性時間排序算法。許多CPU和GPU的快速實現已經完成。這是我從我的C++實現翻譯成JavaScript的一個。它比較用JavaScript內置的排序和爲5〜50倍更快排序無符號整數High Performance Radix Sort LSD

Answer 5

的陣列我遇到CRLS第三版8.3節

基數排序這本書提供的基數排序的神祕起源。它將MSD版本描述爲過時和棘手。它還建議實施LSD。

這裏我提供一個使用這種技術的基數排序的實現。

讓我們開始通過僞代碼：

/** 
* @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); 

最後，正如本書中提到的，這種特定算法的工作原理僅僅是因爲counting-sort是一種就地排序算法，這意味着如果兩個元素相連，它們在輸入數組中的出現次序將被保留。

Answer 6

以下函數對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位或更少的所有TypedArrays。那就是：

• Uint32Array
• Int32Array
• Float32Array
• Uint16Array
• Int16Array
• Uint8Array
• Int8Array
• 任何普通數組，你知道所有值符合上述條件之一

Full gist here。我以後可能會去Float64，那麼我們基本上都會支持全部的 javascript數字。

TypedArray benchmarks shows radix beats the built-in sort function。

It's faster with plain arrays too, although not quite as much because of the added overhead