日期：2011-03-22 16:17:00 来源：本站整理

java的排序和搜索[Java编程]

赞助商链接

分享到： QQ空间新浪微博腾讯微博人人网

　　本文“java的排序和搜索[Java编程]”是由七道奇为您精心收集，来源于网络转载，文章版权归文章作者所有，本站不对其观点以及内容做任何评价，请读者自行判断，以下是其具体内容：
Java 1.2增添了自己的一套实用工具,可用来对数组或列表举行布列和搜索.这些工具都属于两个新类的“静态”办法.这两个类辨别是用于排序和搜索数组的Arrays,以及用于排序和搜索列表的Collections.

1. 数组
Arrays类为全部基本数据范例的数组供应了一个过载的sort()和binarySearch(),它们亦可用于String和Object.下面这个例子显示出若何排序和搜索一个字节数组（其他全部基本数据范例都是近似的）以及一个String数组:

//: Array1.java
// Testing the sorting & searching in Arrays
package c08.newcollections;
import java.util.*;

public class Array1 {
  static Random r = new Random();
  static String ssource = 
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
    "abcdefghijklmnopqrstuvwxyz";
  static char[] src = ssource.toCharArray();
  // Create a random String
  public static String randString(int length) {
    char[] buf = new char[length];
    int rnd;
    for(int i = 0; i < length; i++) {
      rnd = Math.abs(r.nextInt()) % src.length;
      buf[i] = src[rnd];
    }
    return new String(buf);
  }
  // Create a random array of Strings:
  public static 
  String[] randStrings(int length, int size) {
    String[] s = new String[size];
    for(int i = 0; i < size; i++)
      s[i] = randString(length);
    return s;
  }
  public static void print(byte[] b) {
    for(int i = 0; i < b.length; i++)
      System.out.print(b[i] + " ");
    System.out.println();
  }
  public static void print(String[] s) {
    for(int i = 0; i < s.length; i++)
      System.out.print(s[i] + " ");
    System.out.println();
  }
  public static void main(String[] args) {
    byte[] b = new byte[15];
    r.nextBytes(b); // Fill with random bytes
    print(b);
    Arrays.sort(b);
    print(b);
    int loc = Arrays.binarySearch(b, b[10]);
    System.out.println("Location of " + b[10] +
      " = " + loc);
    // Test String sort & search:
    String[] s = randStrings(4, 10);
    print(s);
    Arrays.sort(s);
    print(s);
    loc = Arrays.binarySearch(s, s[4]);
    System.out.println("Location of " + s[4] +
      " = " + loc);
  }
} ///:~

类的第一部份包含了用于产生随机字串对象的实用工具,可供挑选的随机字母保存在一个字符数组中.randString()返回一个肆意长度的字串;而readStrings()成立随机字串的一个数组,同时给定每个字串的长度以及但愿的数组大小.两个print()办法简化了对示范数组的显示.在main()中,Random.nextBytes()用随机挑选的字节填充数组自变量（没有对应的Random办法用于成立其他基本数据范例的数组）.得到一个数组后,便可发现为了履行sort()大概binarySearch(),只需发出一次办法调用便可.与binarySearch()有关的还有一个重要的告诫:若在履行一次binarySearch()之前不调用sort(),便会发生不可猜测的行为,此中乃至包含无限循环.
对String的排序以及搜索是类似的,但在运路程序的时刻,我们会注意到一个风趣的现象:排序服从的是字典次序,亦即大写字母在字符集合位于小写字母的前面.因此,全部大写字母都位于列表的最前面,背面再跟上小写字母——Z竟然位于a的前面.仿佛连电话簿也是这样排序的.

2. 可对比与对比器
但假如我们不满意这一排序方法,又该若何处理呢?比方本书背面的索引,假如必须对以A或a开首的词条辨别到两处地方查看,那么必定会使读者颇不耐烦.
若想对一个Object数组举行排序,那么必须办理一个问题.按照什么来断定两个Object的次序呢?不幸的是,最初的Java计划者并不认为这是一个重要的问题,不然就已经在根类Object里定义它了.这样造成的一个后果就是:必须从外部举行Object的排序,并且新的调集库供应了实现这一操作的尺度方法（最抱负的是在Object里定义它）.
针对Object数组（以及String,它当然属于Object的一种）,可以利用一个sort(),并令其采取另一个参数:实现了Comparator接口（即“对比器”接口,新调集库的一部份）的一个对象,并用它的单个compare()办法举行对比.这个办法将两个预备对比的对象作为自己的参数利用——若第一个参数小于第二个,返回一个负整数;若相等,返回零;若第一个参数大于第二个,则返回正整数.基于这一法则,上述例子的String部份便可重新写过,令其举行真正按字母次序的排序:

//: AlphaComp.java
// Using Comparator to perform an alphabetic sort
package c08.newcollections;
import java.util.*;

public class AlphaComp implements Comparator {
  public int compare(Object o1, Object o2) {
    // Assume it's used only for Strings...
    String s1 = ((String)o1).toLowerCase();
    String s2 = ((String)o2).toLowerCase();
    return s1.compareTo(s2);
  }
  public static void main(String[] args) {
    String[] s = Array1.randStrings(4, 10);
    Array1.print(s);
    AlphaComp ac = new AlphaComp();
    Arrays.sort(s, ac);
    Array1.print(s);
    // Must use the Comparator to search, also:
    int loc = Arrays.binarySearch(s, s[3], ac);
    System.out.println("Location of " + s[3] +
     " = " + loc);
  }
} ///:~

通过造型为String,compare()办法会举行“表示”性的测试,保证自己操作的只能是String对象——运行期系统会捕捉任何不对.将两个字串都逼迫换成小写情势后,String.compareTo()办法会产生预期的后果.
若用自己的Comparator来举行一次sort(),那么在利用binarySearch()时必须利用那个相同的Comparator.
Arrays类供应了另一个sort()办法,它会采取单个自变量:一个Object数组,但没有Comparator.这个sort()办法也必须用一样的方法来对比两个Object.通过实现Comparable接口,它采取了赋予一个类的“自然对比办法”.这个接口含有单独一个办法——compareTo(),能辨别按照它小于、等于大概大于自变量而返回负数、零大概正数,从而实现对象的对比.下面这个例子简单地阐示了这一点:

//: CompClass.java
// A class that implements Comparable
package c08.newcollections;
import java.util.*;

public class CompClass implements Comparable {
  private int i;
  public CompClass(int ii) { i = ii; }
  public int compareTo(Object o) {
    // Implicitly tests for correct type:
    int argi = ((CompClass)o).i;
    if(i == argi) return 0;
    if(i < argi) return -1;
    return 1;
  }
  public static void print(Object[] a) {
    for(int i = 0; i < a.length; i++)
      System.out.print(a[i] + " ");
    System.out.println();
  }
  public String toString() { return i + ""; }
  public static void main(String[] args) {
    CompClass[] a = new CompClass[20];
    for(int i = 0; i < a.length; i++)
      a[i] = new CompClass(
        (int)(Math.random() *100));
    print(a);
    Arrays.sort(a);
    print(a);
    int loc = Arrays.binarySearch(a, a[3]);
    System.out.println("Location of " + a[3] +
     " = " + loc);
  }
} ///:~

当然,我们的compareTo()办法亦可按照实际情形增大复杂程度.

3. 列表
可用与数组相同的情势排序和搜索一个列表（List）.用于排序和搜索列表的静态办法包含在类Collections中,但它们拥有与Arrays中差不多的签名:sort(List)用于对一个实现了Comparable的对象列表举行排序;binarySearch(List,Object)用于查找列表中的某个对象;sort(List,Comparator)操纵一个“对比器”对一个列表举行排序;而binarySearch(List,Object,Comparator)则用于查找那个列表中的一个对象（注释⑨）.下面这个例子操纵了预先定义好的CompClass和AlphaComp来示范Collections中的各种排序工具:

//: ListSort.java
// Sorting and searching Lists with 'Collections'
package c08.newcollections;
import java.util.*;

public class ListSort {
  public static void main(String[] args) {
    final int SZ = 20;
    // Using "natural comparison method":
    List a = new ArrayList();
    for(int i = 0; i < SZ; i++)
      a.add(new CompClass(
        (int)(Math.random() *100)));
    Collection1.print(a);
    Collections.sort(a);
    Collection1.print(a);
    Object find = a.get(SZ/2);
    int loc = Collections.binarySearch(a, find);
    System.out.println("Location of " + find +
     " = " + loc);
    // Using a Comparator:
    List b = new ArrayList();
    for(int i = 0; i < SZ; i++)
      b.add(Array1.randString(4));
    Collection1.print(b);
    AlphaComp ac = new AlphaComp();
    Collections.sort(b, ac);
    Collection1.print(b);
    find = b.get(SZ/2);
    // Must use the Comparator to search, also:
    loc = Collections.binarySearch(b, find, ac);
    System.out.println("Location of " + find +
     " = " + loc);
  }
} ///:~

⑨:在本书写作时,已公布了一个新的Collections.stableSort(),可用它举行归并式排序,但还没有它的测试版问世.

这些办法的用法与在Arrays中的用法是完好一致的,只是用一个列表替换了数组.
TreeMap也必须按照Comparable大概Comparator对自己的对象举行排序.
　　以上是“java的排序和搜索[Java编程]”的内容，如果你对以上该文章内容感兴趣，你可以看看七道奇为您推荐以下文章：

利用Javascript实现网页水印(非图片水印)

Java开辟环境的搭建

Ubuntu java安装与配置

办理Ubuntu 10.04 Firefox3.6 Java浏览器插件不工作的问

Ubuntu重装后Java环境的设置

Sun Java进入Ubuntu 10.10软件中央

Ubuntu 10.10配置Java开辟环境

在Ubuntu 10.10中配置Java环境变量的办法

Ubuntu下Java环境的搭建

Ubuntu 10.04 下安装 Java, JRE

Ubuntu 10.04下的搭建SUN JAVA开辟环境

Ubuntu 12.04安装java7