江苏龙网

  1. 主页 > 生活百科 > >

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

TypeScript

编写测试代码我们将上述图中的例子放进代码中看其是否能正确执行 。
const array = [12, 5, 6, 7, 8, 9, 11, 3, 4, 19];const sort = new Sort(array);const result = sort.bucketSort(array);console.log(result.join());

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

文章插图
 
基数排序基数排序也是一个分布式排序算法，它根据数字的有效位或基数将整数分布到桶中 。比如，十进制数，使用的基数是10.因此，算法将会使用10个桶用来分布元素并且首先基于各位数字进行排序，然后基于十位数字，然后基于百位数字，以此类推 。
实现思路基数排序也是用来排序整数，因此我们从最后一位开始排序所有的数 。首先，只会基于最后一位有效位对数字进行排序，在下次迭代时，我们会基于第二个有效位进行排序（十位数字），然后是第三个有效位（百位数字），以此类推 。我们继续这个过程直到没有待排序的有效位，因此我们需要知道数组中的最小值和最大值 。实现基数排序我们需要一个辅助函数（countingSortForRadix），即根据有效位对数组进行排序 。接下来，我们先来看下基数排序主函数的实现思路 。
  • 创建基数排序函数（radixSort），接受2个参数：待排序数组array，基数radixBash
  • 首先，获取array的最大值maxValue和最小值minValue
  • 声明一个辅助变量significantDigit，用于存储当前有效数字，默认从最后一位有效数字，即1
  • 计算有效位，公式为：(maxValue - minValue) / significantDigit，计算出的值如果大于等于1执行下述逻辑：
    • 以当前有效位作为参数调用singnificantDigit函数对数组进行排序
    • 当前有效数字*基数，继续执行上述过程
  • 最后，执行完成返回排序好多的数组
接下来，我们来看下基于有效位进行排序的函数实现思路 。
  • 创建countingSortForRadix函数，接受4个参数：待排序数组array，基数radixBase、有效位significantDigit、数组的最小值minValue
  • 声明桶索引bucketsIndex以及桶buckets以及辅助数组aux
  • 通过radixBase来初始化桶，默认初始化为0
  • 遍历array，基于有效位计算桶索引执行计数排序
    • 计算桶索引，公式为：((array[i] - minValue) / significantDigt) % radixBase
    • 根据桶索引，执行计数操作，即buckets[bucketsIndex++]
  • 计算累积结果得到正确的计数值，从1开始遍历到radixBase位置 。
    • buckets[i]等于buckets[i] 加上buckrts[i - 1]的值
  • 计数完成，遍历array将值移回原始数组中，用aux辅助数组来存储
    • 计算当前元素的桶索引bucketsIndex，公式为：((array[i] - minValue) / significantDigit) % radixBase
    • 对当前桶索引内的元素执行自检操作，得到其在数组中的正确位置index
    • 计算出索引后，在aux中的对应位置存储当前遍历到的元素
  • 最后排序完成，返回axu 。
我们通过一个例子来描述上述过程，如下图所示 。
TypeScript实现八大排序与搜索算法

文章插图
 
实现代码接下来，我们将上述思路转换为代码.
    /**     * 基数排序     * @param array 待排序数组     * @param radixBase 10进制排序，基数为10     */    radixSort(array: number[], radixBase = 10): number[] {        if (array.length < 2) {            return array;        }        // 获取数组的最小值和最大值        const minValue = this.findMinValue(array);        const maxValue = this.findMaxValue(array);        // 当前有效数字,默认会从最后一位有效数字开始排序        let significantDigit = 1;        /**         * 计算有效位         * 最大值和最小值的差与有效数字进行除法运算，其值大于等于1就代表还有待排序的有效位         */        while ((maxValue - minValue) / significantDigit >= 1) {            // 以当前有效位为参数对数组进行排序            array = this.countingSortForRadix(array, radixBase, significantDigit, minValue);            // 当前有效数字乘以基数，继续执行while循环进行基数排序            significantDigit *= radixBase;        }        return array;    }    /**     * 基于有效位进行排序     * @param array 待排序数组     * @param radixBase 基数     * @param significantDigit 有效位     * @param minValue 待排序数组的最小值     */    private countingSortForRadix = (array: number[], radixBase: number, significantDigit: number, minValue: number) => {        // 声明桶索引以及桶        let bucketsIndex;        const buckets = [];        // 辅助数组，用于计数完成的值移动会原数组        const aux = [];        // 通过基数来初始化桶        for (let i = 0; i < radixBase; i++) {            buckets[i] = 0;        }        // 遍历待排序数组，基于有效位计算桶索引执行计数排序        for (let i = 0; i < array.length; i++) {            // 计算桶索引            bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase);            // 执行计数操作            buckets[bucketsIndex]++;        }        // 计算累积结果得到正确的计数值        for (let i = 1; i < radixBase; i++) {            buckets[i] = buckets[i] + buckets[i - 1];        }        // 计数完成，将值移回原始数组中,用aux辅助数组来存储        for (let i = array.length - 1; i >= 0; i--) {            // 计算当前元素的桶索引            bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase);            // 对当前桶索引内的元素执行自减操作,得到其在数组中的正确的位置            const index = --buckets[bucketsIndex];            // 计算出索引后，在aux中的对应位置存储当前遍历到的元素            aux[index] = array[i];        }        console.log(aux);        return aux;    };


推荐阅读


上一篇：详解DBSCAN聚类

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