[9, 8, 1, 3,8] js桶排序
时间: 2023-05-22 17:05:04 浏览: 43
这是一个非常好的问题,桶排序是一种非常高效的排序算法。下面是一个简单的 JavaScript 桶排序算法:
function bucketSort(arr) {
let len = arr.length,
buckets = [],
result = [];
for(let i = 0; i < len; i++) {
buckets[arr[i]] = buckets[arr[i]] || 0;
buckets[arr[i]]++;
}
for(let i = 0; i < buckets.length; i++) {
if(buckets[i]) {
for(let j = 0; j < buckets[i]; j++) {
result.push(i);
}
}
}
return result;
}
console.log(bucketSort([9, 8, 1, 3, 8]));
希望这能够帮助您!
相关问题
js 桶排序
桶排序是一种常见的排序算法,它将数据分成若干个桶,然后对每个桶中的数据进行排序,最后将所有桶中的数据合并起来。
下面是 JavaScript 中桶排序的代码实现:
```javascript
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
// 找出数组中的最大值和最小值
var minValue = arr[0];
var maxValue = arr[0];
for (var i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i];
} else if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
// 计算桶的数量
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var buckets = new Array(bucketCount);
for (var j = 0; j < buckets.length; j++) {
buckets[j] = [];
}
// 将数据分配到各个桶中
for (var k = 0; k < arr.length; k++) {
var bucketIndex = Math.floor((arr[k] - minValue) / bucketSize);
buckets[bucketIndex].push(arr[k]);
}
// 对每个桶中的数据进行排序
arr.length = 0;
for (var m = 0; m < buckets.length; m++) {
insertionSort(buckets[m]); // 可以使用其他排序算法,例如插入排序
for (var n = 0; n < buckets[m].length; n++) {
arr.push(buckets[m][n]);
}
}
return arr;
}
// 插入排序
function insertionSort(arr) {
for (var i = 1; i < arr.length; i++) {
var temp = arr[i];
var j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
```
使用方法:
```javascript
var arr = [5, 3, 8, 4, 2];
var sortedArr = bucketSort(arr, 3);
console.log(sortedArr); // [2, 3, 4, 5, 8]
```
其中,`arr` 是待排序的数组,`bucketSize` 是桶的大小。在上面的代码中,我们使用了插入排序对每个桶中的数据进行排序。如果你想使用其他的排序算法,只需要将 `insertionSort` 函数替换成其他的排序函数即可。
桶排序
桶排序(Bucket Sort)是一种线性排序算法,它的时间复杂度为O(n+k),其中n为待排序元素的个数,k为桶的数量。桶排序的基本思想是将待排序的元素分配到不同的桶中,然后对每个桶中的元素进行排序,最后将所有桶中的元素按照顺序依次排列起来。
桶排序的具体步骤如下:
1. 创建k个桶,并确定每个桶的范围区间。
2. 将待排序的元素分配到不同的桶中,可以使用Hash函数或者映射函数来确定桶的编号。
3. 对每个桶中的元素进行排序,可以使用插入排序等简单排序算法。
4. 将所有桶中的元素按照顺序依次排列起来,得到排序后的数组。
下面是桶排序的示例代码,假设我们要对一个整型数组进行从小到大的排序:
```csharp
private static void BucketSort(int[] arr, int bucketSize)
{
if (arr == null || arr.Length < 2)
{
return;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] < minValue)
{
minValue = arr[i];
}
if (arr[i] > maxValue)
{
maxValue = arr[i];
}
}
int bucketCount = (maxValue - minValue) / bucketSize + 1;
List<int>[] buckets = new List<int>[bucketCount];
for (int i = 0; i < bucketCount; i++)
{
buckets[i] = new List<int>();
}
for (int i = 0; i < arr.Length; i++)
{
int bucketIndex = (arr[i] - minValue) / bucketSize;
buckets[bucketIndex].Add(arr[i]);
}
int index = 0;
for (int i = 0; i < bucketCount; i++)
{
int[] bucketArr = buckets[i].ToArray();
InsertionSort(bucketArr);
for (int j = 0; j < bucketArr.Length; j++)
{
arr[index++] = bucketArr[j];
}
}
}
private static void InsertionSort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
```
在上面的代码中,`BucketSort`方法首先通过遍历数组找到最小值和最大值,然后根据桶的大小确定桶的数量,创建桶的数组,并将待排序的元素分配到不同的桶中。接着对每个桶中的元素进行排序,这里使用了插入排序算法;最后将所有桶中的元素按照顺序依次排列起来,得到排序后的数组。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)