高位优先的字符串排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//MSD(Most Significant Digit First) 高位优先的字符串排序
//该算法基于键索引计数法的思想，进行了扩展，使得该算法可以
//处理不等长的字符串排序，其中涉及两个关键点。
//1、采用分治法，从高位向低位的方向，依次选取关键字做为排序
//
的键字进行排序，每一轮排序后，将字符串组进行拆分，对拆
//
分后的每个子组分别进行排序，这里子组拆分的依据就是本轮
//
键索引计数法排序之后的分类组。
//
//
如下示例，最初只有一个字符串组，其中组成员数为5个字符串
//
首先，选择第0列做为排序的链字进行键索引计数法排序，排序
//
完成后，按分类组划分，此时分为了两组（见第一次后的情况）,
//
这时候对这两组分别进行链索引计数法排序，注意这时每组第
//
0列已经为相同字符，所以此时选择第1做为排序的链字进行键
//
索引计数法排序，在第二次排序后，此时已经分为了4组字符串
//
组，依次类推，直到所有子组仅含有一个成员，所有子组排序
//
处理完后，即整个字符串排序算法完成。
//
//
原始：
第一次后：
第二次后：
//
abcd
abcd
abcd
//
ddba
acca
//
daca
acca
//
acca
ddba
//
daab
daca
daca
//
daab
daab
//
//
ddba
//
//2、刚才提到了该算法可以处理不等长的字符串排序，该算法采用一
//
种比较巧妙的方法，将短字符串长度已经满足不了排序的处理也
//
做为键值比较处理了，同时如果短字符串长度满足不了排序处理
//
时，该键值优先级最高，所以就会出现排在最上方。
//
//
如下示例，当第2列(字符c的位置)处理完后，开始进行第3列比较
//
处理，此时第一个条目abcd的第3列键值为d、第二个条目abc的第
//
3列键值已经不存在，长度已经满足不了排序，但此时键值优先级
//
为最高，第三个条目abcde的第3列键值为d，所以本轮最终将第二
//
个条目abc排在了最上面，相同原理，abcd条目就会比abcde条目的
//
优先级高。
//
//
原始：
排序后：
//
abcd
abc
//
abc
abcd
//
abcde
abcde
//
//有效字符基数
#define CHAR_BASE 256
//查找提指定索引处char的值，如果不存在则返回-1
char charAt(const char *pStr, const int index)
{
const char *pOldStr = pStr;
if ( pStr == NULL )
{
return -1;
}
while ( *pStr != '' )
{
if ( (pStr-pOldStr) == index )
{
return *pStr;
}
pStr++;
}
return -1;
}
//高位优先字符串排序核心算法
//正如上面描述，该算法是基于键索引计数法的思想，对于键索引计数法
//这里不详细描述，有兴趣可以参考相关信息，这里仅对特定点进行注释
//说明。
void msdSort(char *strArray[], int lo, int hi, int d)
{
int count[CHAR_BASE+2] = {0};
char **ppAux = NULL;
int i = 0;
//当前函数是递归函数，这里为递归跳出点。当进行字符串排序时，如
//果少于二组条目，则不再进行排序处理。
if ( lo >= hi )
{
return;
}
//对键值进行个数统计，这里选取本组排序字符串中第d列索引字符做为键
//值。
//为什么会出现+2,该步中count[0]预留出来，用于下面步骤的算法使用，
//详细原因参见键索引计数法中的解释，所以当前键值统计需要从索引1开始，
//charAt的实现是找出的字符索引范围为-1~(length(string)-1)，所以如
//果需要满足从索引1开始，则需要在charAt的结果之后+2.
for ( i = lo; i <= hi; i++ )
{
count[charAt(strArray[i], d) + 2]++;
}
//将键值统计转换为排序索引
//这里CHAR_BASE+1，是因为CHAR_BASE仅表示合法字符基数，该算法中由于
//支持不等长处理，对于不满足比较长度的键-1也参与了算法处理，所以这
//里为其+1.
for ( i = 0; i < CHAR_BASE + 1; i++ )
{
count[i+1] += count[i];
}
ppAux = (char **)malloc((hi - lo + 1) * sizeof(char *));
if ( ppAux == NULL )
{
return;
}
memset(ppAux, 0, (hi - lo + 1) * sizeof(char *));
//根据排序索引进行分类，将排序好的分类存储到临时空间ppAux中
//这里会出现+1，也是因为charAt的实现返回索引范围是-1~(lenght(string)-1)，
//当前步骤count有效使用是从索引0开始，所以需要+1来满足。
for ( i = lo; i <= hi; i++ )
{
int index = count[charAt(strArray[i], d) + 1]++;
ppAux[index] = strArray[i];
}
//将排序好的临时空间ppAux内容回写到原来数组中。
for ( i = lo; i <= hi; i++)
{
strArray[i] = ppAux[i-lo];
}
free(ppAux);
//在每一轮排序后，采用分治思想，将当前组拆分为几个更小的组，并对每个更
//小的组进行递归排序处理，这里划分组的依据为，根据本次键值索引的分类进
//行分组，同时在下一轮对更小的组进行算法处理时，键值d则切换为下一列字符
//做为键值，因为本轮算法处理后，每个小组的当前键值d已经相同了。
//这里需要注意一下此时count[0]的为不满足长度处理的键值-1的最后索引位置，
//该键值是不需要参与分组处理的。
for ( i = 0; i < CHAR_BASE; i++ )
{
msdSort(strArray, lo + count[i], lo + count[i+1] - 1, d + 1);
}
}
void dumpArray(char *strArray[], int count)
{
int i = 0;
for ( i = 0; i < count; i++ )
{
printf("[%d] %srn", i, strArray[i]);
}
}
int main()
{
int i = 0;
char *test[10] = {
"she",
"sells",
"seashells",
"by",
"the",
"seashore",
"she",
"are",
"surely",
"secca"
};
dumpArray(test, 10);
msdSort(test, 0, 9, 0);
printf("*****************rn");
dumpArray(test, 10);
return 0;
}