1 字典序概念

2021-0319上机编程认证的入门级&工作级第二题-可漫游服务区，输出结果要求字符串按照字典序降序排序，本文对各编程语言字典序排序方法做一个总结。

题目描述

漫游（roaming）是一种移动电话业务，指移动终端离开自己注册登记的服务区，移动到另一服务区（地区或国家）后，移动通信系统仍可向其提供服务的功能。

用户可签约漫游限制服务，设定一些限制区域，在限制区域内将关闭漫游服务。

现给出漫游限制区域的前缀范围，以及一批服务区（每个服务区由一个数字字符串标识），请判断用户可以漫游的服务区，并以字典序降序输出；如果没有可以漫游的服务区，则输出字符串empty。

输入

首行输入两个整数m n，取值范围均为 [1, 1000]。
随后 m 行是用户签约的漫游限制区域的前缀范围，每行格式为start end（含start和end），start和end是长度相同的数字字符串，长度范围为[1, 6]，且 start <= end。
接下来 n 行是服务区列表，每行一个数字字符串表示一个服务区，长度范围为[6,15]。

输出

字典序降序排列的可漫游服务区列表，或字符串empty

样例

输入样例 1 复制

2 4

755 769

398 399

3970001

756000000000002

600032

755100

输出样例 1

600032

3970001

提示样例 1

服务区 755100 和 756000000000002 的前缀在漫游限制 [755,769] 范围内，不能漫游。 3970001 和 600032，不在任何漫游限制范围内，因此可以漫游，按字典序降序先输出 600032。

题目中提供了字典序的概念定义：

提示

字典序：指按照单词出现在字典的顺序进行排序的方法。先按照第一个字母以 0、1、2 … 9，a、b、c … z 等的ASCII码值顺序排列，如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如 sigh 和 sight），那么把短者排在前。

同时也可参见维基百科的定义https://zh.wikipedia.org/wiki/%E5%AD%97%E5%85%B8%E5%BA%8F

字典序是字符串比较、排序的最常用方式，各编程语言提供的字符串比较或排序的库函数，核心比较逻辑也都基于字典序。

通过对题目答题代码的分析，大部分员工对题目的基本实现是对的，但其中有相当一部分员工在字典序降序排序时出现错误：未正确使用库函数，或者自己实现但出错。例如某C语言答题代码：未使用库函数，自己写了一个冒泡排序，但降序的比较方向搞反了，实现为升序排列了：

……

void Swapresult(char result[MAXN][BUF_LEN], int resultnum)

{

int i, j, ret;

char tmpstr[BUF_LEN] = {0};

for (i = 0; i < resultnum; i++)

{

for (j = i + 1; j < resultnum; j++)

{

if (strcmp(result[i], result[j])) // 错误，降序应该是小于0或者把strcmp的两个参数调换一下顺序

{

ret = memcpy_s(tmpstr, sizeof(tmpstr), result[i], BUF_LEN);

ret = memcpy_s(result[i], BUF_LEN, result[j], BUF_LEN);

ret = memcpy_s(result[j], BUF_LEN, tmpstr, BUF_LEN);

}

……

下面某Java答题代码，仅实现了反转，并未排序；按其逻辑，前面加上sort就可以了：

……

List<String> allowAreas = new ArrayList<>();

……

Collections.reverse(allowAreas); // 错误：仅反转，需要先sort 再reverse

return allowAreas.toArray(new String[0]);

……

本文对字典序及字符串的比较和排序的原理，以及各语言提供的相关库函数进行介绍，并给出使用的代码样例，供大家编程时参考。主要涉及到下面两方面内容：

1）使用库函数进行字符串的比较（按字典序规则），以及正确应用在排序中

2）延伸应用到二维排序等复杂场景

2 各语言提供的相关库函数

2.1 C语言相关库函数及代码示例

1. 字符串比较：C语言库函数strcmp就是基于字典序比较两个字符串的大小：

函数原型: int strcmp(const char *str1, const char *str2);

返回值： str1 大于 str2 , 返回正值；

str1 小于 str2 , 返回负值；

str1 等于 str2 , 返回 0；

如下是strcmp函数的一个大致实现，用了字典序的规则，即：逐个字符比较，根据第一个不同字符的ASCII码值给出比较结果，如果所有字符都相同时，这两个字符串相等。

#include <stdio.h>

#include <string.h>

static int MyStrcmp(const char *str1, const char *str2) {

while ((*str1) && (*str1 == *str2)) { // 逐字符比较

str1++;

str2++;

}

if (*(unsigned char *)str1 > *(unsigned char *)str2) {

return 1;

}

else if (*(unsigned char *)str1 < *(unsigned char *)str2) {

return -1;

} else {

return 0;

}

2. 字符串序列排序：库函数 qsort 是C语言提供的通用排序函数，可用于对字符串序列进行排序，只要在比较函数cmp中调用字符串比较函数 strcmp 即可实现按字典序排序，代码示例如下：

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int cmp(const void *s1, const void *s2)

{

// 字典序降序的比较条件；升序可以用strcmp(s1, s2)

return strcmp((const char *)s2, (const char *)s1);

}

int main()

{

char str[4][10] = {"apple", "banana", "9", "10"};

qsort(str, 4, 10, cmp);

printf("字典序排序: ");

for (int i = 0; i < 4; i++) {

printf("%s ", str[i]);

}

return 0;

}

补充说明：qsort +比较函数是C语言提供的通用排序功能，比较函数cmp可根据不同的需要来实现，从而获得不同的排序效果。参考 http://3ms.huawei.com/km/groups/3803117/blogs/details/8089073 对qsort的介绍。

对于0319-可漫游服务区，下面的C答题代码就是利用库函数进行降序排序的正确实现：

......

int CmpFunc(const void *a, const void *b)

{

return strcmp((char *)b, (char *)a);

}

......

qsort(outBuf, k, sizeof(outBuf[0]), CmpFunc);

......

2.2 C++语言库函数及代码示例

1. 字符串比较：类似于C语言的strcmp函数，C++标准库string类重载了大于、等于、小于等运算符，可直接用于字符串的比较（基于字典序）。例如 "apple" < "banana", "9" > "10" 。

2. 字符串序列排序：同样的，类似于C语言的qsort函数，C++标准库还提供了 sort函数，可用于对字符串序列进行排序。sort 函数默认的排序方式是字典序升序，两个参数就可以了。sort函数原型如下：

Defined in header<algorithm>

template <class RandomIt>

void sort(RandomIt first, RandomIt last);

template <class RandomIt, class Compare>

void sort(RandomIt first, RandomIt last, Compare comp);

comp: The signature of the comparison function should be equivalent to the following :

bool cmp(const Type1 &a, const Type2 &b);

基于sort函数，可以采用不同形式的comp参数，来实现按字典序降序排序：

1）lambda表达式（其中调用string类的比较运算符实现）；

2）全局函数或者静态函数；

3）greater模板类对象；

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

bool Cmp(const string &a, const string &b)

{

return a > b;

}

int main()

{

vector<string> arr = {"apple", "banana", "9", "10"};

sort(arr.begin(), arr.end(), [](string a, string b) { return a > b; });

// sort(arr.begin(), arr.end(), Cmp);

// sort(arr.begin(), arr.end(), greater<string>());

cout << "降序排序-基于comp参数: ";

for (auto s : arr) {

cout << s << ' ';

}

cout << endl;

}

也可以采用 sort 的默认形式完成升序排序，然后再调用 reverse 反转实现降序排序；但sort + reverse多进行了一次反转，性能会略低：

arr = {"apple", "banana", "9", "10"};

sort(arr.begin(), arr.end());

reverse(arr.begin(), arr.end());

cout << "降序排序-基于库函数 sort + reverse: ";

for (auto s : arr) {

cout << s << ' ';

}

cout << endl;

2.3 Java语言库函数及代码示例

1. 字符串比较：Java String类实现了compareTo接口，可用于两个字符串的比较（基于字典序），用法为str1.compareTo(str2); 返回一个整数值，按字典序str1等于str2字符串时返回0，str1大于str2时返回值大于0，小于时返回值小于0。

2. 字符串序列排序：sort 函数可用于字符串序列的排序，默认按字典序升序排序。基于sort函数有多种方式可以实现降序排序，同时存储字符串可用List或Array：

图1	图2 List	图3 Array
图4 自己实现比较函数，可调用String类的compareTo接口实现	ü	ü
图5 Collections.reverseOrder() 或 Comparator.reverseOrder()	ü	ü
图6 利用stream	ü	ü
图7 sort()升序 + reverse()反转	ü	ü

import java.util.List;

import java.util.Arrays;

import java.util.Collections;

import java.util.stream.Collectors;

public class Main {

public static void main(String[] args) {

// List排序-自己实现比较函数

List<String> list = Arrays.asList("apple", "banana", "9", "10");

list.sort((o1, o2) -> o2.compareTo(o1)); // 降序

System.out.println("List排序-比较函数：" + list);

// List排序-Collections.reverseOrder()

list = Arrays.asList("apple", "banana", "9", "10");

list.sort(Collections.reverseOrder()); // 或者Comparator.reverseOrder()

System.out.println("List排序-Collections.reverseOrder()：" + list);

// List排序-stream

list = Arrays.asList("apple", "banana", "9", "10");

List<String> list2 = list.stream().sorted(Comparator.reverseOrder()).collect(Collectors.toList());

System.out.println("List排序-stream：" + list2);

// List排序-升序+反转

list = Arrays.asList("apple", "banana", "9", "10");

Collections.sort(list);

Collections.reverse(list);

System.out.println("List排序-升序+反转：" + list);

// Array排序-比较函数

String[] arr = {"apple", "banana", "9", "10"};

// 字典序降序排序，如果升序改为第二个参数改为 o1.compareTo(o2)即可

Arrays.sort(arr, (o1, o2) -> o2.compareTo(o1));

System.out.println("数组字典序排序：" + Arrays.toString(arr));

}

注：采用sort()升序 + reverse()反转方式，多进行了一次反转，性能会略低。

对于0319-可漫游服务区，下面一个Java答题代码就是利用库函数的正确实现：

List<String> result = new ArrayList<>();

.......

result.sort((o1, o2) -> {

return o2.compareTo(o1);

});

String[] strs = result.toArray(new String[result.size()]);

return strs;

......

2.4 Python语言库函数及代码示例

1. 字符串比较：Python的大于、等于、小于等运算符可直接用于比较两个字符串（基于字典序），例如 "apple" < "banana", "9" > "10"。

2. 字符串序列排序：Python库函数 sort 可用于多个字符串的排序，其背后逻辑就是利用字符串比较运算符（字典序的），默认为字典序升序排序。降序的实现方式有：

1） sort + reverse参数

2） sort + 比较函数

from functools import cmp_to_key

# 字符串序列排序-sort+reverse参数

arr = ["apple", "banana", "9", "10"]

arr.sort(reverse=True) # 降序

print("字符串序列排序-reverse参数: " + str(arr))

# 字符串序列排序-比较函数

def cmp(x, y):

if x < y: return 1

elif x == y: return 0

else: return -1

arr = ["apple", "banana", "9", "10"]

arr.sort(key=cmp_to_key(cmp))

print("字符串序列排序-比较函数: " + str(arr))

2.5 Go语言库函数及代码示例

1、字符串比较：1）go语言的大于、等于、小于等运算符可直接用于比较两个字符串（基于字典序），例如 "apple" < "banana"，"9" > "10"； 2）strings.Compare 基于字典序实现两个字符串的比较，strings.Compare("apple" , "banana")返回值小于0。

2、字符串序列排序：库函数 sort 可用于多个字符串的排序，默认为字典序升序排序。降序的实现方式有：

1）sort + 比较函数

2）sort + Reverse

package main

import (

"fmt"

"sort"

)

func main() {

// 字符串数序列排序-比较函数

arr := []string{"apple", "banana", "9", "10"}

sort.Slice(arr, func(i, j int) bool {

return arr[i] > arr[j]

})

fmt.Print("字符串序列排序-比较函数: ")

fmt.Print(arr)

// 字符串序列排序-reverse

arr2 := []string{"apple", "banana", "9", "10"}

sort.Sort(sort.Reverse(sort.StringSlice(arr2)))

fmt.Print("\n字符串序列排序-reverse: ")

fmt.Print(arr2)

}

2.6 JavaScript语言库函数及代码样例

1. 字符串比较：JavaScript的大于、等于、小于等运算符可直接用于比较两个字符串（基于字典序），例如 'apple' < 'banana', '9' > '10' 。

2. 字符串序列排序：库函数 sort 默认为字典序升序排序。降序的实现方式有：

1） sort + 比较函数

2） sort + reverse

const cmp = (x, y) => x < y ? 1 : -1;

let arr = ['apple', 'banana', '9', '10'];

arr.sort(cmp);

// arr.sort((x, y) => x < y ? 1 : -1);

console.log(arr);

arr = ['apple', 'banana', '9', '10'];

arr.sort().reverse(); // 按字典序降序排序；如果升序直接用 sort() 即可

console.log(arr);

3 总结及延伸

3.1 各语言字符串比较、字符串序列排序方式汇总

基于字典序的字符串比较、字符串序列排序，可以直接利用各语言标准库的功能，不需要自己写排序算法或字符串比较函数，汇总如下：

图8	图9 字符串比较（字典序）	图10 字符串序列排序（字典序降序）
图11 C语言	ü strcmp	ü qsort +比较函数（调用strcmp）
图12 C++语言	ü string类比较运算符： >， <， ==	ü sort + 比较函数（3种方式）
图13 Java语言	ü String类实现了Comparable接口的compareTo方法	ü sort + 比较函数（调用String类compareTo方法） ü sort + Collections.reverseOrder() 或Comparator.reverseOrder() ü stream().sorted方法
图14 Python语言	ü str类比较运算符： >， <， ==	ü sort + 比较函数
图15 Go语言	ü string比较运算符： >， <， == ü strings类Compare方法	ü sort + 比较函数
图16 JavaScript语言	ü string类比较运算符： >， <， ==	ü sort + 比较函数

基于字典序排序是编程中的一个常用知识点，认证中也会进行考察，例如下面上机编程认证试题都涉及到了字典序排序（升序或降序）：

1）2021-0319上机编程认证的入门级&工作级第二题-可漫游服务区

2）【认证试题】整理工号 http://oj.rnd.huawei.com/problems/1808/details

3.2 二维整数数组（不等长）排序

基于字典序的字符串比较，相当于两个字符数组的比较；其它类型数组的比较，也可以应用这一比较思路；进而可以实现二维数组（可能不等长）的排序。例如二维整数数组[[2,10], [2,9, 1], [2,10,-1]]，升序排序为[[2,9,1], [2,10], [2,10,-1]]，降序排序为[[2,10,-1], [2,10], [2,9,1]]。【认证试题】整数分解http://oj.rnd.huawei.com/problems/1908/details 就涉及到二维整数数组（不等长）的排序。

二维整数数组排序相关的库函数及参考代码如下：

	二维整数数组（不等长）排序
	sort + 比较函数	sort + reverse
C语言	// 对于不等长二维数组，建议C语言采用结构体 #define NODE_MAX_NUM 100 struct Node { int num; int values[NODE_MAX_NUM]; }; int intCmp(const void data1, const void data2) { struct Node key1 = (struct Node )data1; struct Node key2 = (struct Node )data2; int minLength = key1->num; if (key2->num < key1->num) minLength = key2->num; for (int i = 0; i < minLength; i++) { if (key1->values[i] == key2->values[i]) continue; return key2->values[i] -key1->values[i]; //升序取负 } return key2->num - key1->num; } int main { … struct Node n1 = {2, {2, 10}}; struct Node n2 = {3, {2, 9, 1}}; struct Node n3 = {3, {2, 10, -1}}; struct Node arr[3] = {n1, n2, n3}; qsort(arr, 3, sizeof(struct Node), intCmp); … return 0; }	无
C++语言	sort(arr.begin(), arr.end(), greater<vector<int>>());	sort(arr.begin(), arr.end()); reverse(arr.begin(), arr.end());
Java语言	Arrays.sort(arr, (a, b) -> { int minLength = Math.min(a.length, b.length); for (int i = 0; i < minLength; i++) { if (a[i] == b[i]) { continue; } return b[i] - a[i]; //升序改成 a[i] - b[i] } return b.length -a.length; //升序 a.length -b.length });	无
Python语言	def compare(x, y): if x < y: return 1 elif x == y: return 0 else: return -1 arr = [[2, 9, 1], [2, 10, -1], [2, 10]] arr.sort(key=cmp_to_key(compare))	arr.sort(reverse=True)
Go语言	intArr := [][]int{{2, 10}, {2, 9,1}, {2, 10, -1}} sort.Slice(intArr, func(i, j int) bool { min := len(intArr[i]) if len(intArr[j]) < min { min = len(intArr[j]) } for k := 0; k < min; k++ { if intArr[i][k] != intArr[j][k] { return intArr[i][k] > intArr[j][k] } } return len(intArr[j]) < len(intArr[i]) })	无
JavaScript语言	let arr = [[2, 10], [2, 10, -1], [2, 9, 1]]; arr.sort((a, b) => { let minLength = Math.min(a.length, b.length); for (let i = 0; i < minLength; i++) { if (a[i] === b[i]) { continue; } return b[i] - a[i]; // 升序改成 a[i] - b[i] } return b.length -a.length; //升序改成 a.length -b.length });	无