使用插入排序对字符串开头的元音进行排序
Use insertion sort to sort vowels at the beginning of string
是否可以使用插入排序算法对字符串开头的元音进行排序?
我尝试了很多,但我不明白,有人提示如何实现它,或者我应该使用其他排序算法吗?
static char[] text = "thisIsAString".toCharArray();
static void instertionSort() {
for (int i = 0; i < text.length; i++) {
char h = text[i];
int j = i - 1;
while ((j >= 0) && Character.toLowerCase(text[j]) > Character.toLowerCase(h)) {
text[j+1] = text[j];
j = j - 1;
}
text[j+1] = h;
}
}
示例:"thisIsAString" -> "AiiIghnrssStt"
你可以为此使用插入排序(就像其他每个 sort-algorithm 一样,它们都是相等的。只是它们对字段进行排序所花费的时间不同,但结果总是相同的)。
你算法的问题是你没有检查比较的字符是元音字母还是 upper/lower 大小写。
此代码应该有效:
public class StringSorter {
private static final String vowels = "aeiou";
public static void main(String[] args) {
char[] string = "thisIsAString".toCharArray();
char[] test2 = "thisIsAStringaAabBs".toCharArray();
System.out.println("unsorted: " + new String(string));
insertionSort(string);
System.out.println("sorted: " + new String(string));
System.out.println();
System.out.println("unsorted: " + new String(test2));
insertionSort(test2);
System.out.println("sorted: " + new String(test2));
}
public static void insertionSort(char[] string) {
for (int i = 1; i < string.length; i++) {
char h = string[i];
int j = i;
while ((j > 0) && isBefore(string[j - 1], h)) {
string[j] = string[j - 1];
j = j - 1;
}
string[j] = h;
}
}
private static boolean isBefore(char a, char b) {
String lowA = Character.toString(Character.toLowerCase(a));
String lowB = Character.toString(Character.toLowerCase(b));
if (vowels.contains(lowA)) {
if (vowels.contains(lowB)) {
//both are vowels
return chooseLowerCaseFirst(a, b);
}
else {
//only a is a vowel
return false;
}
}
else if (vowels.contains(lowB)) {
//only b is a vowel
return true;
}
else {
//none is a vowel
return chooseLowerCaseFirst(a, b);
}
}
private static boolean chooseLowerCaseFirst(char a, char b) {
String lowA = Character.toString(Character.toLowerCase(a));
String lowB = Character.toString(Character.toLowerCase(b));
if (lowA.equals(lowB)) {
//both are the same character
if (Character.isLowerCase(a)) {
if (Character.isLowerCase(b)) {
//both are lower case
return Character.toLowerCase(a) > Character.toLowerCase(b);
}
else {
//only a is lower case
return false;
}
}
else if (Character.isLowerCase(b)) {
//only b is lower case
return true;
}
else {
//both are upper case
return Character.toLowerCase(a) > Character.toLowerCase(b);
}
}
else {
//different characters
return Character.toLowerCase(a) > Character.toLowerCase(b);
}
}
}
生成的输出是:
unsorted: thisIsAString
sorted: AiiIghnrssStt
unsorted: thisIsAStringaAabBs
sorted: aaAAiiIbBghnrsssStt
如果你也在考虑其他方法,从Java 8你可以通过混合streams and comparators。
import java.util.*;
import java.util.stream.Collectors;
public class Main {
private static List<Character> order = new ArrayList<>(Arrays.asList('a', 'A', 'e', 'E', 'i', 'I', 'o', 'O', 'u', 'U', 'b', 'B', 'c', 'C', 'd', 'D', 'f', 'F', 'g', 'G', 'h', 'H', 'j', 'J', 'k', 'K', 'l', 'L', 'm', 'M', 'n', 'N', 'p', 'P', 'q', 'Q', 'r', 'R', 's', 'S', 't', 'T', 'v', 'V', 'w', 'W', 'x', 'X', 'y', 'Y', 'z', 'Z'));
public static void main(String[] args) {
String example = "thisIsAString";
List<Character> cl = example.chars().mapToObj(c -> (char) c).collect(Collectors.toList());
List<Character> ls = cl.stream().sorted(Comparator.comparingInt(order::indexOf)).collect(Collectors.toCollection(ArrayList::new));
StringBuilder result = new StringBuilder();
for (Character c : ls) result.append(c);
System.out.println(result);
}
}
是否可以使用插入排序算法对字符串开头的元音进行排序?
我尝试了很多,但我不明白,有人提示如何实现它,或者我应该使用其他排序算法吗?
static char[] text = "thisIsAString".toCharArray();
static void instertionSort() {
for (int i = 0; i < text.length; i++) {
char h = text[i];
int j = i - 1;
while ((j >= 0) && Character.toLowerCase(text[j]) > Character.toLowerCase(h)) {
text[j+1] = text[j];
j = j - 1;
}
text[j+1] = h;
}
}
示例:"thisIsAString" -> "AiiIghnrssStt"
你可以为此使用插入排序(就像其他每个 sort-algorithm 一样,它们都是相等的。只是它们对字段进行排序所花费的时间不同,但结果总是相同的)。
你算法的问题是你没有检查比较的字符是元音字母还是 upper/lower 大小写。
此代码应该有效:
public class StringSorter {
private static final String vowels = "aeiou";
public static void main(String[] args) {
char[] string = "thisIsAString".toCharArray();
char[] test2 = "thisIsAStringaAabBs".toCharArray();
System.out.println("unsorted: " + new String(string));
insertionSort(string);
System.out.println("sorted: " + new String(string));
System.out.println();
System.out.println("unsorted: " + new String(test2));
insertionSort(test2);
System.out.println("sorted: " + new String(test2));
}
public static void insertionSort(char[] string) {
for (int i = 1; i < string.length; i++) {
char h = string[i];
int j = i;
while ((j > 0) && isBefore(string[j - 1], h)) {
string[j] = string[j - 1];
j = j - 1;
}
string[j] = h;
}
}
private static boolean isBefore(char a, char b) {
String lowA = Character.toString(Character.toLowerCase(a));
String lowB = Character.toString(Character.toLowerCase(b));
if (vowels.contains(lowA)) {
if (vowels.contains(lowB)) {
//both are vowels
return chooseLowerCaseFirst(a, b);
}
else {
//only a is a vowel
return false;
}
}
else if (vowels.contains(lowB)) {
//only b is a vowel
return true;
}
else {
//none is a vowel
return chooseLowerCaseFirst(a, b);
}
}
private static boolean chooseLowerCaseFirst(char a, char b) {
String lowA = Character.toString(Character.toLowerCase(a));
String lowB = Character.toString(Character.toLowerCase(b));
if (lowA.equals(lowB)) {
//both are the same character
if (Character.isLowerCase(a)) {
if (Character.isLowerCase(b)) {
//both are lower case
return Character.toLowerCase(a) > Character.toLowerCase(b);
}
else {
//only a is lower case
return false;
}
}
else if (Character.isLowerCase(b)) {
//only b is lower case
return true;
}
else {
//both are upper case
return Character.toLowerCase(a) > Character.toLowerCase(b);
}
}
else {
//different characters
return Character.toLowerCase(a) > Character.toLowerCase(b);
}
}
}
生成的输出是:
unsorted: thisIsAString
sorted: AiiIghnrssStt
unsorted: thisIsAStringaAabBs
sorted: aaAAiiIbBghnrsssStt
如果你也在考虑其他方法,从Java 8你可以通过混合streams and comparators。
import java.util.*;
import java.util.stream.Collectors;
public class Main {
private static List<Character> order = new ArrayList<>(Arrays.asList('a', 'A', 'e', 'E', 'i', 'I', 'o', 'O', 'u', 'U', 'b', 'B', 'c', 'C', 'd', 'D', 'f', 'F', 'g', 'G', 'h', 'H', 'j', 'J', 'k', 'K', 'l', 'L', 'm', 'M', 'n', 'N', 'p', 'P', 'q', 'Q', 'r', 'R', 's', 'S', 't', 'T', 'v', 'V', 'w', 'W', 'x', 'X', 'y', 'Y', 'z', 'Z'));
public static void main(String[] args) {
String example = "thisIsAString";
List<Character> cl = example.chars().mapToObj(c -> (char) c).collect(Collectors.toList());
List<Character> ls = cl.stream().sorted(Comparator.comparingInt(order::indexOf)).collect(Collectors.toCollection(ArrayList::new));
StringBuilder result = new StringBuilder();
for (Character c : ls) result.append(c);
System.out.println(result);
}
}