我已经在网上搜索了一段时间，想知道是否有一个“稳定”的事实标准Radix Sort实现通常被使用？
基数排序有两种分类：最低有效位（LSD）基数排序和最高有效位（MSD）基数排序。
寻找LSD或MSD的示例。
JavaScript 基数排序
7
- BendYourTaxes
11
3这里的讨论与主题无关。请访问[帮助]页面以了解原因。很可能在CODEREVIEW更合适。 - mplungjan
刚刚更新了问题，谢谢。 - BendYourTaxes
1实现基数排序的标准方式是LSD。自1950年代以来，这种方式就已经存在了，当时使用卡片分类器。使用LSD，每个基数排序步骤后，桶可以合并到下一个步骤中。使用MSD，则必须保持桶分离，所以如果按十进制排序，则第一步有10个桶，第二步有100个桶，第三步有1000个桶等等，因此通常不被使用。 - rcgldr
如果有人能够用JavaScript干净地编写基数排序，并且使用更少的循环，请通过@jasonleonhard让我知道，我仍然很好奇它会是什么样子。我的猜测是使用条件语句的单个循环而不是额外的循环，但是截至今天，我还没有看到少于3个循环的实现，无论这些循环是否在单独的方法中。提前感谢大家的参与！ - jasonleonhard
@jasonleonhard：循环的数量是性能的非常糟糕的估计。虽然运行时嵌套循环的数量可能会提供更多信息，但是这些循环的界限将决定速度。在批评它们的循环次数之前，您是否对各种解决方案进行过基准测试？ - Scott Sauyet
显示剩余6条评论
11个回答
6
我的版本可能会更冗长，但对于大量项目，执行速度很快：
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.log(testArray);
- Greg Lafrance
1
你在这里使用了很多循环（5个），因此这不是一个非常高效的解决方案。 - jasonleonhard
5
以下函数对Uint32值执行LSB基数排序。顺便说一下，它比内置的排序函数快。
它使用类型化数组来提高性能，但只要传递的是仅包含32位值的纯数组，它就可以正常工作：
以下是如何将上述内容应用于Int32值的方法：
我编写了一组函数，可以处理所有32位或以下的TypedArrays，包括：
它使用类型化数组来提高性能，但只要传递的是仅包含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
- 任何你知道所有值都符合这些标准的普通数组
- Job
1
基数排序（LSD）
function radixSort(arr) {
const base = 10;
let divider = 1;
let maxVal = Number.NEGATIVE_INFINITY;
while (divider === 1 || divider <= maxVal) {
const buckets = [...Array(10)].map(() => []);
for (let val of arr) {
buckets[Math.floor((val / divider) % base)].push(val);
maxVal = val > maxVal ? val : maxVal;
}
arr = [].concat(...buckets);
divider *= base;
}
return arr;
}
免责声明：它仅适用于正整数。
- 对于混合的负数和正数，请查看this版本。
- 我避免使用
Math.max，因为它会在非常大的数组上使用大量资源。
- Lior Elrom
2
简洁易懂的答案是+1，但你在这里使用了很多循环（3），因此这不是一个非常高效的解决方案。 - jasonleonhard
1话虽如此，在撰写本文时，这个答案既是最简洁的，也是循环次数最少的（3次），与 @Abanoub Fathy 在循环次数上并列，但更为简洁，并且所有操作都在一个方法中处理（这种方法有其优缺点）。 - jasonleonhard
1
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));
- BendYourTaxes
1
简洁易读的答案+1，但你在这里使用了很多循环（4个），因此这不是一个非常高效的解决方案。 - jasonleonhard
1
使用下面的代码，您可以传递包含大量项的数组。
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);- Pradeep kumar
1
通过位运算进行LSD基数排序可能如下所示:
这里在做什么？
我们按照八进制进行排序（
我们创建
我们使用“掩码”获取给定数字的每个八进制数字，例如：
如果
对于每次迭代，我们获取
对于
为了处理负数，我们实际上同时执行两个基数排序：将负值反向排序，将正值按正常顺序排序。如果数字是负数，则表示数字7应该在0处，6应该在1处，5应该在2处，以此类推。
如果是正数，则表示基数7应该在索引14处，6应该在13处等等。
最后的检查 -
当然，基数排序只能用于整数。
如果您需要使用大于
const initialMask = 0b1111;
const bits = 4;
const getBuckets = () => Array.from(
{ length: (2 * initialMask) + 1 },
() => [],
);
function radixSort(array) {
let max = 0;
array.forEach(n => {
const abs = Math.abs(n);
if (abs > max) max = abs;
});
if (max >= 0x80000000) {
throw new Error('cannot perform bitwise operations on numbers >= 0x80000000');
}
for (
let mask = initialMask,
shifted = 0,
buckets = getBuckets();
true;
mask = (mask << bits),
shifted = (shifted + bits),
buckets = getBuckets()
) {
array.forEach(n => {
const digit = mask & Math.abs(n);
const bucket = (Math.sign(n) * (digit >> shifted)) + initialMask;
buckets[bucket].push(n);
});
let i = 0;
buckets.forEach(bucket => bucket.forEach(n => {
array[i] = n;
i += 1;
}));
if ((max ^ mask) <= mask) break;
}
}
const getArray = () => Array.from(
{ length: 1e6 },
() => Math.floor(Math.random() * 0x80000000) * Math.sign(Math.random() - 0.5),
);
const isSorted = array => {
for (let i = 1; i < array.length; i += 1) {
if (array[i - 1] > array[i]) return false;
}
return true;
}
const radixArray = getArray();
const nativeArray = radixArray.slice();
const radixStart = +new Date();
radixSort(radixArray);
const radixEnd = +new Date();
const nativeStart = +new Date();
nativeArray.sort();
const nativeEnd = +new Date();
document.write(`
<dl>
<dt>Sorted array in</dt>
<dd>${radixEnd - radixStart}ms</dd>
<dt>Properly sorted</dt>
<dd>${isSorted(radixArray)}</dd>
<dt>Sorted with Array.prototype.sort in</dt>
<dd>${nativeEnd - nativeStart}ms</dd>
</dl>
`);我们按照八进制进行排序（
0b1111 有助于概念化位运算）。我们创建
0b1111 * 2 + 1 个桶，这是集合 [-0b1111 … 0b1111] 中的项数。我们使用“掩码”获取给定数字的每个八进制数字，例如：
如果
n = 0b101000101010，n & 0b1111 给出了 0b1010，这是 n 的第一个八进制数字。对于每次迭代，我们获取
n & 0b11110000，然后是 n & 0b111100000000，以此隔离每个连续的八进制数字。对于
n & 0b11110000，我们得到了 0b00100000，我们想要的是 0b0010，所以我们执行了一个右移 4 位。下一次迭代将向右移动 8 位，依此类推。为了处理负数，我们实际上同时执行两个基数排序：将负值反向排序，将正值按正常顺序排序。如果数字是负数，则表示数字7应该在0处，6应该在1处，5应该在2处，以此类推。
如果是正数，则表示基数7应该在索引14处，6应该在13处等等。
最后的检查 -
（max ^ mask）<= mask - 确定掩码是否已经获取了最高位数字的最大值。如果是，则数组已排序。当然，基数排序只能用于整数。
如果您需要使用大于
0x80000000的数字，则可以使用字符串进行实现。- Joseph Nields
1
我相信所有这些答案都是可行的，但我非常重视重构来解释底层发生了什么。因此，这里是带有辅助方法的答案：
// helper
function getDigit(num, place) {
return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}
// helper
function digitCount(num) {
if (num === 0) {
return 1;
}
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
// helper
function mostDigits(nums) {
let max = 0;
for (let num of nums) {
max = Math.max(max, digitCount(num));
}
return max;
}
function radixSort(nums) {
let maxDigits = mostDigits(nums);
for (let k = 0; k < maxDigits; k++) {
let buckets = Array.from({length: 10}, () => []);
for (let num of nums) {
let digit = getDigit(num, k);
buckets[digit].push(num);
}
nums = [].concat(...buckets);
}
return nums;
}
- Dev
3
这里仍然使用了很多循环（3），因此这不是一个非常高效的解决方案。而且，这几乎是另一个网站上的答案的完全副本，包括方法和变量的名称及其实现。请参见：https://www.freecodecamp.org/news/introduction-to-algorithms-with-javascript-examples/#radix-sort - jasonleonhard
话虽如此，我同意重构是好的，并且要使用“SOLID原则”中的“单一职责原则”。总的来说，如果这是你的答案，那么它已经足够好了。我要提到我链接的文章是在你发表答案之后才发布的，所以他们可能抄袭了你的答案，而不是相反。 - jasonleonhard
然而，提供更多关于你答案本身的见解是明智的。你是如何得出这个答案的？主要部分是什么？概念框架是什么？所有这些都将有助于提高对抄袭的担忧。同时也能帮助人们决定为什么应该选择你的答案而不是其他人的。 - jasonleonhard
0
用户Jason Leonhard重新提出了这个旧问题，寻找新的解决方案。他似乎认为各种答案中的循环都是一个性能问题。虽然我怀疑这是真的，但至少下面的版本将明确的循环隐藏在数组方法和递归调用之后：
// problems with Math.max for large parameter lists
const maximum = (ns) => ns .reduce ((m, n) => n > m ? n : m, -Infinity)
const radixSort = (ns, max = maximum (ns), divisor = 1) =>
divisor < max
? radixSort (ns .reduce (
(buckets, n) => ((buckets [(~~ (n / divisor)) % 10] .push (n)), buckets),
[... Array (10)] .map (() => [])
) .flat (), max , divisor * 10)
: ns
console .log (radixSort ([5, 3, 88, 235, 65, 23, 4632, 234]))
console .log (radixSort ([589, 111, 777, 65, 124, 852, 345, 888, 553, 654, 549, 448, 222, 165])).as-console-wrapper {max-height: 100% !important; top: 0}这个只适用于正整数。我们可以做一些优化。我们可以内联调用maximum。我们可以用[[], [], [], [], [], [], [], [], [], []]替换[... Array (10)] .map (() => []) 。这些会稍微减少时钟时间，但不会改变算法复杂度。
与其他答案一样，它的算法复杂度似乎是O(n*d)，其中n是要排序的元素数量，d是最大元素的位数。实际速度可能比Lior Elrom的答案慢，因为它暴露了相同的算法，但使用递归函数调用而不是while循环。或者也许不是，因为它只在最前面找到最大值一次，而不是像那个答案一样在每次迭代中都找到最大值。但重要的是，如果没有进行基准测试，我们真的不知道哪一个是最快的，或者对于多少数字/什么最高位数，其中一个比另一个更快。
- Scott Sauyet
0
我的实现
// get the digits in the number by index
const getDigit = (num, index) => {
return Math.floor(Math.abs(num) / Math.pow(10, index)) % 10;
}
// get the number of digits in a number
const getNumberOfDigits = (num) => {
if(num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
// get the max Number of digits in arr
const getMaxNumOfDigits = (arr) => {
let max = 0;
for(let item of arr) {
max = Math.max(max, getNumberOfDigits(item))
}
return max;
}
// sorting the numbers
const radixSort = (arr) => {
let maxIteration = getMaxNumOfDigits(arr),
buckets;
for (let i = 0; i < maxIteration; i++) {
// set bucket to arr of 10 empty sub arrs
buckets = Array.from({length: 10}, () => []);
for(let item of arr) {
// put the number in the right bucket position
buckets[getDigit(item, i)].push(item);
}
// re-collect from the buckets
arr = [].concat(...buckets);
}
return arr;
}
radixSort([9, 212, 55, 19, 111, 3])
console.log(radixSort([9, 212, 55, 19, 111, 3]))
- Abanoub Fathy
1
简洁易懂的答案是+1，但你在这里使用了很多循环（3），因此这不是一个非常高效的解决方案。 - jasonleonhard
0
我编写了一个LSD基数排序器的实现，用于对整数和浮点数进行排序。它使用位掩码来减少迭代次数。
与Joseph Nields的答案相比，在测试包含1000000个数字和范围为-0x80000000至0x80000000的数组时，速度快了一倍。
与Joseph Nields的答案相比，在测试包含1000000个数字和范围为-0x80000000至0x80000000的数组时，速度快了一倍。
- Aldo
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接