Hark的数据结构与算法练习之桶排序
算法说明
桶排序的逻辑其实特别好理解,它是一种纯粹的分而治之的排序方法。
举个例子简单说一下大家就知道精髓了。
假如对11,4,2,13,22,24,20 进行排序。
那么,我们将4和2放在一起,将11,13放在一起,将22,24,20放在一起。然后将这三部分分别排序(可以根据实现情况任意选择排序方式,我的代码中使用的是快排),将子数组排序后,再顺序输出就是最终排序结果了(大概应该明白了,我们是根据数字大小进行分组的,故而顺序输出即可)
怎么样,很简单吧。
具体实现大家看代码就行,我实现的其实有许多可以优化的地方呐。
代码
使用的是java
另外,以下代码中的第44行代码 QuickSort.QuickSortMethod(arrayBucket[i]);
调用的是 这里 的方法
import java.util.Arrays;
/*
* 桶排序
*/
public class BucketSort {
public static void main(String[] args) {
int[] arrayData = https://www.it610.com/article/{ 22, 33, 57, 55, 58, 77, 44, 65, 42 };
BucketSortMethod(arrayData, 10);
for (int integer : arrayData) {
System.out.print(integer);
System.out.print(" ");
}
} /*
* buckenCount - 桶的数量
*/
public static void BucketSortMethod(int[] arrayData, int buckenCount) {
int[][] arrayBucket = new int[buckenCount][arrayData.length];
// 桶容器for (int i = 0;
i < arrayBucket.length;
i++) {
for (int j = 0;
j < arrayBucket[i].length;
j++) {
arrayBucket[i][j] = -1;
}
}int[] arrayLength = new int[arrayData.length];
int num;
// 将数据分桶
for (int i = 0;
i < arrayData.length;
i++) {
// 根据结果来确定是存在在哪个桶中
num = arrayData[i] / buckenCount;
num = 10 - num;
// 这是为了降序// System.out.println(num);
arrayBucket[num][arrayLength[num]] = arrayData[i];
arrayLength[num]++;
}// 将桶内数据进行排序,这里使用的是快排
for (int i = 0;
i < arrayBucket.length;
i++) {
QuickSort.QuickSortMethod(arrayBucket[i]);
}int resultIndex = 0;
// 对于桶内的数据进行输出
for (int i = 0;
i < arrayBucket.length - 1;
i++) {
if (arrayLength[i] > 0) {
for (int j = 0;
j < arrayBucket[i].length;
j++) {
if (arrayBucket[i][j] != -1) {
arrayData[resultIndex++] = arrayBucket[i][j];
}
}
}
}
}
}
结果
77 65 58 57 55 44 42 33 22
时间复杂度:
时间复杂度主要还是取决于子数组的排序时间复杂度。 子数组的排序复杂度平均是O(n*log2n),然后分桶这块的的空间复杂度是O(n)
即O(n+n*log2n)
空间复杂度:
假设桶的数量是b,待排序数组的长度是n。
那么O(b*n)=O(n)
稳定性:稳定性主要取决于子数组中的排序(即44行调用的快排),子数组中使用的排序方法是稳定的,那么桶排序就是稳定的。
参考
【Hark的数据结构与算法练习之桶排序】http://flyingcat2013.blog.51cto.com/7061638/1286645
推荐阅读
- 热闹中的孤独
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 放屁有这三个特征的,请注意啦!这说明你的身体毒素太多
- 一个人的旅行,三亚
- 布丽吉特,人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事,我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量