华为2015实习上机：字符串排序

古城微笑少年丶 2022-08-07 15:54 117阅读 0赞

# 一、按照字母的ascii码顺序排序，其他非字母字符在字符串中位置不变 #

## 快速排序算法    ##

可以看出，下面的程序就是一个快速排序算法，只是增加了对非英文字母的字符的处理：

快速排序参考文章[快速排序的几种常见实现][Link 1]

//输入字符串，按照字母的ascii码顺序排序，其他非字母字符在字符串中位置不变
    //如，输入Wor#d，输出Wdo#r
    //快速排序实现
    
    void QuickStrSort(char str[], int left, int right) {
        char pivot = str[left];
        int i = left, j = right;
        if (left < right) {
            while (i < j) {
                //j从右向左找第一个小于枢纽的字母，如果遇到不是字母的继续向前找
                while (i < j && 
                         (
                           (isalpha(str[j]) && str[j] >= pivot) || (!isalpha(str[j]))
                         )
                      )
                    j--;
                str[i] = str[j];
                //i从左向右找第一个大于枢纽的字母，遇到不是字母继续向后找
                while (i < j && 
                    ((isalpha(str[i]) && str[i] <= pivot) || (!isalpha(str[i])))
                    )
                    i++;
                str[j] = str[i];
            }
            str[i] = pivot;
            QuickStrSort(str, left, i - 1);
            QuickStrSort(str, i + 1, right);
        }
    }
    int main() {
        char str[102];
        while (1) {
            cin >> str;
            QuickStrSort(str, 0, strlen(str) - 1);
            cout << str << endl << endl;;
        }
        return 0;
    }

![SouthEast][]

## 冒泡排序 ##

使用类似冒泡排序方法求解：

int main() {
    	string str;
    	getline(cin, str);
    	int i, j;
    	int len = str.length();
    	for (i = 0; i < len - 1; i++) {
    		for (j = 0; j < len - i - 1; j++) {
    			//每趟找到第一个字母，然后找到该字母后的第一个字母
    			//对这两个字母比较大小，若为逆序则交换它们
    			if (isalpha(str[j])) {
    				int k = j + 1;
    				while (!isalpha(str[k]) && k < len - i - 1)
    					++k;
    				if (isalpha(str[k])) {
    					if (str[j] > str[k]) {
    						char temp = str[j];
    						str[j] = str[k];
    						str[k] = temp;
    					}
    				}
    			}
    		}
    	}
    	cout << str << endl;
    	return 0;
    }

# 二、另一类型 #

![Center][]

这个题目根据其规则2：要求同一字母（不区分大小写）按照输入顺序排列；所以不能再使用快速排序，因为快速排序是不稳定的，那么相同字母顺序在排序后可能会改变。

下面是类似冒泡解决方法：

int main()
    {
    	char str[1000];
    	int i,j,k;
    	int len = 0;
    	char tmp;
    	gets(str);
    	len = strlen(str);
    	for(i = 0; i < len-1; ++i)
    	{
    		for(j = 0; j < len-1-i; ++j)
    		{
    			k = j;
    			//如果str[j]是一个字母，那么就寻找其后的第一个字母a
    			//找到了,并且a大于str[j]那么就将它们交换
    			if(isalpha(str[j]))
    			{
    				while(!isalpha(str[k+1]) && k < len-i-1)
    					k++;
    
    				if(isalpha(str[k+1]))
    					if(tolower(str[j]) > tolower(str[k+1]))
    					{
    						tmp = str[j];
    						str[j] = str[k+1];
    						str[k+1] = tmp;
    					}
    			}
    		}
    
    	}
    	puts(str);
    	return 0;
    }

[Link 1]: http://blog.csdn.net/u013074465/article/details/42083607
[SouthEast]: /images/20220805/81e6ef1b529b4c2cb3bf034349e66d3e.png
[Center]: /images/20220805/91103ded7a374b819c9c0bff26bfb3d6.png