数组和排序算法的应用（附面试题）

定义和使用数组

数组是 Java 编程中最重要的数据结构之一，也是最基本的数据结构，Java 中常用集合 ArrayList、HashMap 数组结构用于内部实现。数组只能用于存储一种类型的集合，通过下标访问值中的所有元素。

有两种方式可以对数组进行声明，如整数数组，请参考以下代码：

• 方式一：int[] arr;
• 方式二：int arr[];

在大多数情况下，我们会使用第一种方法 int[] arr; 声明数组。

数组初始化

数组可使用 new int[n] 初始化，每个元素初始化为 0，声明了 n 个元素。也可以直接赋值，比如 new int[]{ 1,2,3... }，具体用法可参考以下代码：

// int[]初始化方法 arr = new int[5];// 二int[]初始模式 arr2 = new int[]{1, 2, 3, 4, 5};// 初始化模式二的延伸版可以省略 new int[] int[]直接赋值 arr3 = {1, 2, 3, 4, 5};

注意：在 Java 如果数组的初始化声明了数组的长度，则不能直接赋值。例如，int[] arr = new int[5]{1, 2, 3, 4, 5}; 编译器在给出初始化数组长度并赋值时，会报错，编译失败。

有三种常见的数组遍历方法：传统的 for 循环、for each 遍历、还有 JDK 8 中新增的 Lambda 表达式。具体实现请参考以下实例。

方法一：传统 for 循环

Integer[] arr = {2, 3, 6, 7, 9};// 方法一：传统 forfor (int i = 0; i < arr.length; i++) {  System.out.println(arr[i]);}

方式二：for each

Integer[] arr = {2, 3, 6, 7, 9};// 方式二：for eachfor (int i : arr) {  System.out.println(i);}

方式三：JDK 8 中的 Lambda 表达式

Integer[] arr = {2, 3, 6, 7, 9};// 方式三：jdk 8 LambdaArrays.asList(arr).forEach(x -> System.out.println(x));

其中 for each 写作方法更简单，也更不容易出错，不用担心数组的越界(大于元素的最大下标值)。

注：数组的访问是从 0 开始，而不是 1 开始，第一个元素的获取是 arr[0]，而非 arr[1]。

使用的是数组复制 Arrays.copyof() 具体实现方法请参考以下代码：

int[] arr = {3, 4, 9};int[] arr2 = Arrays.copyOf(arr, arr.length);System.out.println(Arrays.toString(ar2);

程序执行结果：[3， 4, 9]

注意：Arrays.copyOf(array,newLength) 第二个参数 newLength 声明这个数组的长度可以比复制的数组长，多余的元素会初始化为 0 值。

即使每个元素统一赋值，使用 Arrays.fill() 对于数组填充，请参考以下代码：

int[] arr = new int[10];Arrays.fill(arr, 6);System.out.println(Arrays.toString(arr));

程序执行结果：[6， 6, 6, 6, 6, 6, 6, 6, 6, 6]

注意：使用 Arrays.fill() 即使数组之前有赋值操作，也会覆盖原始值。

使用 org.apache.commons.lang3.ArrayUtils.addAll() 具体实现方法请参考以下代码：

int[] arr = {2, 8, 13, 11, 6, 7};int[] arr2 = {66, 88};// 合并数组int[] arr3 = org.apache.commons.lang3.ArrayUtils.addAll(arr, arr2);System.out.println(Arrays.toString(ar3);

程序执行结果：[2， 8, 13, 11, 6, 7, 66, 88]

使用 Arrays.sort() 具体实现方法请参考以下代码：

int[] arr = {2, 8, 13, 11, 6, 7};Arrays.sort(arr);System.out.println(Arrays.toString(arr));

程序执行结果：[2， 6, 7, 8, 11, 13]

使用 org.apache.commons.lang3.ArrayUtils.reverse(arr) 具体实现方法请参考以下代码：

int[] arr = {2, 8, 13, 11, 6, 7};int[] arr = {2, 8, 13, 11, 6, 7};// 数组正序(排序)Arrays.sort(arr);// 数组逆序org.apache.commons.lang3.ArrayUtils.reverse(arr);System.out.println(Arrays.toString(arr));

程序执行结果：[13， 11, 8, 7, 6, 2]

注意：org.apache.commons.lang3.ArrayUtils.reverse() 这是数组逆序，不是数组倒序，也就是说 ArrayUtils.reverse() 只会将数组的原始顺序逆转输出，在逆转输出之前不会自然排序。

相邻的两个数字，把较大的值放在后面，执行整个循环后，数组从小到大排列。具体实现请参考以下代码：

int[] arr = {2, 8, 13, 11, 6, 7};System.out.println“排序前：” + Arrays.toString(arr));for (int i = 0; i < arr.length; i++) {    // 因为泡沫是将每个循环中较大的数量漂浮到后面，所以是 arr.length-i-1    for (int j = 0; j < arr.length - i - 1; j++) {        if (arr[j] > arr[j + 1]) {            // 元素交换            int temp = arr[j + 1];            arr[j + 1] = arr[j];            arr[j] = temp;        }    }}System.out.println(”排序后：“” + Arrays.toString(arr));

程序执行结果：

排名前：[2， 8, 13, 11, 6, 排序后：[2， 6, 7, 8, 11, 13]

每次从待排序的数据元素中选择最小（或最大）元素，并将其放在已排序的数字列的最后，直到所有待排序的数据元素完成。具体实现请参考以下代码：

int[] arr = {2, 8, 13, 11, 6, 7};System.out.println“排序前：” + Arrays.toString(arr));for (int i = 0; i < arr.length; i++) {  int lowerIndex = i;  for (int j = i + 1; j < arr.length; j++) {    // 找出最小的索引    if (arr[j] < arr[lowerIndex]) {      lowerIndex = j;    }  }  // 交换  int temp = arr[i];  arr[i] = arr[lowerIndex];  arr[lowerIndex] = temp;}System.out.println(”排序后：“” + Arrays.toString(arr));

程序执行结果：

排名前：[2， 8, 13, 11, 6, 排序后：[2， 6, 7, 8, 11, 13]

以后会有专门的章节介绍更多的排序算法。

找出数组是否包含某个值，并使用它 Arrays.binarySearch() 方法查询。 Arrays.binarySearch() 使用二分法查询一个值，如果发现包含一个值，则返回该值的下标，如果未发现，则返回负值。

int[] arr = {1, 3, 4, 5};// Arrays.binarySearch() 使用二分法查询int值 index = Arrays.binarySearch(arr, 5);System.out.println(index);

注意：使用 Arrays.binarySearch 之前一定要先调用 Arrays.sort() 对数组进行排序，否则返回结果将是错误的。

我们以前使用的数组可以称为一维数组，多维数组可以理解为数组数组。以二维数组为例。二维数组也是一种特殊的多维数组。

例如，我们声明一个二维数组：int[][] arr = new int[2][4];

这相当于我们创建了一个两行四列的表，它的使用、赋值和取值，请查看以下代码示例：

// 声明二维数组int[][] arr = new int[2][4];///循环二维数组 (int i = 0; i < arr.length; i++) {    for (int j = 0; j < arr[0].length; j++) {        // 二维数组赋值        arr[i][j] = j;    }}// Systeme二维数组的值.out.println(arr[0][1]);// System打印二维数组.out.println(Arrays.toString(arr[0]));System.out.println(Arrays.toString(arr[1]));

上述程序执行的结果如下：

1[0, 1, 2, 3][0, 1, 2, 3]

使用 split 将字符串分开形成数组，请参考以下代码：

String str = "laowang,stone,wanglei";String[] arr = str.split(","); // Systemtem字符串转数组.out.println(arr[0]);

使用 Arrays.toString() 方法，请参考以下代码：

String[] arr = {"laowang", "stone", "wanglei"};String str = Arrays.toString(arr);System.out.println(str);

如需查看更多数组转字符串的方式，请查看本文面试部分的介绍。

使用 Arrays.asList() 方法，请参考以下代码：

String[] strArr = {"cat", "dog"};List list = Arrays.asList(strArr);System.out.println(list);

使用 List.toArrray() 方法，请参考以下代码：

List<String> list = new ArrayList<String>();list.add("cat");list.add("dog");// 集合转换为数组String[] arr = list.toArray(new String[list.size()]);System.out.println(Arrays.toString(arr));

答:数组和集合的区别如下:

• 收集可以存储任何类型的对象数据，数组只能存储相同类型的数据；
• 集合长度会发生变化，数组长度是固定的；
• 与数组相比，集合功能更强，数组比集合效率更高。

int[] arr = new int[5] {1, 2, 3, 4, 5};System.out.println(arr[4]);

答:程序编译报错，在 Java 在数组初始化中，如果数组直接赋值，则不能声明数组长度；如果数组长度声明，则不能赋值数组，否则编译器报告错误。

正确的写作方法如下：

int[] arr = new int[]{1, 2, 3, 4, 5};System.out.println(arr[4]);

输出结果为：5，访问元素从 0 开始。

public static void main(String[] args) {    int[] arr = {2, 3, 4, 8};    change(arr);    System.out.println(arr[2]);}private static void change(int[] arr) {    for (int i = 0; i < arr.length; i++) {        if (i % 2 == 0) {            arr[i] *= i;        }    }}

答:输出的结果是 8。

题目分析:在 Java 中数组的本质是引用类型，所以在调用方法中修改数组是对原数组本身的修改。

int[] intArr = new int[3];String[] StrArr = new String[3];System.out.println(intArr[1]);System.out.println(StrArr[1]);

答:以上程序打印结果为:0 和 null。

题目解析：new int[3] 相当于声明数组的长度 3.每个元素初始化为 0，而 new String[3] 相当于声明数组的长度 3.每个元素初始化为 null。

答:数组转换字符串的方法有以下几种。

方法1：遍历拼接，完整代码如下：

String[] arr = {"laowang", "stone", "wanglei"};StringBuffer sb = new StringBuffer();for (int i = 0; i < arr.length; i++) {    sb.append(arr[i]);    if (i != arr.length - 1)        sb.append(",");}System.out.println(sb.toString());

方式二：Arrays.toString() 转换完整代码如下：

String[] arr = {"laowang", "stone", "wanglei"};String str2 = Arrays.toString(arr);System.out.println(str2);

方式三：StringUtils.join() 转换完整代码如下：

String[] arr = {"laowang", "stone", "wanglei"};String str3 = StringUtils.join(Arrays.asList(arr), ","); // 用英文逗号分隔Systemem.out.println(str3);

答:常见的数组遍历有三种方式。

• 传统 for 循环，如 for (int i = 0; i < arr.length; i++) { //.... }
• for each 循环，如 for (int i : arr) { //... }
• jdk 8 Lambda 方式，如 Integer[] arr = {2, 3, 6, 7, 9}; Arrays._asList_(arr).forEach(x -> System._out_.println(x));

String[] strArr = {"dog", "cat", "pig", "bird"};String[] strar2 = {"dog", "cat", "pig", "bird"};System.out.println(Arrays.equals(strArr, strar2);System.out.println(strArr.equals(strar2);System.out.println(strArr == strar2);

答：上述代码执行的结果分别为：true、false、false。

题目解析：strArr == strar2 因此，结果必须是引用比较 false，数组本身的比较是 strArr.equals(strar2) 为 false 原因是数组没有重写 equals 因此，方法也是引用比较。数组 equals 源代码实现如下：

public boolean equals(Object obj) {  return (this == obj);}

而 Arrays.equals 结果是的原因 true 是因为 Arrays.equals 重写了 equals 方法。源代码实现如下：

public static boolean equals(Object[] a, Object[] a2) {        if (a==a2)            return true;        if (a==null || a2==null)            return false;        int length = a.length;        if (a2.length != length)            return false;        for (int i=0; i<length; i++) {            Object o1 = a[i];            Object o2 = a2[i];            if (!(o1==null ?(o1==null ? o2==null : o1.equals(o2)))                return false;        }        return true;    }

String[] arr = {"dog", "cat", "pig", "bird"};int result = Arrays.binarySearch(arr, "bird");System.out.println(result == -1);

答:返回结果如下:true。

题目分析：使用 Arrays.binarySearch 之前一定要先调用 Arrays.sort() 对数组进行排序，否则返回的结果是错误的，这个数组返回的结果是 ﹣1.由于没有使用排序结果，请查看以下代码：

String[] arr = {"dog", "cat", "pig", "bird"};Arrays.sort(arr);int result = Arrays.binarySearch(arr, "bird");System.out.println(result == -1);

答：Arrays 常用方法如下：

• Arrays.copyOf() 数组拷贝
• Arrays.asList() 数组转为 List 集合
• Arrays.fill() 数组赋值
• Arrays.sort() 数组排序
• Arrays.toString() 数组转字符串
• Arrays.binarySearch() 二分法查询元素
• Arrays.equals() 比较两个数组的值

答:查询数组中是否包含一个值有两种常见方法:

• 方式一：Arrays.asList(array).contains("key");
• 方式二：Arrays.binarySearch(array, "key");

具体实现代码如下：

String[] arr = {"doc", "pig", "cat"};// 方式一：Arrays.asList(array).containsboolean bool = Arrays.asList(arr).contains("cat");System.out.println(bool);// 方式二：Arrays.binarySearchArrays.sort(arr);boolean bool2 = Arrays.binarySearch(arr, "cat") > -1;System.out.println(bool2);

答:这个问题调查的知识点显然不是用来的 for 循环修改如此简单，但调查是正确的 Arrays.fill() 掌握方法，以下提供了两种实现方法供参考。

方式一：for 循环方式

int[] arrInt = new int[10];for (int i = 0; i < arrInt.length; i++) {    if (i >= 2 && i < 5) {        arrInt[i] = 6;    }}

方式二：Arrays.fill() 方式

int[] arrInt = new int[10];Arrays.fill(arrInt, 2, 5, 6);

在 Java 中数组的本质是引用类型，数组只能用来存储固定大小的相同类型元素。在 Java 许多集合的内部依赖于数组，例如 ArrayList 和 HashMap 等。数组冒泡排序和选择排序也是面试的常见内容，很多公司会要求面试官手写冒泡排序。本文还介绍了数组、字符串和集合之间的相互转换。只有掌握了这些技能，我们才能发展得更好 Java 程序。