我有一个关于使用String[]插入排序算法排序数组的问题。我确实意识到,我的问题很可能很容易用不同的算法来完成,但我正在尝试首先学习如何处理这个问题。
基本上,我试图使用该算法对字符串数组进行排序。为此,我比较了字符串数组中的char值,因此我能够使用标准的>和==操作符,因为通过这种方式比较值(就像您与ints一样)自然非常简单。
我有一个我正在处理的解决方案,根据每个数组索引中找到的前2个字符值对字符串数组进行排序,但我开始意识到,我所做的并不是一个非常健壮的解决方案,因为数组中的字符串可以很容易地具有“更长”的值,这不会使我对具有类似值的较长字符串的排序非常准确。
考虑到这一点,有人能建议我如何动态地比较从各种字符串创建的char值,以排序原始的字符串值(与我下面编写的代码一起使用)吗?
所以.
A: ...I不会遇到比较不同大小字符串值的NullPointer异常
B: ...every char值与字符串进行比较,无论大小如何,这样我就可以准确地对原始字符串数组进行排序)
public String[] sortArrayOfStrings(String[] array){
//NOT COMPLETE, ONLY SORTS BASED ON FIRST & SECOND CHAR OF STRING INDEX
//BASED ON INSERTION SORT ALGORITHM
int length = array.length;
String value;
int index;
for(int a = 1; a < length; a++){
char currentCharValue = array[a].charAt(0);//USE '[a]' not '[index]'
value = array[a];
index = a;
if(currentCharValue == array[a - 1].charAt(0) ){//IF FIRST CHAR == PREVIOUS
while (index > 0 && array[index - 1].charAt(1) > array[index].charAt(1)){
array[index] = array[index - 1];
index = index - 1;
}
}else{
while (index > 0 && array[index - 1].charAt(0) > currentCharValue){
array[index] = array[index - 1];
index = index - 1;
}
}
array[index] = value;
}
return array;
}由于2 char检查而按预期工作的示例数组:
String[] arr = {"zz", "bb", "cb", "ba","za", "zb", "cz", "ab","aa"};由于额外的字符而无法正确排序的示例数组:
String[] arr = {"bbz", "bba", "abz","abc"};我知道上面的数组由于两个字符的硬编码' check‘而无法正确排序,我试图消除硬编码检查的需要。
发布于 2018-03-08 21:50:57
如果您真的想使用chars比较来进行比较,最好的方法是创建单独的方法来比较这些String。
在isSmallerThan()中,循环增量currentIndex,直到它对任何参数都没有超出限制,和直到字符相同为止。然后,如果语句检查currentIndex是否超出了至少一个字符串的范围,那么它可以发生在输入例如:(aaa,aa),(aaabb,aaa),(aaa,aaa)。那么,我们必须通过长度比较来决定什么比较小。
对于插入排序算法,我们不关心(aaa,aaa)是相同的字符串,我们只需返回这是false,它就会中断sortArrayOfStrings方法中的while循环。
否则,我们知道字符是不同的,我们只是比较它们。
String[] sortArrayOfStrings(String[] array){
int length = array.length;
String value;
int index;
for(int a = 1; a < length; a++){
value = array[a];
index = a;
while(index > 0 && isSmallerThan(value, array[index-1])) {
array[index] = array[index - 1];
--index;
}
array[index] = value;
}
return array;
}
boolean isSmallerThan(String left, String right) {
int curIndex = 0;
while (curIndex < left.length()
&& curIndex < right.length()
&& left.charAt(curIndex) == right.charAt(curIndex)){
++curIndex;
}
if (curIndex == left.length() || curIndex == right.length())
return left.length() < right.length();
else
return left.charAt(curIndex) < right.charAt(curIndex);
}但是,正如人们前面所说的,最好使用字符串库中的compareTo或compareToIgnoreCase方法。为了完成这项工作,将 isSmallerThan(value,arrayindex-1) 改为arrayindex-1。
发布于 2018-03-08 19:43:01
尝试使用String.CompareTo(String s)方法。它非常类似于您一直使用的比较运算符,除非它将计算为一个整数。
String str1 = "Cat";
String str2 = "Dog";
int sCompare = str1.CompareTo(str2);编辑:
为了清楚起见,在上述示例中,sCompare将计算为负值。
发布于 2018-03-08 20:05:21
使用compareTo()方法,insertion sort算法的实现如下所示:
class InsertionSorter {
public String[] sortArrayOfStrings(String[] array) {
for (int i = 1; i < array.length; i++) {
String element = array[i];
int j;
for (j = i - 1; j >= 0 && element.compareTo(array[j]) <= 0; j--)
array[j + 1] = array[j];
array[j + 1] = element;
}
return array;
}
}示例测试:
public class InsertionSorterTest {
@Test
public void shouldSortTwoLetterWords() {
String[] arr = {"zz", "bb", "cb", "ba", "za", "zb", "cz", "ab", "aa"};
String[] sortedArray = new InsertionSorter().sortArrayOfStrings(arr);
Assert.assertEquals(sortedArray, new String[]{"aa", "ab", "ba", "bb", "cb", "cz", "za", "zb", "zz"});
}
@Test
public void shouldSortLongerWords() {
String[] arr = {"bbz", "bba", "abz", "abc"};
String[] sortedArray = new InsertionSorter().sortArrayOfStrings(arr);
Assert.assertEquals(sortedArray, new String[]{"abc", "abz", "bba", "bbz"});
}
}https://stackoverflow.com/questions/49181083
复制相似问题