一、动态数组

1、数组的定义

​ 用于存储相同数据类型的一组连续的存储空间

2、数组的特点：

​ 数组的长度一旦定义，则不可改变

​ 访问数组的元素需要通过下标（索引）访问，下标从0开始

​ 数组是引用数据内存，内存分布在堆内存中，数组的变量存储的内存地址

3、动态数组：

​ 由于数组的长度定义后不能改变，所谓“动态数组”是可以增加数组的长度， 所以Java实现动态数组是改变数组变量指向不同的内存的地址。 本质并没有将数组的长度改变。

​ 动态数组的本质： 将内存空间的改变， 以及指向数组内存的地址改变

​ 操作1 ： 给数组 添加新元素 ，可添加在最后面 ，也可添加到指定位置

/** * 添加元素 （添加到末尾） */ public static int [] addEle(int [] array ,int num){ // 目标数组 添加的原始 //int [] array = {10,9,3,2,1}; // 1、创建临时数组的变量 int [] tempArray = new int[array.length+1]; //2、将目标数组的元素 copy到 临时数组的内存中 for(int i = 0 ;i<array.length;i++){ tempArray[i]= array[i]; } // 3、将添加的元素放入临时数组中 tempArray[tempArray.length-1] = num; // 4、将目标数组的地址 指向 临时数组的地址 array= tempArray; // 由于tempArray 是局部变量， 方法执行完内存自动回收 ， // 如果不返回 没有地址指向tempArray的内存 // 如果返回并接收，说明这块内存仍然有用。 return array; }

/** * 将元素num 添加到指定index的位置 * @param arr * @param num * @param index * @return */ public static int [] addEle(int [] arr , int num ,int index){ // 1、创建临时数组的大小 int [] tempArray = new int[arr.length+1]; //2、遍历arr for(int i = 0 ; i<=arr.length;i++){ // 如果i<index if(i<index){ tempArray[i] = arr[i]; }else if(i==index){ // 2 tempArray[i] = num; }else{ // i > index // i=3 arr[i-1] 10 9 3 2 1 -> 10 9 5 3 0 0 // i =4 array[i-1] 2-> 10 9 5 3 2 0 // i=5 array[4] 1 -> 10 9 5 3 2 1 tempArray[i] = arr[i-1]; } } // 赋值 arr = tempArray; return arr; }

操作2： 删除元素 ，删除指定下标的元素

/** * 删除指定下标的元素 * @param arr 目标数组 * @param index 删除的下标 * @return 删除之后的数组 */ public static int [] removeEle(int [] arr, int index){ // 1、创建一个临时数组 用于存放删除后的原始 int [] tempArray = new int [arr.length-1]; // 2、遍历目标数组 for(int i = 0 ;i<arr.length;i++){ if(i<index){ tempArray[i] = arr[i]; }else if(i==index){ continue; }else {//i>index tempArray[i-1] = arr[i]; } } // 3 将目标数组的地址变换成 新数组的地址 arr=tempArray; return arr; }

​

二、数组的排序

​ 排序： 将一组数列（无序的）按照从小到大或者从大到小的顺序排列。

1、冒泡排序

​ 从第一个数开始， 与它相邻的数比较 ，较大（或较小）的数放在后面，最终比较一轮之后，得出最大（或最小）的数放在最后

​ 比较思路：

​

冒泡排序的规则 * 1、从第一个数开始，将这个数 与它相邻的数比较 ，如果 这个数大于它相邻的数 * 则两个数交换位置 * i=0 相邻i=1 * 2、依次 从第二个数开始，再将这个数与它相邻的数比较，如果第二个数大于相邻的数 * 则继续交换 * 依次类推， 到倒数第二个截止 ，直到将最大的数放在最后面 * 3、重复以上1,2步骤 / public static void main(String[] args) { int [] array = {5,4,3,2,1}; //用于交换的临时变量 int temp=0; for(int j =0;j<array.length-1;j++) { for (int i = 0; i < array.length -j-1; i++) { // 相邻的数比较 if (array[i] > array[i + 1]) { temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; } } System.out.println("比较一轮之后：" + Arrays.toString(array)); } }

2、选择排序

/** * 选择排序： 从一堆数中选择一个最小数 放在第一个位置，再从一堆数中选择一个 * 最小数放在第二个位置， 依次 将一堆数的最小数按顺序排放。 * 步骤： 1、假设第一个数是最小数，需要定义最小数的下标minIndex=0 * 将这个数与后面的每一个数比较，找到最小数的下标即可 * 2、将第一个数与最小数的下标交换 ，得出最小数在第一位。 * 3、 依次类推， 将已比较的数 忽略，继续从生下的元素中找足最小数，放入已比较的数的下一位 * 直到整个数列比较结束 * @param args */ public static void main(String[] args) { int [] array = {3,2,1,5,7,4}; for(int j=0;j<array.length-1;j++) { // 假设第一个数是最小数 int minIndex = j; // 为什么i =j+1 因为初始值要略过已比较的下标 for (int i = 1+j; i < array.length; i++) { if (array[minIndex] > array[i]) { minIndex = i; } } // 将这个最小数放在 第一位 int temp = 0; temp = array[j]; array[j] = array[minIndex]; array[minIndex] = temp; System.out.println("----第一次完成后：" + Arrays.toString(array)); } System.out.println("最后的排序："+Arrays.toString(array)); } }

3、插入排序

/** * 插入排序 * 1、从第一个元素开始，假设第一个元素是已排好序的 * 2、从下一个元素开始，依次比较它前面的所有元素（从后向前扫描） * 3、 如果这个元素 小于它前面的元素 则两两交换 ， * 如果这个元素 大于它前面的元素，则不交换 * 4、依次重复2,3步骤 ，直到将所有数 比较完成 * 5,4,3,2,1 * * 4 5 3 2 1 i从1开始 * * 4 3 5 2 1 i从2开始 * 3 4 5 2 1 * * 3 4 2 5 1 i从3开始 * 3 2 4 5 1 * 2 3 4 5 1 * * 2 3 4 1 5 i从4开始 * 2 3 1 4 5 * 2 1 3 4 5 * 1 2 3 4 5 * @param args */ public static void main(String[] args) { int [] array = {5,4,3,2,1}; // 外层循环循环 每一个数的比较次数 for(int j=0;j<array.length-1;j++) { int temp = 0; for (int i = 1+j; i > 0; i--) { if (array[i] < array[i - 1]) { temp = array[i]; array[i] = array[i - 1]; array[i - 1] = temp; } } System.out.println("每一次完成后的结果："+ Arrays.toString(array)); } System.out.println("最后一次完成后的结果："+Arrays.toString(array)); }

ay[i - 1]; array[i - 1] = temp; } } System.out.println(“每一次完成后的结果：”+ Arrays.toString(array)); } System.out.println(“最后一次完成后的结果：”+Arrays.toString(array));

}