協助實現基數排序在JavaScript中

Question

我需要一些幫助在JavaScript中實現基數排序algorthim。

我發現this example網上，用下面的代碼，但我不明白，我怎麼調用函數，因爲它出現在這個網站進行調整：

// 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'); 
} 

Answer 1

術語「基數排序」是棘手的。實際上有兩種不同的類型以相似的方式工作 - 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/。然後，我將它們編譯爲javascript，並在http://jashkenas.github.com/coffee-script/處編寫了插入方法/重新格式化以提高可讀性。

Answer 2

我的版本是更冗長，但很快就執行鍼對大型數據集：

 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 3

基數排序是一個美妙的線性時間排序算法。許多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

Answer 4

您所提供的鏈接更多細節的陣列不再可用，但我希望我的實施對您或任何有興趣的人都儘可能清晰。

我執行在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); 

最後測試這個方法，因爲在書中mentionned，這種特殊的算法工作，只是因爲統計排序是就地排序算法，這意味着如果兩個元素配合，它們的順序輸入數組中發生的事件被保留。