帮我写一个JS的计数排序算法,且支持负数和小数。
时间: 2023-02-08 15:30:25 浏览: 104
JavaScript 计数排序算法:
```javascript
function countingSort(arr) {
let min = Math.min(...arr);
let max = Math.max(...arr);
let range = max - min + 1;
let count = new Array(range).fill(0);
let output = new Array(arr.length);
for (let i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
for (let i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
for (let i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
return output;
}
```
注意:
1. 计数排序的时间复杂度是O(n),但是空间复杂度是O(n+k)
2. 数组中的数字必须是整数
实现支持负数和小数,可以考虑将数组中的数字先乘以一个负数和小数,然后使用计数排序,最后再将数组中的数字除以这个负数和小数。
例如:
```javascript
const arr = [-5.5, -3.2, 0, 2.1, 5.5, 8.9];
const factor = 100; // 乘以 100,变成整数
const sortedArr = countingSort(arr.map(num => num * factor));
const result = sortedArr.map(num => num / factor);
console.log(result);
```
这样就可以支持负数和小数了。
阅读全文