排序算法: 超高速根据字符串长度排序的算法

890 字

4 分钟

排序算法: 超高速根据字符串长度排序的算法

2020-06-26

.NET

字符串

/

算法

/

列表

/

csharp

1. 你需要知道这些:#

代码适用于:#

适用于字符串数组的元素长度变化量较小的, 比如字符串的长度普遍在1~2000, 那么此时, 这个算法将有超高的性能, 测试结果是 10万条数据排序所需时间为91ms(你没看错).

应用场景:#

你有一个超级长的文本文件, 这里面每一行都是一条数据, 例如这些数据是用爬虫获取的搜索关键字, 你现在需要将它们排序, 别犹豫, 我认为这个算法非常适合你.

局限性#

字符串数组的元素长度变化量越大, 该算法效率可能会越低,因为里面包含了对字符串长度变化量排序的过程,这个过程是使用的选择排序法。（选择排序法的所需时间与数据长度不成正比,不多赘述）

2.算法的主要内容#

主要原理:#

定义一个字典, 键是int, 值是可变的字符串列表, 定义一个可变的字符串列表作为存储结果的容器
循环源字符串数组, 将一切可能的长度作为int, 一个新的字符串列表作为值, 添加到上面所说的字典里面
第二次循环源字符串数组, 将迭代到的字符串的长度作为键, 在字典中键所对应的字符串列表中添加这个字符串
排序字典的键, 循环排序后的所有键, 将键对应的字符串列表的每一个字符串添加到结果中
排序结束

示例代码:#

1
// 这是C#代码
2
// Dictionary 与 List 位于 System.Collections.Generic 命名空间下
3
string[] StringSort(string[] source)
4
        {
5
            int[] sortKeys(int[] src)    // 这里是用于排序字典的键的
6
            {
7
                int most;
8
                int mostIndex = 0;
9
                int temp;
10
                if (src.Length > 1)
11
                {
12
                    for (int i = 1; i < src.Length; i++)
13
                    {
14
                        most = src[i];
15
                        for (int j = i; j < src.Length; j++)
16
                        {
17
                            if (src[j] < most)
18
                            {
19
                                most = src[j];
20
                                mostIndex = j;
21
                            }
22
                        }
23
                        if (most < src[i - 1])
24
                        {
25
                            src[mostIndex] = src[i - 1];
26
                            src[i - 1] = most;
27
                        }
28
                    }
29
                }
30
                return src;
31
            }
32

33
            Dictionary<int, List<string>> firstSortedString = new Dictionary<int, List<string>>();
34
            List<string> result = new List<string>();
35

36
            foreach (string i in source)
37
            {
38
                if (!firstSortedString.ContainsKey(i.Length))
39
                {
40
                    firstSortedString.Add(i.Length, new List<string>());
41
                }
42
            }
43
            foreach (string i in source)
44
            {
45
                firstSortedString[i.Length].Add(i);
46
            }
47
            foreach (int i in sortKeys(firstSortedString.Keys.ToArray()))
48
            {
49
                foreach (string j in firstSortedString[i])
50
                {
51
                    result.Add(j);
52
                }
53
            }
54

55
            return result.ToArray();
56
        }
57
    }