HJ14 字符串排序

题目描述

示例

代码

代码1 使用数组的sort方法排序（默认即为字典序）

/*
字典序排序字符串 第一种方法
直接使用 数组的api，sort（默认即为字典排序）
*/


let readline = require('readline')
let rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

let count = 0 // 第几次输入
let firstNum = -1 // 总共输入几个值，第一次输入的时候记录

let tempArr = [] // 记录输入的字符串集合，先保存在这里，好排序

rl.on('line', line=>{
    count++
    
    if( count === 1 ){
        firstNum = +line // 记录总共输入几个值
    }else {
        tempArr.push( line ) // 记录每次输入的字符串
        
        if( tempArr.length === firstNum ){ // 当输入更好等于个数的时候，开始排序，计算结果
            tempArr.sort() // 使用数组的api，默认即为字典序
            
            tempArr.forEach(item=>{
                console.log( item ) // 输出结果
            })
            
            // 关闭输入流
            rl.close()
        }
    }
})

代码2 自己写比较函数，按字典序一个一个字母比较

/*
字典序排序字符串 第二种方法
自己实现一个比较器，按照字典序排序
*/

let readline = require('readline')
let rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

let count = 0 // 第几次输入
let firstNum = -1 // 总共输入几个值，第一次输入的时候记录

let tempArr = [] // 记录输入的字符串集合，先保存在这里，好排序

rl.on('line', line=>{
    count++
    
    if( count === 1 ){
        firstNum = +line // 记录总共输入几个值
    }else {
        tempArr.push( line ) // 记录每次输入的字符串
        
        if( tempArr.length === firstNum ){ // 当输入更好等于个数的时候，开始排序，计算结果
            
            // 字典序排序
            let newArr = dicQuickSort(tempArr)
            
            // 打印结果
            for( let item of newArr ){
                console.log( item )
            }
            
            
            // 关闭输入流
            rl.close()
        }
    }
})

/*
字典序排序
使用快排的思想
*/
function dicQuickSort(arr){
    
    // 出口
    if( arr.length <= 1 ) return arr
    
    let pivotIndex = Math.floor( arr.length / 2 ) // 基准索引
    let pivot = arr.splice( pivotIndex, 1 )[0] // 把基准拿出来
    
    let left = [] // 保存比自己小的
    let right = [] // 保存比自己大的
    
    // 开始比较
    for( let i = 0; i < arr.length; i++ ){
        if( compare(arr[i], pivot) ){ // 如果比基准大
            right.push( arr[i] )
        }else { // 如果比基准小，或者相等
            left.push( arr[i] )
        }
    }
    
    return dicQuickSort(left).concat( pivot, dicQuickSort(right) )
    
    
    
    /*
        比较字典序
        if 
            str1 > str2 return true
        else 
            str1 <= str2 return false
    */ 
    function compare(str1, str2){
        let i = 0 // 初始索引为 0
        
        while( i < str1.length && i < str2.length ){
            if( str1[i]!== str2[i] ){ // 如果两个值不相等
                return str1[i] > str2[i]
            }else { // 如果两个值相等，比较下一个
                i++
            }
        }
        
        // 如果比较完了，还没有返回值，两种可能
        if( str1.length === str2.length ){ // 两个字符串相等
            return false // 相等的时候，返回false
        }else { // 两个字符串不相等
            return str1.length > str2.length ? true : false
        }
    }
}

题目来源

HJ14 字符串排序