江苏龙网

  1. 主页 > 生活百科 > >

TypeScript实现八大排序与搜索算法( 六 )

TypeScript


const array = [12, 6, 3, 4, 1, 7];const sort = new Sort(array);const result = sort.countingSort(array);console.log(result.join());

TypeScript实现八大排序与搜索算法

文章插图
 
桶排序桶排序也是一种分布式排序算法，它将元素分为不同的桶，再使用一个简单的排序算法，例如插入排序，来对每个桶进行排序，最后，它将所有的桶合并为结果数组 。
实现思路首先，我们需要指定需要多个桶来排序各个元素，默认情况，我们会使用5个桶 。桶排序在所有元素平分到各个桶中时的表现最好 。如果元素非常稀疏，则使用更多的桶会更好 。如果元素非常密集，则使用较少的桶会更好 。因此我们为了算法的效率，会让调用者根据实际需求将桶的数量作为参数传进来 。我们将算法分为两个部分：
  • 创建桶，并将桶分布到不同的桶中
  • 对每个桶中的元素执行排序算法并将所有桶合并成排序好后的结果数组
我们先来看看创建桶的思路
  • 声明创建桶函数（createBuckets），接收两个参数：待排序数组（array），桶大小（bucketSize）
  • 计算array中的最大值（maxValue）和最小值（minValue）
  • 计算每个需要的桶数量，公式为：(maxValue - minValue) / bucketSize)+1
  • 声明一个二维数组buckets，用于存放所有桶
  • 根据桶数量，初始化每个桶
  • 遍历array，将每个元素分布到桶中
    • 计算需要将元素放到哪个桶中(bucketIndex)，公式为：(array[i] - minValue) / bucketSize
    • 将元素与放进合适的桶中，即buckets[bucketIndex].push(array[i])
  • 将桶返回
接下来我们来看看对每个桶里的元素进行排序的思路
  • 创建排序桶函数（sortBuckets），接收一个参数: 桶buckets
  • 需要一个辅助数组sortedArray，用于存放排序好的结果数组
  • 遍历sortedArray
    • 如果当前桶内存储的桶buckets[i]不为null，就对其执行插入排序
    • 将排序好的桶buckets[i]解构后放进sortedArray中
  • 最后，返回sortedArray
我们通过一个例子，来讲解上述思路，如下图所示
TypeScript实现八大排序与搜索算法

文章插图
 
实现代码接下来，我们将上述思路转换为代码 。
    // 桶排序    bucketSort(array: number[], bucketSize = 5): T[] | number[] {        if (array.length < 2) {            return array;        }        // 创建桶，对桶进行排序        return this.sortBuckets(<[][]>this.createBuckets(array, bucketSize));    }    /**     * 创建桶     * @param array 待排序数组     * @param bucketSize 桶大小，即每个桶里的元素数量     *     * @return 二维数组类型的桶     */    private createBuckets = (array: number[], bucketSize: number): number[][] => {        // 计算数组最大值与最小值        let minValue = array[0];        let maxValue = array[0];        for (let i = 1; i < array.length; i++) {            if (array[i] < minValue) {                minValue = array[i];            } else if (array[i] > maxValue) {                maxValue = array[i];            }        }        // 计算需要的桶数量，公式为: 数组最大值与最小值的差值与桶大小进行除法运算        const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;        // 用于存放桶的二维数组        const buckets: number[][] = [];        // 计算出桶数量后，初始化每个桶        for (let i = 0; i < bucketCount; i++) {            buckets[i] = [];        }        // 遍历数组，将每个元素分布到桶中        for (let i = 0; i < array.length; i++) {            // 计算需要将元素放到哪个桶中，公式为: 当前遍历到的元素值与数组的最小值的差值与桶大小进行除法运算            const bucketIndex: number = Math.floor((array[i] - minValue) / bucketSize);            // 将元素放进合适的桶中            buckets[bucketIndex].push(array[i]);        }        // 将桶返回        return buckets;    };    // 对每个桶进行排序    private sortBuckets(buckets: T[][]): T[] {        const sortedArray: T[] = [];        for (let i = 0; i < buckets.length; i++) {            if (buckets[i] != null) {                // 调用插入排序                this.insertionSort(buckets[i]);                // 将排序好的桶取出来，放进sortedArray中                sortedArray.push(...buckets[i]);            }        }        return sortedArray;    }


推荐阅读


上一篇：详解DBSCAN聚类

下一篇：面向对象编程OOP的基本概念