在go语言中实现高位优先字符串排序算法示例代码

Go  /  管理员 发布于 2年前   351

本文是在go语言中实现高位优先字符串排序算法，如果你想要其他语言的实现可以自行搜索，或者按同样的思路编码就ok了。

字符串常见的排序算法有两种，分别是低位优先（LSD）和高位优先（MSD），低位优先从右向左检查字符，高位优先从左向右检查字符。

低位优先字符串排序要求待排序的字符串长度一致，然而很多时候字符串长度并不一致，低位优先排序并不适用，此时就要用到高位优先排序或者三向字符串快排。

高位优先字符串排序算法代码示例：

var MAX_R int    //最大字母数字
var aux []string //结果数组

//高位优先字符串排序算法
func sortMSD(a []string, lo int, hi int, d int) []string {
    //根据第d个字母字符用键索引排序(从前面)
    count := map[int][]string{}
    
    for i := lo; i <= hi; i++ {
        temp := 0
        
        //兼容字符长度不一样的
        if len(a[i]) > d { 
            temp = cast.ToInt(a[i][d] + 1)
            count[temp] = append(count[temp], a[i])
        } else {
            temp = 0
            count[temp] = append(count[temp], a[i])
        }
        
        if temp > MAX_R {
            MAX_R = temp
        }
    }
    
    //回写
    for r := 0; r < MAX_R; r++ {
          //有多个值，需要再次排序
        if len(count[r]) > 1 { 
            //递归排序
            sortMSD(count[r], 0, len(count[r])-1, d+1)
        } else {
              //合并数据
            if len(count[r]) == 1 { 
                aux = append(aux, count[r][0])
            }
        }
    }
    return aux
}

调用测试：

func TestHeight(t *testing.T) {
    a := []string{
        "she",
        "sky",
        "selle",
        "sell",
        "by",
        "the",
        "an",
        "a",
    }
    
    N := len(a)
    fmt.Println(sortMSD(a, 0, N-1, 0))
}