使用Java实现桶排序算法

2023-12-13 16:34:36

文章目录

今天来看看桶排序算法:

桶排序算法

(1)基本思想:把数组 arr 划分为 n 个大小相同子区间(桶),每个子区间各自排序,最后合并 。计数排序是桶排序的一种特殊情况,可以把计数排序当成每个桶里只有一个元素的情况。

(2)排序过程

  • 找出待排序数组中的最大值 max、最小值 min
  • 我们使用 动态数组 ArrayList 作为桶,桶里放的元素也用 ArrayList 存储。桶的数量为(maxmin)/arr.length+1
  • 遍历数组 arr,计算每个元素 arr[i] 放的桶
  • 每个桶各自排序

示例代码:

/**
 * 桶排序
 *
 * @param data 待排序数组
 */
public static void bucketSort(int data[]){
    int n = data.length;
    int bask[][] = new int[10][n];
    int index[] = new int[10];
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        max = max > (Integer.toString(data[i]).length()) ? max : (Integer.toString(data[i]).length());
    }
    String str;
    for (int i = max - 1; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            str = "";
            if (Integer.toString(data[j]).length() < max) {
                for (int k = 0; k < max - Integer.toString(data[j]).length(); k++)
                    str += "0";
            }
            str += Integer.toString(data[j]);
            bask[str.charAt(i) - '0'][index[str.charAt(i) - '0']++] = data[j];
        }
        int pos = 0;
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k < index[j]; k++) {
                data[pos++] = bask[j][k];
            }
        }
        for (int x = 0; x < 10; x++) index[x] = 0;
    }
}

文章来源:https://blog.csdn.net/weixin_44797327/article/details/134905681
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。