桶排序python
时间: 2023-11-16 17:02:06 浏览: 38
桶排序是一种排序算法,它将元素分为不同的桶,然后对每个桶中的元素进行排序,最后将所有桶中的元素按顺序合并起来。Python实现桶排序的方法如下:
```python
def bucket_sort(arr):
# 创建桶
buckets = [0] * ((max(arr) - min(arr)) // len(arr) + 1)
# 将元素放入桶中
for i in arr:
buckets[(i - min(arr)) // len(arr)] += 1
# 将桶中元素排序
res = []
for i in range(len(buckets)):
if buckets[i] != 0:
res += [i * len(arr) + j for j in range(buckets[i])]
return res
```
其中,arr为待排序的列表,buckets为桶,res为排序后的结果。这个实现方法的时间复杂度为O(n),空间复杂度为O(n)。
相关问题
java桶排序python
以下是Java和Python实现桶排序的例子:
1. Java实现桶排序
```java
import java.util.Arrays;
public class BucketSort {
public static void bucketSort(int[] array, int bucketSize) {
if (array.length == 0) {
return;
}
int minValue = array[0];
int maxValue = array[0];
for (int value : array) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
int bucketCount = (maxValue - minValue) / bucketSize + 1;
int[][] buckets = new int[bucketCount][0];
for (int value : array) {
int bucketIndex = (value - minValue) / bucketSize;
buckets[bucketIndex] = grow(buckets[bucketIndex], value);
}
int currentIndex = 0;
for (int[] bucket : buckets) {
InsertionSort.insertionSort(bucket);
for (int value : bucket) {
array[currentIndex++] = value;
}
}
}
private static int[] grow(int[] array, int value) {
array = Arrays.copyOf(array, array.length + 1);
array[array.length - 1] = value;
return array;
}
public static void main(String[] args) {
int[] array = {29, 25, 3, 49, 9, 37, 21, 43};
bucketSort(array, 10);
System.out.println("Sorted array: " + Arrays.toString(array));
}
}
class InsertionSort {
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int current = array[i];
int j = i - 1;
while (j >= 0 && array[j] > current) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = current;
}
}
}
```
2. Python实现桶排序
```python
def bucket_sort(array, bucketSize):
if len(array) == 0:
return array
minValue = array[0]
maxValue = array[0]
for value in array:
if value < minValue:
minValue = value
elif value > maxValue:
maxValue = value
bucketCount = (maxValue - minValue) // bucketSize + 1
buckets = [[] for _ in range(bucketCount)]
for value in array:
bucketIndex = (value - minValue) // bucketSize
buckets[bucketIndex].append(value)
array.clear()
for bucket in buckets:
bucket.sort()
array.extend(bucket)
return array
array = [29, 25, 3, 49, 9, 37, 21, 43]
bucket_sort(array, 10)
print("Sorted array:", array)
```
桶排序的python实现
可以回答这个问题。桶排序是一种线性排序算法,它的基本思想是将待排序的数据分到有限数量的桶子里,然后对每个桶子里的数据进行排序,最后将所有桶子中的数据依次取出,即可得到有序序列。以下是桶排序的 Python 实现代码:
def bucket_sort(arr):
max_num = max(arr)
bucket = [0] * (max_num + 1)
for i in arr:
bucket[i] += 1
res = []
for j in range(len(bucket)):
if bucket[j] != 0:
res += [j] * bucket[j]
return res
arr = [3, 5, 1, 7, 9, 2, 4, 6, 8, 0]
print(bucket_sort(arr)) # 输出 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]