字符串排序

问题描述

编写一个程序，将输入字符串中的字符按如下规则排序。
规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。
如，输入： Type
输出： epTy
规则 2 ：同一个英文字母的大小写同时存在时，按照输入顺序排列。
如，输入： BabA
输出： aABb
规则 3 ：非英文字母的其它字符保持原来的位置。
如，输入： By?e
输出： Be?y
示例1
输入
A Famous Saying: Much Ado About Nothing (2012/8).
输出
A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).

思路

其实就是排除非字母的排序问题，且注意不区分大小，注意如果你采用排序算法来做这道题，一定要注意你选择的算法必须是稳定的，即保留元素的相对位置不变。

代码

代码一

package com.special.spet;
import java.util.Scanner;
/**
* 字符串排序
* 1.常规方法：将原字符串中的非字母与字母分开
* 非字母数组中记录在原字符串中出现的索引
* 字母数组用插入排序（必须是稳定的排序算法）
* 然后对排序后的数组根据非字母数组的索引位置依次插入非字母
* 复杂度O(n的平方）
* 2.对以上方法进行改进：我们无需记录非字母
* 对字母排序后，我们只要遍历原字符串，在是字母的情况下
* 依次从字母数组取出来字符并代替！
* @author special
* @date 2017年9月18日 上午8:12:01
*/
public class Pro25 {
/**
* 字母比较大小，基于小写字母的比较
* @param ch1
* @param ch2
* @return
*/
public static boolean less(char ch1, char ch2){
ch1 = toLower(ch1);
ch2 = toLower(ch2);
if(ch1 < ch2) return true;
else
return false;
}
/**
* 插入排序
* @param ch
* @param length
*/
public static void sort(char[] ch , int length){
for(int i = 1; i < length; i++){
char temp = ch[i];
int j = i - 1;
for(; j >= 0; j--){
if(less(temp, ch[j]))
ch[j + 1] = ch[j];
else
break;
}
/**
* 不管以何种条件结束循环
* 都是赋值到j + 1的位置上
*/
ch[j + 1] = temp;
}
}
/**
* 判断是不是字母
* @param ch
* @return
*/
public static boolean isNotLetter(char ch){
if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
return false;
return true;
}
/**
* 转换成小写字母
* @param ch
* @return
*/
public static char toLower(char ch){
if(ch >= 'A' && ch <= 'Z')
return (char) ('a' + ch - 'A');
return ch;
}
/**
* 字符串排序
* @param str
* @return
*/
public static String sort(String str){
int length = str.length();
int[] flag = new int[length];
char[] sortedSeq
= new char[length];
int flagSize = 0;
int sortedSeqSize = 0;
for(int i = 0; i < length; i++){
char temp = str.charAt(i);
if(isNotLetter(temp)) flag[flagSize++] = i;
else
sortedSeq[sortedSeqSize++] = temp;
}
sort(sortedSeq,sortedSeqSize);
for(int i = 0; i < flagSize; i++){
int index = flag[i];
for(int j = sortedSeqSize - 1; j >= index; j--){
sortedSeq[j + 1] = sortedSeq[j];
}
sortedSeq[index] = str.charAt(index);
sortedSeqSize++;
}
return new String(sortedSeq);
}
/**
* 改进以上的sort方法
* 此方法不需要记录非字母数组
* 且不需要进行非字母的插入操作！
* @param str
* @return
*/
public static String improveSort(String str){
int length = str.length();
char[] sortedSeq
= new char[length];
int sortedSeqSize = 0;
for(int i = 0; i < length; i++){
char temp = str.charAt(i);
if(!isNotLetter(temp)) sortedSeq[sortedSeqSize++] = temp;
}
sort(sortedSeq,sortedSeqSize);
StringBuilder sortedString = new StringBuilder(str);
int index = 0;
/**
* 我们这里不需要像上诉sort方法那样记录非字母，然后一个一个插进来
* 直接可以判断原字符串是不是字母，是的话，就依次从字母数组提取
* 不是的话，跳过，还是原字符
* 聪明的做法，赞一个！
*/
for(int i = 0; i < length; i++){
char temp = str.charAt(i);
if(!isNotLetter(temp)) sortedString.setCharAt(i, sortedSeq[index++]);
}
return sortedString.toString();
}
public static void main(String[] args){
Scanner input = new Scanner(System.in);
while(input.hasNext()){
String str = input.nextLine();
String result = improveSort(str);
System.out.println(result);
}
}
}

代码二

package com.special.spet;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
*
* @author special
* @date 2017年9月18日 上午11:30:33
*/
public class Pro25Improve1 {
/**
* 没有采用排序，而是按字母表的每一位来考察原字符串是否含有。
* 有的话，就添加到list中，这样就不用考虑处理顺序，必然自动维护一个顺序
* 然后就在遍历一次字符串，其中的每一位字母位都从list中取
* 大神的杰作！
* @param str
* @return
*/
public static String sort(String str){
int length = str.length();
List<Character> letterList = new ArrayList<Character>();
for(int i = 0; i < 26; i++){
for(int j = 0; j < length; j++){
char temp = str.charAt(j);
/**
* 这里判断是否是按顺序来的字母的方法也很巧妙
* 以后可以借鉴一下
*/
if((temp - 'a' == i) || (temp - 'A' == i))
letterList.add(temp);
}
}
StringBuilder sortedString = new StringBuilder(str);
int index = 0;
for(int i = 0; i < length; i++){
char temp = str.charAt(i);
if((temp >= 'a' && temp <= 'z') || (temp >= 'A' && temp <= 'Z'))
sortedString.setCharAt(i, letterList.get(index++));
}
return sortedString.toString();
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
String str = input.nextLine();
String result = sort(str);
System.out.println(result);
}
}
}

代码三

package com.special.spet;
import java.util.Scanner;
/**
*
* @author special
* @date 2017年9月18日 下午1:49:32
*/
public class Pro25Improve2 {
public static boolean isNotLetter(char ch){
if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
return false;
return true;
}
public static char toLower(char ch){
if(ch >= 'A' && ch <= 'Z')
return (char) ('a' + ch - 'A');
return ch;
}
/**
* 变形的冒泡法，类比希尔排序
* 非字母不参与排序
* @param str
* @return
*/
public static char[] sort(String str){
int length = str.length();
char[] strArray = str.toCharArray();
int letterFirstIndex = 0;
/**
* 找到第一字母的位置
* 方便我们下面循环的时候，内循环少一点。
*/
while(isNotLetter(strArray[letterFirstIndex]))
letterFirstIndex++;
for(int i = 0; i < length; i++){
int swapIndex = letterFirstIndex;
for(int j = swapIndex + 1; j < length - i; j++){
if(isNotLetter(strArray[j])) continue;
//如果该位置不是字母，继续下一个
/**
* 若上一个位置的字母大于当前位置字母，则交换
*/
if(toLower(strArray[swapIndex]) > toLower(strArray[j])){
char temp = strArray[j];
strArray[j] = strArray[swapIndex];
strArray[swapIndex] = temp;
}
/**
* 无论是否交换，都应该记住j的位置
* 因为j的位置永远代表最大的
*/
swapIndex = j;
}
}
return strArray;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
String str = input.nextLine();
char[] result = sort(str);
System.out.println(result);
}
}
}

代码四

package com.special.improve;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* 类似桶排序
* @author special
* @date 2017年9月18日 下午2:29:39
*/
public class Pro25Improve3 {
public static boolean isNotLetter(char ch){
if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
return false;
return true;
}
public static char toLower(char ch){
if(ch >= 'A' && ch <= 'Z')
return (char) ('a' + ch - 'A');
return ch;
}
/**
* 变形的冒泡法，类比希尔排序
* 非字母不参与排序
* @param str
* @return
*/
@SuppressWarnings("unchecked")
public static char[] sort(String str){
int length = str.length();
char[] strArray = str.toCharArray();
/**
* 这里Java创建泛型类数组，会报错
* 只能采用这种不安全的做法
*/
Queue[] letterList = new LinkedList[26];
for(int i = 0; i < 26; i++)
letterList[i] = new LinkedList();
for(int i = 0; i < length; i++){
if(isNotLetter(strArray[i])) continue;
else letterList[toLower(strArray[i]) - 'a'].add(strArray[i]);
}
int noEmptyIndex = 0;
for(int i = 0; i < length; i++){
if(isNotLetter(strArray[i])) continue;
while(letterList[noEmptyIndex].size() == 0){
noEmptyIndex++;
}
strArray[i] = (char) letterList[noEmptyIndex].poll();
}
return strArray;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
String str = input.nextLine();
char[] result = sort(str);
System.out.println(result);
}
}
}

总结

多思考，多想，总有收获！

最后

以上就是曾经鸭子为你收集整理的字符串排序的全部内容，希望文章能够帮你解决字符串排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。