黑马程序员技术交流社区

标题: 排序一个数组 [F,a,f,h,A,g,K],要求输出[A,a,F,f,g,h,K] [打印本页]

作者: 杨朔 时间: 2012-7-6 18:00
标题: 排序一个数组 [F,a,f,h,A,g,K],要求输出[A,a,F,f,g,h,K]
排序一个数组 [F,a,f,h,A,g,K],要求输出[A,a,F,f,g,h,K]

作者: 杨朔 时间: 2012-7-6 19:35
这是我同学的一道面试题，怎么没人写呢？
这里面的比较最主要是a和A的比较，如果用hashcode的话，a的小于f的但是也小于A的，所以有点难度。

作者: 王亚男 时间: 2012-7-6 22:14
您发错版块儿了。。
这个题我用了TreeSet，用比较器还是很方便的。

public class ArraySort {
public static void main(String[] args) {
String[] arr = {"F","a","f","h","A","g","K"};
String str1=sort(arr);
System.out.println(str1);
}
public static String sort(String[] arr){
TreeSet<String> ts = new TreeSet<String>(new Comparator<String>(){
public int compare(String s1, String s2) {
//这里可以把两个字母都转换为小写进行比较，如果相同，num为0的话，再进行大小写排序
int num = s1.toLowerCase().compareTo(s2.toLowerCase());
if(num==0)
return s1.compareTo(s2);
return num;
}
});
for(String s : arr){
ts.add(s);
}
return ts.toString();//我返回的是字符串
}
}

复制代码

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

作者: 杨朔 时间: 2012-7-7 12:27

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

这思路我怎么也想不起来

作者: 吴小东 时间: 2012-7-7 14:04
本帖最后由吴小东于 2012-7-7 14:09 编辑

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

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

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

复制代码

arr1-=32; //<FONT color=red>这步有点强行转化的过程，我觉得有点不合适，不能判断出两个小写的a到底哪一个A 转化过来的</FONT>
为啥代码里面没有效果 - -
作者: 吴小东 时间: 2012-7-7 14:17
突然发现一个问题，Arrays.sort() 可以对大小写进行排序，这让老夫情何以堪
String[] arr = {"F","a","f","h","A","g","K"};

Arrays.sort(arr);

for (int i=0; i<arr.length; i++)

{

System.out.println(arr[i]);

}
复制代码
这样就搞定了
作者: 付蛟龙 时间: 2012-7-8 00:54
楼上的方法是不行的
在java内部 Arrays.sort(arr);方法是将字符转化为相应的二进制编码-------也就是ASCII码进行比较 JVM并分不清字母大小写 A和a在他那里只是65和97的区别
所以打印结果是
A
F
K
a
f
g
h

可以看见并未区分大小写
作者: 黑马-李勇 时间: 2012-7-8 01:35
亚男的办法很好，但如果急了想不出来，告诉你一个没办法的办法，
1.将字符数组存入一个二维数组中，a[x][y],x存字符数组中的值，全转成大写，y记录大小写标记，
2.先排序一次（什么排序都行），
3.再用冒泡排序一次（相邻比较，相等就根据y脚标决定换不换位）
4.根据y脚标转换大小写。{:soso_e120:}
作者: 位雪 时间: 2012-7-11 20:25
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-14 18:15
本帖最后由陈淑飞于 2012-7-14 18:23 编辑

王亚男发表于 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)
根据指定比较器产生的顺序对指定对象数组进行排序。

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

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

import java.util.*;

public class SortDemo

{

      public static void main(String[] args)

      {

            String[] str1 = {"F","a","f","h","A","g","K","A"};

      System.out.println("------------采用Arrays.sort(xx,Comparator<T>)排序-------");

            sort1(str1);

      printArr(str1);



  System.out.println();

      String[] str2 = {"F","a","f","h","A","g","K","A"};

  System.out.println("------------采用笨拙的选择排序-------");

      sort1(str2);

  printArr(str2);



      }

public static void sort1(String[] str){

  Arrays.sort(str,new Comparator<String>(){

public int compare(String str1,String str2){

int num = str1.toUpperCase().compareTo(str2.toUpperCase());

if(0==num)

   num = str1.compareTo(str2);

return num ;

}

  });

}

public static void sort2(String[] str){



  for(int i=0;i<str.length-1;i++){

for(int j=i+1;j<str.length;j++){

if(str[i].toUpperCase().compareTo(str[j].toUpperCase())>0 ){

   sawp(i,j,str);

}else if(str[i].toUpperCase().compareTo(str[j].toUpperCase())==0 ){

   if(str[i].compareTo(str[j])>0 )

   sawp(i,j,str);

}

}

  }

}

private static void sawp(int i, int j, String[] str){

  String temp = str[i];

  str[i] = str[j];

  str[j] = str[i];

}

private static void printArr(String[] str){

  int i =0 ;

  for(String s:str){

if(i>0)

System.out.print(",");

System.out.print(s);

i++;

  }

}



}

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

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

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

忘记上真理图了，呵呵。

排序.jpg (16.65 KB, 下载次数: 67)

下载附件

2012-7-14 18:22 上传

作者: 刘俊佳 时间: 2012-7-14 22:41
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-15 01:25
本帖最后由王亚男于 2012-7-15 01:50 编辑

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

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

public static void main(String[] args) {

String[] arr ={"F","a","f","h","A","g","K","A"};

String str1=sort(arr);

System.out.println(str1);

}

public static String sort(String[] arr){

TreeSet<String> ts = new TreeSet<String>(new Comparator<String>(){

public int compare(String s1, String s2) {

//这里可以把两个字母都转换为小写进行比较，如果相同，num为0的话，再进行大小写排序

int num = s1.toLowerCase().compareTo(s2.toLowerCase());

if(num==0){

num=s1.compareTo(s2);

if(num==0) //如果num还为0的话直接返回-1就可以了。

return -1;

}

return num;

}

});

for(String s : arr){

ts.add(s);

}

return ts.toString();//我返回的是字符串

}

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

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

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2