nodejs实现字符串排序(高位优先&低位优先)

字符串排序

网上很多都是c实现的，这里我写一个nodejs实现的

低位优先字符串排序

const testArr = ['abc', 'abd', 'dbc', 'wdx', 'yex', 'nds', 'wed', 'dqs'];

lowFirstSort(testArr);
console.log(testArr)

function lowFirstSort(stringArray: string[]) {
    /**
     * 字符串数组长度
     */
    const arrLength = stringArray.length;
    /**
     * 字符表(a-z)长
     */
    const charLength = 26;
    /**
     * 排序的字符串数组的字符串长度
     */
    const wordLength = stringArray[0].length;
    /**
     * 辅助数组
     */
    const busArr = new Array<string>(arrLength)
    /**
     * 创建键索引计数数组
     */
    const assistenArr = new Array<number>(charLength + 1).fill(0);
    
    // 从低位开始
    for (let i = wordLength - 1; i >=0 ; i--) {
        /**
         * 开始键计数  如：数组第一个元素是'abc'， 元素的最后一个字符是'c'， 则
         * assistenArr数组的索引3的位置加一  ->   assistenArr[3]++
         * [ 0, 0, 3, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0 ]
         * [ 0, 0, a, b, c, d, e, f, g, h, i.... ]
         * 如上就说明有3个a，1个d....
         */
        for (let j = 0; j < arrLength; j++) {
            assistenArr[stringArray[j].charCodeAt(i) - 97 + 1]++
        }
        /**
         * 累计计数   如：[0, 1, 0, 0, 2, 1, 0]  -->  [0, 1, 1, 1, 3, 4, 4]
         * 把键计数转换为索引
         */
        for (let j = 0; j < charLength; j++) {
            assistenArr[j + 1] += assistenArr[j]
        }
        /**
         * 开始排序
         */
        for (let j = 0; j < arrLength; j++) {
            busArr[assistenArr[stringArray[j].charCodeAt(i) - 97]++] = stringArray[j];
        }
        /**
         * 复制回原数组stringArray
         */
        for (let j = 0; j < arrLength; j++) {
            stringArray[j] = busArr[j];
        }
        /**
         * 清空键索引计数数组， 留以下个循环使用
         */
        assistenArr.fill(0);
    }
}

高位优先字符串排序

const testArr2 = ['wdxsexg', 'yex', 'nadsas', 'waaeed', 'dqsf', 'abc', 'abcde', 'abcab'];

highFirstSort(testArr2);
console.log(testArr2)
function highFirstSort(stringArray: string[]) {
    /**
     * 字符串数组长度
     */
    const arrLength = stringArray.length;
    /**
     * 字符表(a-z)长
     */
    const charLength = 26;
    /**
     * 辅助数组
     */
    const busArr = new Array<string>(testArr2.length)
    /**
     * 递归开始
     */
    sort(stringArray, 0, arrLength-1, 0, busArr, charLength);
}
/**
 * 重写的charCodeAt方法
 * @param _string 字符串
 * @param position 位置
 */
function charCodeAtMy(_string: string, position: number) {
    return _string.length > position ? _string.charCodeAt(position) - 97 : -1;
}

function sort(array: string[], low: number, high: number, position: number, busArr: string[], charLength: number){
    if (low >= high) {
        return;
    }
    /**
     * 创建键索引计数数组
     */
    const assistenArr = new Array<number>(charLength + 2).fill(0);
    /**
     * 开始键计数
     * [ 0, 0, 3, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0 ]
     * [ 0, 0, a, b, c, d, e, f, g, h, i.... ]
     * 如上就说明有3个a，1个d....
     */
    for (let i = low; i <= high; i++) {
        assistenArr[charCodeAtMy(array[i], position) + 2]++;
    }
    /**
     * 累计计数   如：[0, 1, 0, 0, 2, 1, 0]  -->  [0, 1, 1, 1, 3, 4, 4]
     * 把键计数转换为索引
     */
    for (let j = 0; j < charLength + 1; j++) {
        assistenArr[j + 1] += assistenArr[j];
    }
    /**
     * 开始排序
     */
    for (let j = low; j <= high; j++) {
        busArr[assistenArr[charCodeAtMy(array[j], position) + 1]++] = array[j];
    }
    /**
     * 复制回原数组stringArray
     */
    for (let j = 0; j <= high-low; j++) {
        array[low + j] = busArr[j];
    }
    /**
     * 递归调用， 如: 'ac' 'ab'这样的高位相同的，在assistenArr数组中的体现就是
     * arr[n+1] - 1 > arr[n]: 这就说明这里存在着相同的字符， 有两个a
     * low + assistenArr[i] < low + assistenArr[i + 1] - 1 
     * 所以还要以第二个字符进行键索引计数排序
     */
    for (let i = 0; i < charLength - 1; i++) {
        sort(array, low + assistenArr[i], low + assistenArr[i + 1] - 1, position + 1, busArr, charLength)
    }
}