黑马程序员技术交流社区

标题: 求解？关于比较器的排序问题？急急急！ [打印本页]

---

作者: HeiMaYSL    时间: 2012-5-14 13:29
标题: 求解？关于比较器的排序问题？急急急！
import java.util.*;
class test2
{
//打印方法
public static void sop(Object obj)
{
  System.out.println(obj);
}
public static void main(String[] args)
{
  List<String> list=new ArrayList<String>();
  list.add("fgdsd");
  list.add("dfs");
  list.add("asdfgg");
  list.add("zdfs");
  list.add("asd");
  sop("原集合："+list);
  //如果list集合中没有bbbb这个元素，就返回(-(插入点)-1);
  //总结：只要返回了负数，证明了这个元素在集合是不存在的。
  int index1=Collections.binarySearch(list,"bbbb",new Stringcomparator());
  sop("用binarySearch方法：index="+index1);
  //有折半的方法和binarySearch的效果一样。
  int index2=zheban(list,"bbbb",new Stringcomparator());
  sop("用折半的方法求插入的位置-1：index1="+index2);
}
//折半方法，返回的是要在的字符串插入集合中的角标位置。
public static int zheban(List<String> list,String key,Comparator<String> cmp)
{
  //定义三个变量，分别为最小值，最大值和中间值，
  int max,min,mid;
  //最大值为，集合的大小-1;
  max=list.size()-1;
  //最小值为list的最小索引是0
  min=0;
  
  while (min<=max) //如果最小值小于或者等于最大值；就可以折半
  {
   mid=(max+min)>>1;  //把最大值和最小值的和右移两位，就等于和除以2
   String str=list.get(mid); //得到集合的中间值角标的元素。
   //用这个中间值和传进来的字符串比较一下。compareTo的返回值为正数，负数和0；
   //注意：在这里要实现比较器的方法compare方法。这里就多了一个参数
   int num=cmp.compare(str,key);  
   //如果如果大于0.说明str大于key。那么key就小于中间值。key就往左移动。
   //那么最大值就等于中间值-1。
   if(num>0)  
    max=mid-1;
   //如果小于0，说明str小于key，那么key就大于中间值。key就往右移动。
   //那么，最小值就等于中间值-1；就是最小值要减少一位。
   else if(num<0)  
    min=mid+1;
   //如果等于0，说明这个就是中间值。就返回中间值。
   else
    return mid;
  }
  //如果返回：-min-1;就是和binarySearch的功能一样了。如果返min就是插入点。
  return -min-1;  
}
}

//实现Comparator比较器，复写compare方法，实现自己特有的字符串长度比较方式。
class Stringcomparator implements Comparator<String>
{
public int compare(String s1,String s2)  //注意他的返回值为正数，负数和0
{
  if(s1.length()>s2.length())
   return 1;
  if(s1.length()<s2.length())
   return -1;
  return s1.compareTo(s2);  //如果为0 ，就是长度相等了，就比较它们的字符串。compareTo是字符串特有的比较法。
}
}


打印结果为：

问：为什么我明明实现了长度比较器，也调用了，怎么打印时，没有按照长度排序呢？

---

作者: 任睦强    时间: 2012-5-14 15:03
import java.util.*;
class test2
{
//打印方法
public static void sop(Object obj)
{
  System.out.println(obj);
}
public static void main(String[] args)
{
  List<String> list=new ArrayList<String>();
  list.add("fgdsd");
  list.add("dfs");
  list.add("asdfgg");
  list.add("zdfs");
  list.add("asd");
  sop("原集合："+list);
  //如果list集合中没有bbbb这个元素，就返回(-(插入点)-1);
  //总结：只要返回了负数，证明了这个元素在集合是不存在的。
  int index1=Collections.binarySearch(list,"bbbb",new Stringcomparator());
  sop("用binarySearch方法：index="+index1);
  //有折半的方法和binarySearch的效果一样。
  int index2=zheban(list,"bbbb",new Stringcomparator());
  sop("用折半的方法求插入的位置-1：index1="+index2);
}
//折半方法，返回的是要在的字符串插入集合中的角标位置。
public static int zheban(List<String> list,String key,Stringcomparator cmp)//这样声明才能找到你自己实现的接口
{
  //定义三个变量，分别为最小值，最大值和中间值，
  int max,min,mid;
  //最大值为，集合的大小-1;
  max=list.size()-1;
  //最小值为list的最小索引是0
  min=0;
  
  while (min<=max) //如果最小值小于或者等于最大值；就可以折半
  {
   mid=(max+min)>>1;  //把最大值和最小值的和右移两位，就等于和除以2
   String str=list.get(mid); //得到集合的中间值角标的元素。
   //用这个中间值和传进来的字符串比较一下。compareTo的返回值为正数，负数和0；
   //注意：在这里要实现比较器的方法compare方法。这里就多了一个参数
   int num=cmp.compare(str,key);  
   //如果如果大于0.说明str大于key。那么key就小于中间值。key就往左移动。
   //那么最大值就等于中间值-1。
   if(num>0)  
    max=mid-1;
   //如果小于0，说明str小于key，那么key就大于中间值。key就往右移动。
   //那么，最小值就等于中间值-1；就是最小值要减少一位。
   else if(num<0)  
    min=mid+1;
   //如果等于0，说明这个就是中间值。就返回中间值。
   else
    return mid;
  }
  //如果返回：-min-1;就是和binarySearch的功能一样了。如果返min就是插入点。
  return -min-1;  
}
}

//实现Comparator比较器，复写compare方法，实现自己特有的字符串长度比较方式。
class Stringcomparator implements Comparator<String>
{
public int compare(String s1,String s2)  //注意他的返回值为正数，负数和0
{
  if(s1.length()>s2.length())
   return 1;
  if(s1.length()<s2.length())
   return -1;
  return s1.compareTo(s2);  //如果为0 ，就是长度相等了，就比较它们的字符串。compareTo是字符串特有的比较法。
}
}

---

作者: HeiMaYSL    时间: 2012-5-14 15:12

任睦强 发表于 2012-5-14 15:03
import java.util.*;
class test2
{

你说的那样不行啊。我试过了。会出现异常的。

---

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

黑马程序员IT技术论坛 X3.2