O(n)的排序算法-(计数排序、桶排序及其js实现)

2019-08-28

总结一下，常见时间复杂度为O(n)的排序算法，以及给出js实现
非比较排序，比较排序的时间复杂度下界为O(n*logn)

计数排序(Counting sort)

适用范围：待排数组arr[N]，元素处在某一范围[min,max]
核心：假设元素为整数，空间换时间，需要空间大小为O(max-min)的空间，来存储所有元素出现的次数
- 如果元素个数多，但是数值范围较窄时，计数排序是很节省空间的
步骤：
- 遍历arr[N]，使用计数数组count[max-min]，对每个元素进行计数
- 遍历count[]，还原arr[N]，结束
补充：数组index肯定≥0的，待排元素的min不一定为0，需要引入一个offset来修正数值在计数数组count[]中的位置
时间复杂度为O(n)，更准确的将是O(k+n),k表示输入数组元素范围为[0,k]，空间复杂度O(k+n)

function countSort(nums) {
    if (nums.length <= 1) return;

    let max = nums[0];
    let min = nums[0];
    for (let i = 1; i < nums.length; i++) {
        max = nums[i] <= max ? max : nums[i];
        min = nums[i] >= min ? min : nums[i];
    }

    // 计算偏移量
    let offset = 0 - min;

    // 初始化计数数组
    let count = new Array(max - min + 1);
    for (let i = 0; i < count.length; i++) count[i] = 0;

    // 计数：各个元素出现的次数
    for (let i = 0; i < nums.length; i++) {
        count[nums[i] + offset]++;
    }

    // 还原排序数组
    let index = 0;
    for (let i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            nums[index] = i - offset;
            index++;
            count[i]--;
        }
    }
}

桶排序(Bucket sort)

适用范围：待排数组A[N]，元素均匀分布在某一范围[min,max]
核心：假设元素是均匀分布的
- 平均时间复杂度为O(n)，最坏的情况下所有数据都在一个桶内，其时间复杂度取决于桶内元素自排序的算法
- 即使数据不服从均匀分布，只要输入数据满足下列性质：所有桶的大小的平方与总的元素呈线性关系，桶排依然能在线性时间内完成
需要的辅助空间：
- 桶空间B
- 桶内的元素链表空间
步骤：
- 遍历A[N]，元素A[i]，放入对应的桶X
- A[i]放入桶X，如果桶X已有若干元素，一般使用稳定的插入排序，将A[i]放到桶内的合适位置

补充：

桶内的元素一直是有序的;

桶的个数设定

桶排序中桶的设定非常重要，需要制定合理的getBucketIndex算法，使得元素能尽量均匀的放入不同的桶内；
最糟糕，无非所有元素都在一个桶内，时间复杂度就是桶内排序算法时间复杂度
区间划分越细，桶的数量越多，理论上分到每个桶的元素越少，桶内的排序越简单，时间复杂度越接近线性
极端情况下，每个桶内就一个元素，不再需要排序，因为他们都是相同的元素，那桶排序跟计数排序差不多了

稳定，时间复杂度O(n)

// 链表元素，用于桶内的元素排序
function ListNode(val) {
    this.val = val;
    this.next = null;
}

// nums待排数组，内有浮点数，均匀分布在[0,10]的范围
// len：桶的个数
function bucketSort(nums, len) {
    console.log(nums, len);
    if (nums.length <= 1) return;

    let bucket = [];
    for (let i = 0; i < len; i++) {
        bucket[i] = new ListNode(0);
    }

    // 桶内链表排序
    for (const num of nums) {
        // 获取应该插入到哪个桶内
        let idx = getBucketIndex(num);
        let insertNode = new ListNode(num);
        if (bucket[idx].next == null) {
            // 无元素，插入元素
            bucket[idx].next = insertNode;
        } else {
            // 有元素，插入到合适的位置
            let pre = bucket[idx];
            let cur = pre.next;
            while (cur != null && cur.val <= num) {
                pre = cur;
                cur = cur.next;
            }

            insertNode.next = cur;
            pre.next = insertNode;
        }
    }

    // 桶内元素输出
    let index = 0;
    for (let i = 0; i < len; i++) {
        let node = bucket[i].next;
        if (node == null) continue;
        while (node != null) {
            nums[index] = node.val;
            index++;
            node = node.next;
        }
    }
}


// 计算放入哪个桶中
// 当前例子是，浮点数转化为整数，作为桶的索引值，实际开发要根据场景具体设计
function getBucketIndex(num) {
    return parseInt(num);
}

let array = [2.18, 0.18, 0.16, 2.12, 3.66, 7.88, 7.99, 8.12, 9.66, 5.1, 4.12, 5.28];
bucketSort(array, 11);
console.log(array);