java 核心技术-12版 卷Ⅰ- 3.10.6 数组排序

要想对数值型数组进行排序，可以使用 Arrays 类中的 sort 方法:

int[] a = new int[10000];

//...

Arrays.sort(a);

这个方法使用了优化的快速排序(QuickSort) 算法。快速排序算法对于大多数数据集都很高效。Arrays 类还提供了另外一些很便捷的方法，在这一节最后的 API注释中将介绍这些方法。

程序清单 3-7 中的程序具体使用了数组，它会为一个抽彩游戏生成一个随机的数字组合。例如，假如从 49 个数字中抽取 6 个数，那么程序可能的输出结果为：

Bet the following combination. It'll make you rich!

4

7

8

19

30

44

要想选择这样一组随机的数字，首先将值 1,2,,n 填入数组 numbers 中：

int[] numbers = new int[n]
for (int i=0; i< numbers.length; i++)
	numbers[il =i + l;

第二个数组存放抽取出来的数:

int[] result = new int[k];

现在可以开始抽取k个数。Math.random方法将返回一个0 到1 之间（包含0，不包含1）的随机浮点数。用n乘以这个浮点数，可以得到从0到n-1 之间的一个随机数。

int r = (int) (Math.random() * n);

下面将result 的第i个元素设置为该索引对应的数（numbers[r]），最初是 r +1 , 但正如所看到的，numbers 数组的内容在每一次抽取之后都会发生变化。

result[i] = numbers[r] ;

现在，必须确保不会再次抽到那个数，因为所有抽彩数字必须各不相同。因此，这里用数组中的最后一个数覆盖number[r],并将n 减 1.

numbers[r] = numbers[n-1];

n -- ;

关键在于每次抽取的都是索引，而不是实际的值。这个索引指向一个数组，其中包含尚未抽取过的值。

在抽取了k个数之后，可以对 result 数组进行排序，来得到更美观的输出：

Arrays.sort(result);

for(int r : result)

    System.out.println(r);

程序清单 3-7 LotteryDrawing.java

import java.util.*;

/**
 * This program demonstrates array manipulation.
 * @version 1.20 2004-02-10
 * @author Cay Horstmann
 */
public class LotteryDrawing
{
   public static void main(String[] args)
   {
      Scanner in = new Scanner(System.in);

      System.out.print("How many numbers do you need to draw? ");
      int k = in.nextInt();

      System.out.print("What is the highest number you can draw? ");
      int n = in.nextInt();

      // fill an array with numbers 1 2 3 . . . n
      int[] numbers = new int[n];
      for (int i = 0; i < numbers.length; i++)
         numbers[i] = i + 1;

      // draw k numbers and put them into a second array
      int[] result = new int[k];
      for (int i = 0; i < result.length; i++)
      {
         // make a random index between 0 and n - 1
         int r = (int) (Math.random() * n);

         // pick the element at the random location
         result[i] = numbers[r];

         // move the last element into the random location
         numbers[r] = numbers[n - 1];
         n--;
      }

      // print the sorted array
      Arrays.sort(result);
      System.out.println("Bet the following combination. It'll make you rich!");
      for (int r : result)
         System.out.println(r);
   }
}

API: java.util.Arrays (since jdk 1.2)

• static String toString(xxx[] a) jdk5 ：返回一个字符串，其中包含a 中的元素，这些元素用中括号包围，并用逗号包围。在这个方法以及后面的方法中，数组元素类型 xxx 可以是 int 、long、short、char、byte、boolean、float、或double。
• static xxx[] copyOf(xxx[] a, int end) jdk6:
• static xxx[] copyOfRange(xxx[] a, int start , int end) jdk6: 返回与a类型相同的一个数组，其长度为end 或 end - start，并填入a的值。如果 end 大于 a.length， 结果会填充0 或false 的值。
• static void sort(xxx[] a) 使用优化的快速排序算法对数组进行排序。
• static int binarySearch(xxx[] a, xxx v)
• static int binarySearch(xxx[] a, int start ,int end , xxx v) jdk6 : 使用二分查找在有序数组a 中查找v。如果找到v 返回其索引；否则返回一个负数值r 。 -r-1 是v应插入的位置（为保持a 有序）
• static void fill( xxx[] a, xxx v) 将数组的所有元素设置为 v。
• static boolean equals( xxx[] a, xxx[] b)如果两个数组长度相同，并且相同索引对应的元素都相同，返回true。否则返回 false