一个字符数组，里面的字符可能是a-z、A-Z、0-9.现在要求对数组进行排序，要求所有小写字符放在最前面，所有大写字符放在中间，所有数字放在最后，而且各部分内部分别有序。

思路：

先进行字符串排序，用堆排序，按降序排列，排列依据字母对应的ascii值。

排序之后按字符类别进行翻转。时间复杂度O（nlogn）

1. #include  
2. #include  
3. using namespace std;  
4.   
5. void swap(char* a, char* b) {  
6.     char temp = *a;  
7.     *a= *b;  
8.     *b = temp;  
9. }  
10.   
11. void heapAdjust(char* str, int i, int length) {  
12.     int lchild = 2 * i + 1;  
13.     int rchild = 2 * i + 2;  
14.     int minIndex;  
15.     if (lchild < length && str[lchild] < str[i])  
16.         minIndex = lchild;  
17.     else  
18.         minIndex = i;  
19.     if (rchild < length && str[rchild] < str[minIndex])  
20.         minIndex = rchild;  
21.     if (minIndex != i) {  
22.         swap(str + i, str + minIndex);  
23.         heapAdjust(str, minIndex, length);  
24.     }  
25. }  
26.   
27. void heapSort(char* str, int length) {  
28.     int i;  
29.     for (i = length / 2; i >= 0; i--)  
30.         heapAdjust(str, i, length);  
31.     for (i = length - 1; i > 0; i--) {  
32.         swap(str + i, str + 0);  
33.         heapAdjust(str, 0, i);  
34.     }  
35. }  
36.   
37. void revserStr(char* pStart, char* pEnd) {  
38.     char charTemp;  
39.     while (pStart < pEnd) {  
40.         charTemp = *pStart;  
41.         *pStart = *pEnd;  
42.         *pEnd = charTemp;  
43.         pStart++;  
44.         pEnd--;  
45.     }  
46. }  
47.   
48. void rearrangeStr(char* pStr, int length) {  
49.     heapSort(pStr, length);  
50.     int i, startIndex = 0, endIndex = -1;  
51.     for (i = 0; i < length; i++) {  
52.         if (pStr[i] >= 'a' && pStr[i] <= 'z') {  
53.             endIndex++;  
54.         } else {  
55.             break;  
56.         }  
57.     }  
58.     if (endIndex > startIndex)  
59.         revserStr(pStr + startIndex, pStr + endIndex);  
60.     startIndex = endIndex + 1;  
61.     for (; i < length; i++) {  
62.         if (pStr[i] >= 'A' && pStr[i] <= 'Z') {  
63.             endIndex++;  
64.         } else {  
65.             break;  
66.         }  
67.     }  
68.     if (endIndex > startIndex)  
69.         revserStr(pStr + startIndex, pStr + endIndex);  
70.     startIndex = endIndex + 1;  
71.     for (; i < length; i++) {  
72.         if (pStr[i] >= '0' && pStr[i] <= '9') {  
73.             endIndex++;  
74.         } else {  
75.             break;  
76.         }  
77.     }  
78.     if (endIndex > startIndex)  
79.         revserStr(pStr + startIndex, pStr + endIndex);  
80.   
81. }  
82.   
83. int main(int argc, char* argv[]) {  
84.     char str[] = "MDEXE098FGH453a4cf9";  
85.     int length = strlen(str);  
86.     rearrangeStr(str, length);  
87.     cout << str << endl;  
88.     cin.get();  
89.     return 0;  
90. }