排序一个数组 [F,a,f,h,A,g,K],要求输出[A,a,F,f,g,h,K]

这是我同学的一道面试题，怎么没人写呢？
这里面的比较最主要是a和A的比较，如果用hashcode的话，a的小于f的但是也小于A的，所以有点难度。

您发错版块儿了。。
这个题我用了TreeSet，用比较器还是很方便的。

1. public class ArraySort {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 String[] arr = {"F","a","f","h","A","g","K"};
   
5.                 String str1=sort(arr);
   
6.                 System.out.println(str1);
   
7.                 }
   
8.         
   
9.         public static String sort(String[] arr){
   
10.                 TreeSet<String> ts = new TreeSet<String>(new Comparator<String>(){
    
11.                         public int compare(String s1, String s2) {
    
12.                                 //这里可以把两个字母都转换为小写进行比较，如果相同，num为0的话，再进行大小写排序
    
13.                                 int num = s1.toLowerCase().compareTo(s2.toLowerCase());
    
14.                                 if(num==0)
    
15.                                         return s1.compareTo(s2);
    
16.                                 return num;
    
17.                         }
    
18.                         
    
19.                 });
    
20.                 for(String s : arr){
    
21.                         ts.add(s);
    
22.                 }
    
23.                 return ts.toString();//我返回的是字符串
    
24.                
    
25.                
    
26.         }
    
27.                
    
28. }

复制代码

结果为：[A, a, F, f, g, h, K]

王亚男 发表于 2012-7-6 22:14
您发错版块儿了。。
这个题我用了TreeSet，用比较器还是很方便的。结果为：[A, a, F, f, g, h, K] ...

这思路我怎么也想不起来

杨朔 发表于 2012-7-6 19:35
这是我同学的一道面试题，怎么没人写呢？
这里面的比较最主要是a和A的比较，如果用hashcode的话，a的小于f ...

对于你这个想法，我自己也写了一个，虽然能够实现，但是过程有些不如意
其中有一个问题，后面有标注红色字体

1. import java.util.*;
   
2. class SortArray
   
3. {
   
4.         public static void main(String[] args)
   
5.         {
   
6.                 String[] arr = {"F","a","f","h","A","g","K"};
   
7.                 //定义一个新的整型数组 存放字符串数组每个元素所对应的值
   
8.                 int[] arr1 = new int[arr.length];
   
9.                 for (int i=0; i<arr.length ;i++ )
   
10.                 {
    
11.                         //判断如果是大写字母的话，那么就在原有的hashCode的基础上加32变成相对应的小写
    
12.                         //并将得到的hashCode值 存入到arr1中
    
13.                         if (arr[i].hashCode()<97)
    
14.                         {
    
15.                                 arr1[i] = arr[i].hashCode()+32;
    
16.                         }else
    
17.                         {
    
18.                                 arr1[i] = arr[i].hashCode();
    
19.                         }
    
20.                 }
    
21.                 //对新的数组进行排序
    
22.                 Arrays.sort(arr1);
    
23.                 for (int i=0;i<arr.length ;i++ )
    
24.                 {
    
25.                         //如果数组中有两个相同的元素就把第一个元素大写，hashCode-32
    
26.                         //为了防止数组i+1越界 所以加一个防止越界的判断
    
27.                         if (i!=arr.length-1&&arr1[i]==arr1[i+1])
    
28.                         {
    
29.                                 arr1[i]-=32; //<FONT color=red>这步有点强行转化的过程，我觉得有点不合适，不能判断出两个小写的a到底哪一个A 转化过来的</FONT>
    
30.                       }
    
31.                         //把相对应的hashCode值转化成字母
    
32.                         System.out.println((char)arr1[i]);
    
33.                 }
    
34.         }        
    
35. }

复制代码

arr1-=32; //<FONT color=red>这步有点强行转化的过程，我觉得有点不合适，不能判断出两个小写的a到底哪一个A 转化过来的</FONT>
为啥代码里面没有效果 - -

突然发现一个问题，Arrays.sort() 可以对大小写进行排序，这让老夫情何以堪

1. String[] arr = {"F","a","f","h","A","g","K"};
   
2.                 Arrays.sort(arr);
   
3.                 for (int i=0; i<arr.length; i++)
   
4.                 {
   
5.                         System.out.println(arr[i]);
   
6.                 }

复制代码

这样就搞定了

楼上的方法是不行的
在java内部 Arrays.sort(arr);方法是将字符转化为相应的二进制编码-------也就是ASCII码进行比较 JVM并分不清字母大小写 A和a在他那里只是65和97的区别
所以打印结果是  
A
F
K
a
f
g
h

可以看见并未区分大小写

亚男的办法很好，但如果急了想不出来，告诉你一个没办法的办法，
1.将字符数组存入一个二维数组中，a[x][y],x存字符数组中的值，全转成大写，y记录大小写标记，
2.先排序一次（什么排序都行），
3.再用冒泡排序一次（相邻比较，相等就根据y脚标决定换不换位）
4.根据y脚标转换大小写。{:soso_e120:}

import java.util.Arrays;
import java.util.HashMap;
public class TestSort {

        /**
         * @param args
         */
        public static void main(String[] args) {
                // TODO Auto-generated method stub
        //只排序一次，不用大小写转换
                String[] arr = {"F","a","f","h","A","g","K"};
                double arrTemp [] = new double[arr.length];
                HashMap<Double, String> map = new HashMap<Double, String>();
                for(int i=0;i<arr.length;i++)
                {
                        double temp = arr[i].hashCode();
                    if(temp>=97)
                    {
                            arrTemp[i] = temp-31.5;
                    }else
                    {
                            arrTemp[i] = temp;
                    }
                        map.put(arrTemp[i], arr[i]);         
                }
                Arrays.sort(arrTemp);
                for(int i=0;i<arr.length;i++)
                {
                        arr[i] = map.get(arrTemp[i]);
                }
                for(String str:arr)
                {
                        System.out.print(str);
                }       
        }          
}

王亚男 发表于 2012-7-6 22:14
您发错版块儿了。。
这个题我用了TreeSet，用比较器还是很方便的。结果为：[A, a, F, f, g, h, K] ...

其实，这里用TreeSet 集合 在某些情况 下是不合适的。
因为 Set 集合家族，决定了，元素必须是唯一，不能重复。

当我要排序 [F,a,f,h,A,g,K,A]时，用上面的方法就少掉了一个元素了。

这个题目，一开始看到时。有两种思路：
一种是想起了
     Arrays.sort(xx)  方法，但是似乎用sort 解决不了大写与小写排序放在一起，大写放前面。
  
另一种是，自己写双for 循环，用选择或冒泡排序法来搞定。
但效率似乎有点低了。

但一想想，不对既然sun ，提供了Arrays.sort(xx)方法，应该会提供另一个方法，让开发者来决定采用哪种比较来排序数组元素啊。
带着疑问，查看API文档， 呵呵， 果然不出所料。

static <T> void  sort(T[] a, Comparator<? super T> c)
根据指定比较器产生的顺序对指定对象数组进行排序。

用了，这个方法，这个题目还不是小菜一碟了。呵呵。

下面给出，两种思想的具体代码：

1. 
   
2. import java.util.*;
   
3. public class SortDemo
   
4. {
   
5.         public static void main(String[] args)
   
6.         {
   
7.                 String[] str1 = {"F","a","f","h","A","g","K","A"};
   
8.          System.out.println("------------采用Arrays.sort(xx,Comparator<T>)排序-------");
   
9.                 sort1(str1);
   
10.          printArr(str1);
    
11.   
    
12.   System.out.println();
    
13.          String[] str2 = {"F","a","f","h","A","g","K","A"};
    
14.   System.out.println("------------采用笨拙的选择排序-------");
    
15.          sort1(str2);
    
16.   printArr(str2);
    
17.   
    
18.         }
    
19. public static void sort1(String[] str){
    
20.   Arrays.sort(str,new Comparator<String>(){
    
21.    public int compare(String str1,String str2){
    
22.     int num = str1.toUpperCase().compareTo(str2.toUpperCase());
    
23.     if(0==num)
    
24.      num = str1.compareTo(str2);
    
25.     return num ;
    
26.    }
    
27.    
    
28.   });
    
29. }
    
30. 
    
31. public static void sort2(String[] str){
    
32.   
    
33.   for(int i=0;i<str.length-1;i++){
    
34.    for(int j=i+1;j<str.length;j++){
    
35.     if(str[i].toUpperCase().compareTo(str[j].toUpperCase())>0 ){
    
36.      sawp(i,j,str);
    
37.     }else if(str[i].toUpperCase().compareTo(str[j].toUpperCase())==0 ){
    
38.      if(str[i].compareTo(str[j])>0 )
    
39.       sawp(i,j,str);
    
40.     }
    
41.    }
    
42.   }
    
43. }
    
44. private static void sawp(int i, int j, String[] str){
    
45.   String temp = str[i];
    
46.   str[i] = str[j];
    
47.   str[j] = str[i];
    
48. }
    
49. private static void printArr(String[] str){
    
50.   int i =0 ;
    
51.   for(String s:str){
    
52.    if(i>0)
    
53.     System.out.print(",");
    
54.    System.out.print(s);
    
55.    i++;
    
56.   }
    
57. }
    
58.   
    
59. }
    

复制代码

看来，API中方法还是很强大的，通常我们不可能知道所有API中的方法。

个人觉得，学习时也没有必要背下API中的所有方法，主要还是有需求用到的时候，带的疑问来查API中的方法。

这样，下次遇到同样的问题，还不是手到擒来。


忘记上真理图了，呵呵。

public class Sort {

public static void main(String[] args) {
  String[] d= new String[]{"F","a","f","h","A","g","K"};
  String m = null;
  for(int x=0 ; x< d.length ; ++x){
            for(int y=0; y <d.length - x - 1; ++y){
                if(compare(d[y], d[y+1])>0){
                    tmp = d[y];
                    d[y] = d[y + 1];
                    d[y + 1] = tmp;
                }
            }
  }
  
  for(String str:d) {
   System.out.println(str);
  }
}

public static int compare(String c1, String c2) {
  if(c1.toLowerCase().compareTo(c2.toLowerCase()) != 0)
   return c1.toLowerCase().compareTo(c2.toLowerCase());
  if(c1.equals(c2))
   return 0;
  else
   return c1.compareTo(c2);
}
}

陈淑飞 发表于 2012-7-14 18:15
其实，这里用TreeSet 集合 在某些情况 下是不合适的。
因为 Set 集合家族，决定了，元素必须是唯一，不能 ...

兄台果然思维活跃！
不过，Set虽然要求元素是唯一的，但判断元素唯一的方式却是由我们自己编写的。也就是说，我们可以让它把我们主观判断为两个相同的元素认为其并不相同。
所以本例中，只需要稍微修改下compare即可：

1. public class ArraySort {
   
2. 
   
3. public static void main(String[] args) {
   
4. String[] arr ={"F","a","f","h","A","g","K","A"};
   
5. String str1=sort(arr);
   
6. System.out.println(str1);
   
7. }
   
8. 
   
9. public static String sort(String[] arr){
   
10. TreeSet<String> ts = new TreeSet<String>(new Comparator<String>(){
    
11. public int compare(String s1, String s2) {
    
12. //这里可以把两个字母都转换为小写进行比较，如果相同，num为0的话，再进行大小写排序
    
13. int num = s1.toLowerCase().compareTo(s2.toLowerCase());
    
14. if(num==0){
    
15. num=s1.compareTo(s2);
    
16. if(num==0) //如果num还为0的话直接返回-1就可以了。
    
17. return -1;
    
18. }
    
19. return num;
    
20. }
    
21. 
    
22. });
    
23. for(String s : arr){
    
24. ts.add(s);
    
25. }
    
26. return ts.toString();//我返回的是字符串
    
27. 
    
28. 
    
29. }
    
30. 
    
31. }

复制代码

如此，本例中打印的结果就为：
[A, A, a, F, f, g, h, K]

但就代码的简洁性与可读性，带有比较器的Arrays.sort的确是最佳选择。