数组常见算法

1. 数组元素的赋值(杨辉三角，回文数等)

杨辉三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package com.atguigu.exer;
/*
使用二维数组打印一个 10 行杨辉三角。
【提示】
 1. 第一行有 1 个元素, 第 n 行有 n 个元素
 2. 每一行的第一个元素和最后一个元素都是 1
 3. 从第三行开始, 对于非第一个元素和最后一个元素的元素。即：
yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];
 */
public class YangHuiTest {
    public static void main(String[] args) {
        //1.声明并初始化二维数组
        int[][] yangHui = new int[10][];
        //2.给数组的元素赋值
        for (int i = 0; i < yangHui.length; i++) {
            yangHui[i] = new int[i + 1];
            //2.1 给首末元素赋值
            yangHui[i][0] = yangHui[i][i] = 1;
            //2.2 给每行的非首末元素赋值
            for (int j = 1; j < yangHui[i].length - 1; j++) {
                yangHui[i][j] = yangHui[i-1][j-1] + yangHui[i-1][j];
            }
            //3.遍历二维数组
            for (int j = 0; j < yangHui[i].length; j++) {
                System.out.print(yangHui[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

2. 求数值型数组中元素的最大值、最小值、平均数、总和等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package com.atguigu.java;

public class ArrayTest1 {
    public static void main(String[] args) {
        int [] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * (99 -10 + 1) + 10);
        }

        //遍历
        for(int i = 0;i < arr.length;i++){
            System.out.print(arr[i] + "\t");
        }
        System.out.println();

        //求数组元素的最大值
        int maxValue = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (maxValue < arr[i]){
                maxValue = arr[i];
            }
        }
        System.out.println("最大值为：" + maxValue);
        //求数组元素的最小值
        int minValue = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (minValue > arr[i]){
                minValue = arr[i];
            }
        }
        System.out.println("最小值为：" + minValue);
        //求数组元素的总和
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        System.out.println("总和为：" + sum);
        //求数组元素的平均数
        int avgValue = sum / arr.length;
        System.out.println("平均数为：" + avgValue);
    }
}

3. 数组的复制、反转、查找(线性查找、二分法查找)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package com.atguigu.java;

public class ArrayTest2 {
    public static void main(String[] args) {
        String[] arr = new  String[]{"JJ","DD","MM","BB","GG","AA"};

        //数组的复制
        String[] arr1 = new String[arr.length];
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = arr[i];
        }

        //数组的反转
        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;
        }
        //遍历
        for(int i = 0;i < arr.length;i++){
            System.out.print(arr[i] + "\t");
        }
        System.out.println();

        //查找
        //线性查找
        String dest = "BB";
        dest = "CC";
        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("没找到");
        }
        //二分法查找，效率高
        //前提：所要查找的数组必须有序。
        int [] arr2 =new int[]{-98,-34,2,34,54,66,79,105,210,333};
        int dest1 = -34;
        dest1 = 35;
        int head_index = 0;                     //初始的首索引
        int end_index = arr2.length - 1;        //初始的末索引
        boolean isFlag1 = true;
        while (head_index <= end_index){
            int middle_index = (head_index + end_index) / 2;
            if (dest1 == arr2[middle_index]){
                System.out.println("位置为：" + middle_index);
                isFlag = false;
                break;
            }else if(arr2[middle_index] > dest1){
                end_index = middle_index- 1 ;
            }else {
                head_index = middle_index + 1;
            }
        }
        if (isFlag){
            System.out.println("没找到");
        }
    }
}

4. 排序算法

1. 衡量排序算法的优劣：

  1. 时间复杂度：分析关键字的比较次数和记录的移动次数
  2. 空间复杂度：分析排序算法中需要多少辅助内存
  3. 稳定性：若两个记录 A 和 B 的关键字值相等，但排序后 A、B 的先后次序保
    持不变，则称这种排序算法是稳定的。

2. 排序算法分类：内部排序和外部排序。

  1. 内部排序：整个排序过程不需要借助于外部存储器（如磁盘等），所有排序操作都在内存中完成。
  2. 外部排序：参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘）。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。

3. 十大内部排序算法

  1. 选择排序
    1. 直接选择排序
    2. 堆排序
  2. 交换排序
    1. 冒泡排序
    2. 快速排序
  3. 插入排序
    1. 直接插入排序
    2. 折半插入排序
    3. Shell 排序
  4. 归并排序
  5. 桶式排序
  6. 基数排序

4. 算法的 5 大特征

  1. 输入（Input）：有 0 个或多个输入数据，这些输入必须有清楚的描述和定义
  2. 输出（Output）：至少有 1 个或多个输出结果，不可以没有输出结果
  3. 有穷性（有限性，Finiteness）：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
  4. 确定性（明确性，Definiteness）：算法中的每一步都有确定的含义，不会出现二义性
  5. 可行性（有效性，Effectiveness）：算法的每一步都是清楚且可行的，能让用户用纸笔计算而求出答案

5. java 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 冒泡排序
package com.atguigu.java;

public class BubbleSortTest {
    public static void main(String[] args) {
        int [] arr = new int[] {43,32,76,-98,0,64,33,-21,32,99};
        for(int i = 0;i < arr.length - 1;i++){
            for(int j = 0;j < arr.length - 1 - i;j++){
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 快速排序
package com.atguigu.java;

public class QuickSort {
    private static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    private static void subSort(int[] data, int start, int end) {
        if (start < end) {
            int base = data[start];
            int low = start;
            int high = end + 1;
            while (true) {
                while (low < end && data[++low] - base <= 0)
                    ;
                while (high > start && data[--high] - base >= 0)
                    ;
                if (low < high) {
                    swap(data, low, high);
                } else {
                    break;
                }
            }
            swap(data, start, high);

            subSort(data, start, high - 1);//递归调用
            subSort(data, high + 1, end);
        }
    }
    public static void quickSort(int[] data){
        subSort(data,0,data.length-1);
    }


    public static void main(String[] args) {
        int[] data = { 9, -16, 30, 23, -30, -49, 25, 21, 30 };
        System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
        quickSort(data);
        System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
    }
}

5. Arrays 工具类的使用

常用的类 作用
boolean equals(int[] a,int[] b) 判断两个数组是否相等。
String toString(int[] a) 输出数组信息。
void fill(int[] a,int val) 将指定值填充到数组之中。
void sort(int[] a) 对数组进行排序。
int binarySearch(int[] a,int key) 对排序后的数组进行二分法检索指定的值。

java 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package com.atguigu.java;

import java.util.Arrays;

public class ArraysTest {
    public static void main(String[] args) {
        //1.boolean equals(int[] a,int[] b)
        int [] arr1 = new int[]{1,2,3,4};
        int [] arr2 = new int[]{1,3,2,4};
        boolean isEquals = Arrays.equals(arr1, arr2);
        System.out.println(isEquals);               //false

        //2.String toString
        System.out.println(Arrays.toString(arr1));  //[1, 2, 3, 4]

        //3.void fill(int[] a,int val)
        Arrays.fill(arr1, 10);
        System.out.println(Arrays.toString(arr1));  //[10, 10, 10, 10]

        //4.void sort(int[] a)
        Arrays.sort(arr2);
        System.out.println(Arrays.toString(arr2));  //[1, 2, 3, 4]

        ////5.int binarySearch(int[] a,int key)  要有序
        int[] arr3 = new int[]{-98,-34,2,34,54,66,79,105,210,333};
        int index = Arrays.binarySearch(arr3, 210);
        if (index >= 10){
            System.out.println(index);
        }else {
            System.out.println("没找到");
        }
    }
}

6. 数组使用中的常见异常

  1. 数组角标越界的异常：ArrayIndexOutOfBoundsExcetion
  2. 空指针异常：NullPointerException

java 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package com.atguigu.java;

public class ArrayExceptionTest {
    public static void main(String[] args) {
        //1. 数组角标越界的异常：ArrayIndexOutOfBoundsExcetion
        int[] arr = new int[]{1,2,3,4,5};
        //System.out.println(arr[5]);
        //System.out.println(arr[-2]);

        //2.2. 空指针异常：NullPointerException
        //情况一
        int[] arr1 = new int[]{1, 2, 3};
        arr1 = null;
        //System.out.println(arr1[0]);

        //情况二
        int[][] arr2 = new  int[4][];
        //System.out.println(arr2[0][0]);   要初始化

        //情况三：
        String[] arr3 = new String[]{"AA", "BB", "CC"};
        //arr3[0] = null;
        System.out.println(arr3[0].toString());
    }
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章