排序算法 下

以下被称为分布式排序的算法，原始数组中的数据会分发到多个中间结构（桶），再合起来放回原始数组。最著名的分布式算法有计数排序、桶排序和基数排序，这三种算法非常相似。

计数排序

计数排序是一种用来排序整数的优秀算法，时间复杂度为O(n + k)，其中k是临时计数数组的大小，但是，他需要更多的内存来存放临时变量。

• 先创建一个排序数据中最大值 + 1创建一个数组(关于这部分我刚开始也不是很明白，js的数组不是动态的吗!何必多此一举去找排序数据的最大值，然后创建一个数组呢???后来想了一下数组的扩容是不是要数据迁移，那样的确不如提前创建大一点，然后找了一下资料: 探究JS V8引擎下的“数组”底层实现)，感兴趣的可以瞧一瞧。
• 然后开始计数，其实就是以下标代表数据，然后以值作为数据出现的次数(分布式中的第一步)
• 循环计数的数组，然后将其回归到原数组上(分布式中的第二步)

export function sortArray(arr: Array<number>) {
    
    if (arr.length < 2){
        return;
    }
    
    let len = findMaxNumber(arr) + 1;
    let countArr = new Array(len).fill(0);

    for (let i = 0; i < arr.length; i++) {
        countArr[arr[i]]++;
    }

    for (let i = 0,index = 0; i < countArr.length; i++) {

        for (let j = 0; j < countArr[i]; j++) {
            arr[index++] = i;
        }
    }
}

/**
 * 找最大数
 * @param arr
 */
function findMaxNumber(arr: Array<number>):number {
    let max:number = 0;
    
    for (let i = 0; i < arr.length; i++) {
        if(arr[i] > max){
            max = arr[i];
        }
    }
    return max;
}


let arr = [54,8,45,7, 1,2,45,9,8,452,35,754,127,6,21,124,454]
sortArray(arr)

// @ts-ignore
console.log(arr)

可以看出这种排序很适合那种有多个重复数据的整数数组，但是数据中有一个特别大的时候，计数数组将会占用很大的内存

还有这里创建的数组是 最大值 + 1，因为数组的下标是0开始的，所以 +1确保最大值也能加入数据

桶排序

桶排序也称之为箱排序，也是分布式排序算法中的一种，它将元素分为不同的桶(较小的数组)，然后使用一个简单的排序算法排序(比如说插入排序)，然后合并数组为结果

对于桶排序算法，我们需要指定需要多少个桶来排序各个元素，默认情况下，我们会使用5个桶(这里我认为是每个桶的容量为5，而且看这个作者命名bucketSize，也觉得就是桶容量，不过确定了一个桶的容量，自然就确定了桶的个数，后面我还是以桶容量来说明该参数)。桶排序在所有元素平分到各个桶时的表现最好。如果元素非常稀疏，则使用更多的桶会更好。如果元素非常密集，则使用较少的桶会比较好，因此我们允许bucketSize以参数的形式传递

• 第一步: 创建桶

  创建桶看似很简单，实际上还是有点难度的，需要做到几点

  • 算出桶的个数: Math.floor((最大值 - 最小值 ) / 单个桶的容量) + 1
  • 然后创建一个桶的个数对应大小的数组，内部填充[]，注意这里不能使用fill填充，fill填充的数组是同一个引用，所以会导致失败(这里创建了一个二维数组)
  • 将排序元素塞到对应的桶里去: (当前值 - 最小值) / 单个桶的容量，其实这个塞入的过程就已经对桶内数据进行了一次粗略排序

• 第二步: 对桶排序

  传回的是一个二维数组，桶是有序的(0号桶的内容会都小于1号桶的内容)

  使用插入排序对桶内数据排序

  组合为新的数组返回

import {sortArray as insertSort} from "./InsertSort"

export function sortArray(arr: Array<number>, bucketSize: number = 5) {

    if (arr.length < 2) {
        return arr;
    }

    // 创建桶
    let buckets = createBuckets(arr, bucketSize);
    // 桶排序并返回数组
    return sortBuckets(buckets);
}


/**
 * 创建桶
 * @param arr
 * @param bucketSize  单个桶的容量
 */
function createBuckets(arr: Array<number>, bucketSize: number):any[][] {
    let minNum = arr[0];
    let maxNum = arr[0];

    // 循环查找最大值最小值
    for (let i = 1; i < arr.length; i++) {

        if (maxNum < arr[i]) {
            maxNum = arr[i];
        } else if (arr[i] < minNum) {
            minNum = arr[i];
        }

    }

    // 计算桶数
    const bucketCount = Math.floor((maxNum - minNum) / bucketSize) + 1;
    // 创建并初始化装桶的数组,这里就是一个二元数组了
    const buckets = [];
    
    //这个for循环不要使用fill替换
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = [];
    }

    for (let i = 0; i < arr.length; i++) {
        // 计算下标的过程其实是对数据进行了一次简单的排序,然后桶就会呈现出有序性
        const index = Math.floor((arr[i] - minNum) / bucketSize)
        buckets[index].push(arr[i]);
    }

    return buckets;
}

/**
 * 对桶进行排序
 * @param buckets
 */
function sortBuckets(buckets: any[][]) {
    let result = [];
    for (let i = 0; i < buckets.length; i++) {
        let element = buckets[i];

        if(element !== null){
            insertSort(element)
            result.push(...element);
        }
    }

    return result;
}

let arr = [54,8,45,7, 1,2,45,9,8,452,35,754,127,6,21,124,454]
let sortArr = sortArray(arr)

// @ts-ignore
console.log(sortArr)

还是想强调一下，填充桶数组的时候不能使用'fill'