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

编写测试代码我们通过一个例子，来测试下上述代码是否都正确执行。
const array = [12, 6, 3, 4, 1, 7];const sort = new Sort(array);const result = sort.quickSort();console.log(result.join());

文章插图

计数排序计数排序是一个分布式排序，它是用来排序整数的优秀算法。分布式排序使用已组织好的辅助数据结构，然后进行合并，得到排好序的数组。计数排序使用一个用来存储每个元素在原始数组中出现次数的临时数组。在所有元素都计数完成后，临时数组已排好序并可迭代以构建排序后的结果数组。
实现思路

找到要排序数组的最大值
以上一步找到的最大值+1为长度创建一个计数数组
遍历要排序的数组，以当前遍历的元素为索引，寻找计数数组中对应的位置将其初始化为0，如果此处位置有相同元素的话就自增
遍历计数数组，判断当前遍历到的元素是否大于0，如果大于0就取当前遍历到的索引，替换待排序数组中的元素

接下来我们通过一个例子来讲解下上述过程，如下图所示：

文章插图

实现代码接下来我们将上述思路转换为代码

    countingSort(array: number[]): number[] {        // 待排序数组为空或只有一个元素则不用排序        if (array.length < 2) {            return array;        }        // 找到待排序数组中的最大值        const maxValue = this.findMaxValue(array);        // 创建计数数组，数组长度为待排序数组的最大值+1        const counts = new Array(maxValue + 1);        // 遍历待排序数组，为计数数组赋值        array.forEach((element) => {            // 以当前遍历到的元素值为索引将对应位置元素值初始化为0            if (!counts[element]) {                counts[element] = 0;            }            // 当前位置的值进行自增，顺便应对数组中有重复值的情况，有重复值时当前位置的值必定大于1            counts[element]++;        });        // 声明一个变量用于数组最终排序        let sortedIndex = 0;        // 遍历计数数组，根据计数数组的元素位置对待排序数组进行排序        counts.forEach((count, i) => {            // 如果当前遍历到的元素值大于0，则执行替换操作进行排序            while (count > 0) {                // 将当前元素索引赋值给array的sortedIndex号元素，随后sortedIndex自增                array[sortedIndex++] = i;                // 当前元素值自减，如果其值大于1，证明此处有重复元素，那么我们就继续执行while循环                count--;            }        });        // 最后，排序完成，返回排序好的数组        return array;    }

编写测试代码我们将上述图中的例子放进代码中执行，看看我们写的函数是否正确执行。