数组处理

数组相等的条件下不仅要求数组元素的个数必须相等，而且要求对应位置的元素也相等，Arrays 类提供了 equals() 方法比较整个数组。

Arrays.equals(arrayA, arrayB);

Arrays 类提供了一个 fill() 方法，可以在指定位置进行数值填充。 fill() 方法虽然可以填充数组，但是它的功能有限制，只能使用同一个数值进行填充。

Arrays.fill(array, value);

其中， array 表示数组， value 表示填充的值。

查找数组是指从数组中查询指定位置的元素，或者查询某元素在指定数组中的位置。

使用 Arrays 类的 binarySearch() 方法可以实现数组的查找，该方法可使用二分搜索法指定数组，以获得指定对象，该方法返回要搜索元素的索引值。

binarySearch() 方法有多种重载形式来满足不同类型数组的查找需要，常用的重载形式有两种。

binarySearch(Object[] arr, Object key);
// OR
binarySearch(Object[] arr, int fromIndex, int toIndex, Object key);

如果 key 包含在数组中，则返回搜索值的索引；否则返回 -1 或 -插入点 。插入点指搜索键将要插入数组的位置，即第一个大于此键的元素索引。

*注：在进行数组查询之前，必须对数组进行排序（可以使用 sort() 方法）。如果没有对数组进行排序，则结果是不确定的。如果数组包含多个带有指定值的元素，则无法确认找到的是哪一个。

所谓复制数组，是指将一个数组中的元素在另一个数组中进行复制。

在 Java 中实现数组复制分别有以下 4 种方法：

• Arrays 类的 copyOf() 方法；
• Arrays 类的 copyOfRange() 方法；
• System 类的 arraycopy() 方法；
• Object 类的 clone() 方法。

1. 使用 copyOf() 方法和 copyOfRange() 方法

copyOf() 方法是复制数组至指定长度， copyOfRange() 方法则将指定数组的指定长度复制到一个新数组中。

Arrays.copyOf(dataType[] srcArray, int length);

其中， srcArray 表示要进行复制的数组， length 表示复制后的新数组的长度。

使用这种方法复制数组时，默认从原数组的第一个元素（索引值为 0 ）开始复制，目标数组的长度为 length 。如果 length 大于 srcArray.length ，则目标数组中采用默认值填充；如果 length 小于 srcArray.length ，则复制到第 length 个元素（索引值为 length - 1 ）即止。

*注意：目标数组如果已经存在，将会被重构。

Arrays.copyOfRange(dataType[] srcArray, int startIndex, int endIndex)

其中：

• srcArray 表示原数组；
• startIndex 表示开始复制的起始索引，目标数组中将包含起始索引对应的元素，另外， startIndex 必须在 0 到 srcArray.length 之间；
• endIndex 表示终止索引，目标数组中将不包含终止索引对应的元素， endIndex 必须大于等于 startIndex ，可以大于 srcArray.length ，如果大于 srcArray.length ，则目标数组中使用默认值填充。

2. 使用 arraycopy() 方法

arraycopy() 方法位于 java.lang.System 类中，其语法形式如下：

System.arraycopy(dataType[] arcArray, int srcIndex, int destArray, int destIndex, int length)

其中：

• srcArray 表示原始数组；
• srcIndex 表示开始复制的起始索引；
• destArray 表示目标数组；
• destIndex 表示目标数组中的起始索引；
• length 表示要复制的数组的长度。

使用此方法复制数组时， length+srcIndex 必须小于等于 srcArray.length ，同时 length+destIndex 必须小于等于 destArray.length 。

*注：目标数组必须已经存在，且不会被重构，相当于替换目标数组中的部分元素。

3. 使用 clone() 方法

clone() 方法也可以实现复制数组，该方法是类 Object 中的方法，可以创建一个有单独内存空间的对象。

clone() 方法的返回值是 Object 类型，要使用强制类型转换为适当的类型。示例语句如下：

1: int[] targetArray = (int[])sourceArray.clone();

*注：目标数组如果已经存在，将会被重构。

*注：以上几种方法都是浅拷贝。浅拷贝只是复制了对象的引用地址，两个对象指向同一个内存地址，修改其中任意的值，另一个值都会随之变化；深拷贝是将对象及值复制过来，两个对象修改其中任意的值，另一个值不会改变。

Java 语言中使用 Arrays 类提供的 sort() 方法来对数组进行排序。

1. 升序

使用 java.util.Arrays 类中的 sort() 方法对数组进行升序：

1. 导入 java.util.Arrays 包；
2. 使用 Arrays.sort(数组名) 语法对数组进行排序，排序规则是从小到大，即升序。

2. 降序

在 Java 语言中使用 sort() 实现降序两种方法。

2.1 利用 Collections.reverseOrder() 方法（Collections 是一个包装类）

1: public static void main(String[] args) {
2:     Integer[] arr = {9, 8, 7, 2, 3, 4, 1, 0, 6, 5}; // 数组类型为 Integer
3:     Arrays.sort(arr, Collections.reverseOrder());
4: 
5:     for (int item : arr) {
6:         System.out.print(item + " ");
7:     }
8: }
9: // → 9 8 7 6 5 4 3 2 1 0

2.2 实现 Comparator 接口的复写 compare() 方法

 1: public class Test {
 2:     public static void main(String[] args) {
 3:         // 注意，要想改变默认的排列顺序，不能使用基本类型（int, double, char）而要使用它们对就的类
 4:         Integer[] arr = {9, 8, 7, 2, 3, 4, 1, 0, 6, 5};
 5:         // 定义一个自定义类 MyComparator 的对象
 6:         Comparator cmp = new MyComparator();
 7: 
 8:         Array.sort(arr, cmp);
 9:         for (int item : arr) {
10:             System.out.print(item + " ");
11:         }
12:     }
13: }
14: 
15: // 实现 Comparator 接口
16: class MyComparator implements Comparator<Integer> {
17:     @Override
18:     public int compare(Integer o1, Integer o2) {
19:         // 如果 o1 小于 o2 ，就返回正值；
20:         // 如果 o1 大于 o2 ，就返回负值；
21:         // 如此，颠倒一下，就可以实现降序排序了，反之即可自定义升序排序了
22:         return o2 - o1;
23:     }
24: }
25: 
26: // → 9 8 7 6 5 4 3 2 1 0

*注：使用以上两种方法时，数组必须是包装类型，否则编译不通过。

i.e. Bubble Sort

冒泡排序的 基本思想 是：对比相邻的元素值，如果满足条件就交换元素值，把较小的元素值移到数组前面，把大的元素值移动到数组后面（也就是交换两个元素的位置），这样数组就像气泡一样从底部上升到顶部。

冒泡排序的算法比较简单，排序的结果稳定，但时间效率不太高。

Java 中的冒泡排序在双层循环中实现，其中外层循环控制排序轮数，总循环次数为要排序数组的长度减 1 ；而内层循环主要用于对比相邻元素的大小，以确定是否交换位置，对比和交换次数依排序轮数而减少。

来看个例子吧。

 1: public static void main(String[] args) {
 2:     double[] score = {80, 78, 92, 65, 59, 100};
 3: 
 4:     for (int i = 0; i < score.length - 1; i++) {
 5:         // 比较相信两个元素，较大的数往后冒泡
 6:         for (int j = 0; j < score.length - 1 - i; j++) {
 7:             if (score[j] > score[j + 1]) {
 8:                 double temp = score[j + 1];
 9:                 score[j + 1] = score[j];
10:                 score[j] = temp;
11:             }
12:         }
13:     }
14: 
15:     for (int s : score) {
16:         System.out.println(s);
17:     }
18: }
19: // → 59 65 78 80 92 100

i.e. Quick Sort

快速排序是对冒泡排序的一种改进，是一种排序执行效率很高的排序算法。

快速排序的 基本思想 ：通过一趟排序，将要排序的数据分隔成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此使整个数据变成有序序列。

具体做法：假设要对某个数组进行排序，首先需要任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它的前面，所有比它大的数都放到它的后面。这个过程称为一趟快速排序；递归调用此过程，即可实现数据的快速排序。

选择排序是指每一趟从待排序的数据中选出最大（或最小）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。