数组常用算法知识点框架笔记

数组常用算法有一维数组，增强循环，可变参数，命令行参数，常用算法，二维数组，数组复制知识点。适合知识点整理以及背诵的小伙伴。

数组常用算法知识点框架笔记

• 数组概述
  • 什么是数组
    • 数组是用来存储"一组相同类型数据的"数据结构
    • 数组变量属于引用数据类型
    • 数组中的元素可以是任何数据类型(基本类型和引用类型)
    • 数组有一个对应的索引，可以通过索引访问数组中的每个元素
    • 数组被创建好之后，它的大小是不能改变的，但是数组中的各个元素是可以被改变的
• 一维数组
  • 声明
    • int a[];
    • int[] a1;
    • double b [];
    • Mydate []c;
    • 声明数组时不能指定其长度
  • 初始化
    • 动态初始化
      • new 数据类型[大小]
      • new 数据类型[]{元素1,元素2...元素n}
    • 静态初始化
      • 在数组定义的同时，对数组进行初始化
      • int a[] = {1,3,5,7,9,11};
      • String s [] = {"a","b","c"};
  • 简单数据类型数组 (参考PPT上的内存变化图)
    • 定义
    • 创建
  • 引用数据类型数组 (参考PPT上的内存变化图)
    • 定义
    • 创建
    • 初始化
  • 数组元素的默认初始化规则
  • 数组元素的引用方式:数组名[下标]
• 增强for循环
  • for(数据类型 变量名:数组变量名){...}
  • 用途：只适合依次遍历显示数组或集合中全部元素的内容。
  • 缺陷：遍历数组或集合时无法访问索引(下标)值
• 可变参数
  • 在声明方法的时候 .....方法名(数据类型 ... 变量名)
  • 可以接受传入0-n个该类型的参数, 在方法中用数组的方式来处理
  • 必须把可变参数写在形参列表的最后, 否则编译报错.
• 命令行参数
  • java 类名 abc "hello world" 123 "ni hao"
  • 给main方法的(String args[])传参
• 常用算法
  • 排序
    • 冒泡排序
      • public static void bubbleSort(int[] a) { int n = a.length; //总共进行n-1轮的比较 for (int i = 1; i for (int j = 1; j if (a[j-1] > a[j]) {//左>右,则交换 int temp = a[j-1]; a[j-1] = a[j]; a[j] = temp; } } } }
    • 选择排序
      • public static void selectionSort(int[] a) { for(int i = 0; i int k = i;//k记录当前轮最小值的下标 for(int j = k + 1; j if(a[j] k = j; //记下目前找到的最小值所在的位置 } } if(i != k){ //交换a[i]和a[k] int temp = a[i]; a[i] = a[k]; a[k] = temp; } } }
    • 插入排序
      • public static void insertSort(int[] a) { for (int i = 1; i for (int j = i; j > 0; j--) { if (a[j] int temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; } else { break; } } } }
  • 查找
    • 顺序查找,从第一个元素开始顺序依次查找
      • public static int search(int[] a, int num) { for(int i = 0; i if(a[i] == num){ return i; } } return -1; }
    • 二分查找
      • 前提条件：已排序的数组中查找
      • 基本思想
        • 首先确定该查找区间的中间点位置： int mid = (low+upper) / 2; 然后将待查找的值与中间点位置的值比较： 若相等，则查找成功并返回此位置。 若中间点位置值大于待查值，则新的查找区间是中间点位置的左边区域。 若中间点位置值小于待查值，则新的查找区间是中间点位置的右边区域。下一次查找是针对新的查找区间进行的。
      • 代码
        • public static int binarySearch(int[] a, int num) { int low = 0; // 起点 int upper = a.length - 1; // 终点 while (low int mid = (low + upper) / 2; // 中间点 if (a[mid] low = mid + 1; // 更改查找的起点为中间点位置后一位 } else if (a[mid] > num) { // 中间点的值大于要查找的值 upper = mid - 1; // 更改查找的终点为中间点位置前一位 } else { // 中间点的值等于要查找的值 return mid; // 返回该位置 } } return -1; }
• java.util.Arrays 数组操作工具类
  • public static void sort(int[] a);
  • public static int binarySearch(int[] a, int key); //使用二分搜索法,前提是数组已从小到大排序
  • public static String toString(int [] a) //将传入的数组格式化为字符串输出
• 二维数组
  • 由数组组成的数组
  • 初始化
    • 静态初始化
    • 动态初始化
• 数组复制
  • System.arraycopy(.....)
  • Arrays类的public static int[] copyOf(int[] original, int newLength)