排序算法（十一）桶排序

  桶排序（Bucket sort）是计数排序改进版，同样属于非比较排序，该算法的基本思想为将数组分到有限数量的桶子里，再在各个桶里面分别排序，最后将所有桶里的数据依次取出，则为有序序列。

图片演示

桶排序

代码实现（TypeScript实现）

/**
 * 直接插入排序
 * @param arr 源数组
 */
function insertionSort(arr: Array<number>): Array<number> {
    let cur: number;    // 记录当前预转换位置的元素
    let j: number;  // 记录与预转换位置元素做比较的元素的下标，该值每循环一次改变一次

    for (let i = 0, len = arr.length; i < len; i++) {
        cur = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > cur) {
            arr[j + 1] = arr[j];  // 移动元素
            j--;
        }
        arr[j + 1] = cur;   // 预转换的元素插入对应的位置
    }

    return arr;
}

/**
 * 桶排序
 * @param arr 源数组
 * @param bucketSize 每个桶的容量（默认 5）
 */
function bucketSort(arr: Array<number>, bucketSize: number = 5) {
    // 求范围
    let min = arr[0];
    let max = min;
    // 定义计数数组
    arr.forEach(element => {
        if (element < min) { min = element; }
        if (element > max) { max = element; }
    });
    // 初始化桶
    let bucketCount = (((max - min) / bucketSize) | 0) + 1;
    let buckets: number[][] = new Array<Array<number>>(bucketCount);
    for (let i = 0, len = buckets.length; i < len; i++) {
        buckets[i] = [];
    }
    // 数据印映射到桶中
    arr.forEach(element => {
        buckets[((element - min) / bucketSize) | 0].push(element)
    })
    // 对各个桶排序
    arr.length = 0;
    buckets.forEach(bucket => {
        insertionSort(bucket);
        bucket.forEach(element => {
            arr.push(element);
        });
    });
    return arr;
}


let originData: Array<number> = [5, 6, 7, 9, 10, 15, 13, 19, 5, 9, 13, 10];
console.log(bucketSort(originData, 2));

分析

1. 算法的稳定性取决于对桶中元素排序时选择的排序算法。
2. 桶排序与计数排序类似，计数排序只适用于元素值较为集中的情况。
3. 桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。