Java 之 数组常用算法

一、数组的遍历

　　　数组遍历：就是将数组中的每个元素分别获取出来，就是遍历。遍历也是数组操作中的基石。

　　　 方式一：使用索引下标方式

1 int[] array = { 15, 25, 30, 40, 50, 60, 75 };
2 System.out.println(array[0]); // 15
3 System.out.println(array[1]); // 25
4 System.out.println(array[2]); // 30
5 System.out.println(array[3]); // 40
6 System.out.println(array[4]); // 50
7 System.out.println(array[5]); // 50

　　　　这种方式需要依次根据索引进行频繁重复的操作，不推荐使用，只做了解。

　　　    方式二：使用 for 循环

1 for (int i = 0; i < array.length; i++) {
2       System.out.println(array[i]);
3 }

　　　　对于一个数组，每次对每个元素的操作都是相同的，用循环是最好的方法。而且就算数组的长度发送了改变代码也不需要改动。

二、获取数组中最值元素

　　获取数组中最值的步骤：

• •  定义变量，保存数组0索引上的元素；
  •  遍历数组，获取数组中的每个元素；
  •  将遍历到的元素和保存数组 0 索引上值的变量进行比较；
  •  如果数组元素的值大于（小于）变量的值，变量记录新的值；
  •  数组循环遍历结束，变量保存的就是数组中的最大值（最小值）；

 　　实现：

 1  int[] arr = { 5, 15, 2000, 10000, 100, 4000 };
 2 
 3  //定义最大值和最小值变量，保存数组中0索引的元素
 4   int min = arr[0];
 5   int max = arr[0];
 6   //遍历数组，取出每个元素
 7   for (int i = 0; i < arr.length; i++) {
 8       //遍历到的元素和变量max，min比较
 9       //如果数组元素大于max
10       if (arr[i] > max) {
11          //max记录住大值
12           max = arr[i];
13       }
14       //如果数组元素小于min
15       if(arr[i] < min) {
16           //min记录住小值
17           min = arr[i];
18        }
19    }
20    System.out.println("数组最大值是： " + max);
21    System.out.println("数组最小值是： " + min);

　

三、数组的复制与反转

　　1、复制

1　　String[] arr = new String[]{"JJ","DD","MM","BB","GG","AA"};
        
        
4　　//数组的复制(区别于数组变量的赋值：arr1 = arr)
5　　String[] arr1 = new String[arr.length];
6　　for(int i = 0;i < arr1.length;i++){
7　　　　arr1[i] = arr[i];
8　　}

　　2、反转

//方法一：
for(int i = 0;i < arr.length / 2;i++){
    String temp = arr[i];
    arr[i] = arr[arr.length - i -1];
    arr[arr.length - i -1] = temp;
}

//方法二：
for(int i = 0,j = arr.length - 1;i < j;i++,j--){
    String temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

四、数组的查找

　　1、线程查找

　　　　从头到尾，遍历整个数组，看是否与所查找的值相同的。

　　　　实现：

public static void main(String[] args) {
    String[] arr = new String[]{"JJ","DD","MM","BB","GG","AA"};
    String dest = "BB";
    
    boolean isFlag = true;
    
    for(int i = 0;i < arr.length;i++){
        
        if(dest.equals(arr[i])){
            System.out.println("找到了指定的元素，位置为：" + i);
            isFlag = false;
            break;
        }
        
    }
    if(isFlag){
        System.out.println("很遗憾，没有找到的啦！");
        
    }
}

　　2、二分查找

　　　　对排好序的数组，然后分半查找。

　　　　实现：

public static void main(String[] args) {
    int[] arr2 = new int[]{-98,-34,2,34,54,66,79,105,210,333};
    
    int dest1 = -34;
    dest1 = 35;
    int head = 0;//初始的首索引
    int end = arr2.length - 1;//初始的末索引
    boolean isFlag1 = true;
    while(head <= end){
        
        int middle = (head + end)/2;
        
        if(dest1 == arr2[middle]){
            System.out.println("找到了指定的元素，位置为：" + middle);
            isFlag1 = false;
            break;
        }else if(arr2[middle] > dest1){
            end = middle - 1;
        }else{//arr2[middle] < dest1
            head = middle + 1;
        }

        
    }
    
    if(isFlag1){
        System.out.println("很遗憾，没有找到的啦！");
    }
    
}

　　　　注意：使用前提，所要查找的数组必须有序。

五、数组的排序

　　1、冒泡排序

　　　　冒泡排序是最常用的数组排序算法之一，它排序数组元素的过程总是将小数往前放、大数往后放，类似于水中气泡往上升的动作，所以称作冒泡排序。

　　　　基本思想：对比相邻的元素值。

　　　　参考：冒泡排序

　　　　　代码实现：

 1 int array[] = {12,58,3,46,18,43};
 2         for (int i = 0; i < array.length - 1; i++) {
 3             for (int j = 0; j < array.length - 1 - i; j++) {
 4                 if (array[j] > array[j + 1]) {
 5                     int temp = array[j];
 6                     array[j] = array[j + 1];
 7                     array[j + 1] = temp;
 8                 }
 9             }
10             System.out.println("第" + i + "次排序结果：" + Arrays.toString(array));
11         }

　　2、反转排序

　　　　数组的反转：数组中的元素颠倒顺序，例如原始数组为1,2,3,4,5，反转后的数组为5,4,3,2,1

　　　　实现思想：数组最远端的元素互换位置 

• • • 　实现反转，就需要将数组最远端元素位置交换
    •     定义两个变量，保存数组的最小索引和最大索引
    •     两个索引上的元素交换位置
    •     最小索引++，最大索引--，再次交换位置
    •     最小索引超过了最大索引，数组反转操作结束

　　　　流程图：

　　　　　　代码实现：

 1 public static void main(String[] args) {
 2 　　int[] arr = { 1, 2, 3, 4, 5 };
 3 　　/*
 4 　　循环中定义变量min=0最小索引
 5 　　max=arr.length‐1最大索引
 6 　　min++,max‐‐
 7 　　*/
 8 　　for (int min = 0, max = arr.length ‐ 1; min <= max; min++, max‐‐) {
 9 　　//利用第三方变量完成数组中的元素交换
10 　　int temp = arr[min];
11 　　arr[min] = arr[max];
12 　　arr[max] = temp;
13 　　} 
14 　　// 反转后，遍历数组
15 　　for (int i = 0; i < arr.length; i++) {
16　　 System.out.println(arr[i]);
17　　 }
18 }

六、数组作为方法参数和返回值

　　1、数组作为方法参数

　　　　数组作为方法参数传递，传递的参数是 数组内存的地址。

　　　Demo：

 1 public static void main(String[] args) {
 2 　　int[] arr = { 1, 3, 5, 7, 9 };
 3 　　//调用方法，传递数组
 4 　　printArray(arr);
 5 }
 6 /*
 7 创建方法，方法接收数组类型的参数
 8 进行数组的遍历
 9 */
10 public static void printArray(int[] arr) {
11 　　for (int i = 0; i < arr.length; i++) {
12 　　　　System.out.println(arr[i]);
13 　　}
14 }

 　　Tips：方法的参数为基本类型时,传递的是 数据值. 方法的参数为引用类型时,传递的是 地址值.。

　　2、数组作为方法返回值

　　　　数组作为方法的返回值，返回的是 数组的内存地址

　　　 Demo：

 1 public static void main(String[] args) {
 2 　　//调用方法，接收数组的返回值
 3 　　//接收到的是数组的内存地址
 4 　　int[] arr = getArray();
 5 　　for (int i = 0; i < arr.length; i++) {
 6 　　　　System.out.println(arr[i]);
 7 　　}
 8 }
 9 /*
10 创建方法，返回值是数组类型
11 return返回数组的地址
12 */
13 public static int[] getArray() {
14 　　int[] arr = { 1, 3, 5, 7, 9 };
15 　　//返回数组的地址，返回到调用者
16 　　return arr;
17 }

 　　总结：任何数据类型都能作为方法的参数类型，或者返回值类型