打印ASCII字符数组线性时间排序算法描述及稳定性咨询

算法步骤（计数排序） #

• 第一步：划定计数范围。打印ASCII字符的ASCII码值从32（空格）到126（波浪号~），共95种不同字符。先创建一个长度为95的数组，所有元素初始化为0，用来统计每个字符的出现次数。
• 第二步：统计字符出现频率。遍历输入的无序字符数组，每遇到一个字符，就用它的ASCII码值减去32得到对应索引，然后把计数数组该索引位置的数值加1。比如遇到字符b（ASCII码98），计算98-32=66，就把计数数组第66位的数值加1。
• 第三步：生成排序后的数组。从计数数组的第一个位置（对应空格）开始遍历，对于每个索引位置，如果计数数值大于0，就连续输出对应次数的字符（字符=索引+32），将这些字符依次放入结果数组。遍历完成后，结果数组就是按字母顺序排好序的数组。

稳定版本说明 #

计数排序存在稳定版本，只需对上述步骤做如下调整：

• 统计完频率后，对计数数组计算前缀和：将计数数组第i位的数值更新为前i位（含自身）的累加和，这个数值代表对应字符在排序后数组中最后一次出现的位置+1。
• 从输入数组的末尾开始反向遍历，每取一个字符，找到它在计数数组中的前缀和数值，将该数值减1作为它在结果数组中的位置，放入字符后，把计数数组对应位置的数值减1。
• 这种反向遍历+前缀和的方式，能保留原数组中相同字符的相对顺序，实现稳定排序。

内容的提问来源于stack exchange，提问作者Denis Marchenko