数组相关算法
数组
数组的声明
数据类型[] 数组名，或数据类型 数组名[].
例：int[] a或int a[].
数组的初始化
动态初始化
数据类型[] 数组名=new 数据类型[数组长度]
例：int[] a=new int[6]初始化操作：先声明，后赋值。或者声明赋值可同时进行。赋值格式：数组名[下标]=值。
取值格式：数据类型 变量名=数组名[索引值]
静态初始化
数据类型[] 数组名=new 数据类型[]{数组元素}
例：int[] a=new int[]{1,2,3,4,5,6}初始化操作：先声明，后赋值。
例：int[] age;age=new int []{数组元素}声明赋值可同时进行。
例：int[] age=new int[]{数组元素}
静态省略初始化
数据类型[] 数组名={数组元素}，
例：int[] a={1,2,3,4,5,6}.初始化操作：只能声明赋值同时进行。
例：int[] age={数组元素}.
数组的默认值
数组声明后若未进行赋值操作，则数组按照默认值进行操作。
整型数组：默认值为0。
浮点数型数组：默认值为0.0。
布尔型数组：默认值为false。
字符型数组：默认值为不可见字符。
引用数据类型数组：默认值为null。
NullpointerException:空指针异常，指数组取值时索引值超过数组长度时会产生的报错。（注意 null与0的区别：null指没有为数组开辟空间；而0指的是开辟了空间，空间长度为0.
二维数组
指的是数组元素为一维数组的数组
初始化操作：
动态初始化
数据类型[][] 数组名=new 数据类型[数组长度][]
int[][] a=new int[6][].
静态初始化
数据类型[][] 数组名=new 数据类型[][]{数组元素}
例：int[][] a=new int[][]{{1},{2},{3},{4}}.
静态省略初始化
数据类型[][] 数组名={数组元素}
例：int[][] a={{1},{2},{3},{4}}.
多维数组
例：int[] a,b[](a为一维数组，b为二维数组)。
数组的相关算法
（1）元素交换：
以数组a为例，取出a的元素a[x],和a[y]进行交换，若数组为引用数据类型，采用定义中间变量temp的方式，其他的则可使用两数异或的方式快速实现交换。
import java.util.Arrays;
public class Main {public static void main(String[] args) {int[] ns = { 5, 2, 6, 7, 8, 3, 1, 9, 4 }; // 排序前System.out.println("排序前:" + Arrays.toString(ns));for (int i = 0 ,n = ns.length; i < n - 1; i++) {for (int k = 0; k < n - 1 - i ; k++) {if (ns[k] > ns[k+1]) {// 交换ns[k]和ns[k+1]:int tmp = ns[k];ns[k] = ns[k+1];ns[k+1] = tmp;}}}// 排序后System.out.println("排序后:" + Arrays.toString(ns));}
}
（2）数组正序遍历：
以数组a为例，for（int i=0；i<a.length；i++）
public class Main {public static void main(String[] args) {int[] ns = { 1, 4, 9, 16, 25 };for (int i = 0; i < ns.length; i++) {int n = ns[i];System.out.println(n);}}
}
（3）数组逆序遍历：
以数组a为例，for（int i=a.length；i>=0；i–）
public class Main {public static void main(String[] args) {int[] ns = { 1, 4, 9, 16, 25 };for (int i = ns.length; i >= 0; i--) {int n = ns[i];System.out.println(n);}}
}
（4）数组正序遍历前半部分：
以数组a为例，for（int i=0；i<a.length/2；i++）
int[] a = {1, 2, 3, 4, 5, 6, 7, 8};
for (int i = 0; i < a.length / 2; i++) {System.out.println(a[i]);
}
（5）数组逆序遍历后半部分：
以数组a为例，for（int i=a.length-1；i>=a.length/2；i–）
int[] a = {1, 2, 3, 4, 5, 6, 7, 8};
for (int i = a.length - 1; i >= a.length / 2; i--) {System.out.println(a[i]);
}
（6）数组元素求和：
以数组a为例，int sum=0；for（int i=0；i<a.length；i++）；sum+=i;.
int[] a = {1, 2, 3, 4, 5, 6, 7, 8};
int sum = 0;
for (int i = 0; i < a.length; i++) {sum += a[i];
}
System.out.println("Sum: " + sum);
（7）元素扩大两倍(或缩小一半)：
以数组a为例，for（int i=0；i<a.length；i++）；a[i]=a[i]<<1（>>1）.
int[] a = {1, 2, 3, 4, 5, 6, 7, 8};
// 扩大两倍
for (int i = 0; i < a.length; i++) {a[i] = a[i] << 1; // 或 a[i] = a[i] * 2;
}// 打印数组
System.out.println("Array after doubling:");
for (int i : a) {System.out.print(i + " ");
}
System.out.println();// 缩小一半
for (int i = 0; i < a.length; i++) {a[i] = a[i] >> 1; // 或 a[i] = a[i] / 2;
}// 打印数组
System.out.println("Array after halving:");
for (int i : a) {System.out.print(i + " ");
}
（8）首位元素交换：
以数组a为例，for（int i=0；i<a.length/2；i++）；int k=a.length-1；a[i]和a[k]使用异或的方法或·定义中间变量的方法进行交换。
int[] a = {1, 2, 3, 4, 5, 6, 7, 8};
int k = a.length - 1;// 使用异或方法交换
for (int i = 0; i < a.length / 2; i++) {a[i] = a[i] ^ a[k - i];a[k - i] = a[i] ^ a[k - i];a[i] = a[i] ^ a[k - i];
}
// 打印数组
System.out.println("Array after swapping using XOR:");
for (int i : a) {System.out.print(i + " ");
}
System.out.println();
// 使用中间变量交换
// 重新初始化数组
a = new int[]{1, 2, 3, 4, 5, 6, 7, 8};
for (int i = 0; i < a.length / 2; i++) {int temp = a[i];a[i] = a[k - i];a[k - i] = temp;
}
// 打印数组
System.out.println("Array after swapping using temp variable:");
for (int i : a) {System.out.print(i + " ");
}（9）For each遍历数组元素；
以数组a为例，for（int i：a）；i为输出的元素，而非下标。注意：此方法无法修改数组元素，也无法控制循环的起始位置。
public class Main {public static void main(String[] args) {int[] ns = { 1, 4, 9, 16, 25 };for (int n : ns) {System.out.println(n);}}
}
（10）冒泡排序：
n个元素比较，采用双重for循环，外层循环 n-1，内层循环n-1-i。
for(int i=0;i<a.length-1;i++){ //比较的轮数for(int j=0;j<a.length-1-i;j++){ //每轮比较的次数if(a[j] > a[j+1]){ //进行大小值比较（若要逆序，将>改为<）a[j] = a[j] ^ a[j+1];a[j+1] = a[j] ^ a[j+1];a[j] = a[j] ^ a[j+1];}}
}
（11）双指针遍历查找元素：
与单指针不同的是，双指针从两头进行查找，效率相对较高.
核心步骤：以数组a，target（目标值），index（目标值下标）为例：
int Index = -1; // 初始化索引为-1，表示未找到目标值
for (int i = 0, j = a.length - 1; i <= j; i++, j--) {if (target == a[i]) {Index = i;break; // 目标找到则退出判断，直接输出}if (target == a[j]) {Index = j;break; // 目标找到则退出判断，直接输出}
}
（12）二分法查找：
核心思想为找中间值，用中间值与目标值进行比较，相对效率最高，但此方法只能用于有序数组。
核心步骤：以数组a，target（目标值），index（目标值下标）为例：
int low = 0; // 数组起始下标
int high = a.length - 1; // 数组结束下标
int target = -1; // 初始化目标值为-1，表示未找到目标值while (low <= high) {int mid = (low + high) / 2; // 确定中间值下标if (a[mid] == target) {target = mid; // 输出结果break;} else if (a[mid] > target) {high = mid - 1; // 在数组前半部分查找} else if (a[mid] < target) {low = mid + 1; // 在数组后半部分查找}
}
（13）两个数组合并：
以数组a,b,为原数组，c为合并后的数组为例。
方法1：逐个遍历两个数组，将元素存入新数组
public class ArrayMerge {public static void main(String[] args) {int[] a = {1, 2, 3, 4};int[] b = {5, 6, 7, 8};int[] c = new int[a.length + b.length];// 将a数组的元素存入c数组for (int i = 0; i < a.length; i++) {c[i] = a[i];}// 将b数组的元素存入c数组for (int i = 0; i < b.length; i++) {c[i + a.length] = b[i];}// 打印合并后的数组System.out.println("Merged array:");for (int i : c) {System.out.print(i + " ");}}
}方法2：交替检查两个数组，依次存入新数组
public class ArrayMerge {public static void main(String[] args) {int[] a = {1, 2, 3, 4};int[] b = {5, 6, 7, 8};int[] c = new int[a.length + b.length];for (int i = 0; i < a.length || i < b.length; i++) {if (i < a.length) {c[i] = a[i];}if (i < b.length) {c[i + a.length] = b[i];}}// 打印合并后的数组System.out.println("Merged array:");for (int i : c) {System.out.print(i + " ");}}
}
（14）拉链法合并两个有序数组：
核心思想为两个数组的元素相互比较，按照排序要求依次放入新数组。
核心步骤： 以数组a,b,为原数组，c为合并后的数组为例。
package apesource.knowledge02.数组操作;
import java.util.Arrays;
//拉链法合并两个数组
public class Demo03 {public static void main(String[] args) {// 有序的数组--合并后仍然有序int[] ns1 = { 1, 5, 7, 9 };int[] ns2 = { 2, 3, 4, 6, 10, 12, 15, 18 };// 创建新数组int[] newArr = new int[ns1.length + ns2.length];// 定义变量int i = 0, j = 0, k = 0;// 循环放元素while (i < ns1.length && j < ns2.length) {if (ns1[i] < ns2[j]) {newArr[k++] = ns1[i++];} else {newArr[k++] = ns2[j++];}}//数组1中的部分元素没放完while(i<ns1.length) {newArr[k++] = ns1[i++];}//数组2中的部分元素没放完while(j<ns2.length) {newArr[k++] = ns2[j++];}
// if (i < ns1.length) {
// System.arraycopy(ns1, i, newArr, k, ns1.length - i);
// }
//
// if (j < ns2.length) {
// System.arraycopy(ns2, j, newArr, k, ns2.length - j);
// }System.out.println(Arrays.toString(newArr));}
}
（15）数组乱序：
核心思想为产出随机下标与数组元素交换。
import java.util.Arrays;public class ArrayShuffle {public static void main(String[] args) {int[] a = {1, 2, 3, 4, 5, 6, 7, 8};// 打乱数组for (int i = a.length - 1; i > 0; i--) {int random = (int) (Math.random() * i); // 取下标值的随机数// 交换a[i]和a[random]的值a[i] = a[i] ^ a[random];a[random] = a[i] ^ a[random];a[i] = a[i] ^ a[random];}// 打印打乱后的数组System.out.println("Shuffled array:");System.out.println(Arrays.toString(a));}
}
（16）数组旋转：
以数组a右旋w次为例。
方法1：在原数组上进行操作
import java.util.Arrays;public class ArrayRotate {public static void main(String[] args) {int[] a = {1, 2, 3, 4, 5, 6, 7, 8};int w = 3; // 右旋次数for (int j = 0; j < w; j++) { // 旋转次数循环int last = a[a.length - 1]; // 保存最后一个元素for (int i = a.length - 1; i > 0; i--) { // 逆序遍历数组a[i] = a[i - 1]; // 将前一个元素赋值给当前元素}a[0] = last; // 将保存的最后一个元素赋值给第一个元素}// 打印旋转后的数组System.out.println("Array after rotation (method 1):");System.out.println(Arrays.toString(a));}
}
方法2：创建新数组，将原数组的元素赋给旋转后的位置
import java.util.Arrays;public class ArrayRotate {public static void main(String[] args) {int[] a = {1, 2, 3, 4, 5, 6, 7, 8};int w = 3; // 右旋次数int[] b = new int[a.length];for (int i = 0; i < a.length; i++) { // 遍历数组b[(i + w) % a.length] = a[i]; // 计算新位置并赋值}// 打印旋转后的数组System.out.println("Array after rotation (method 2):");System.out.println(Arrays.toString(b));}
}
注意：此方法与方法1的区别，方法1是在原数组上进行操作，而方法2是创建新数组，将原数组的元素的值赋给旋转后元素的值。
数组操作的相关方法：
（1）数组元素打印：
以数组a为例，Arrays.toString(a)，注意：如果直接输出数组a，得到的是a所对应的地址，而非数组的元素.
（2）二维数组元素打印：
数组b为例Arrays.deepToString(a).
import java.util.Arrays;public class ArrayPrint {public static void main(String[] args) {int[] a = {1, 2, 3, 4};int[][] b = {{1, 2}, {3, 4}};System.out.println("One-dimensional array: " + Arrays.toString(a));System.out.println("Two-dimensional array: " + Arrays.deepToString(b));}
}
（3）数组填充数值：
以数组a为例，
《1》Arrays.fill(a,值)表示对数组a全部填充某一个值
《2》Arrays.fill(a,form，to，值）表示对数组a从位置form到to（不包括to）填充某一个值
import java.util.Arrays;public class ArrayFill {public static void main(String[] args) {int[] a = new int[5];Arrays.fill(a, 7);System.out.println("Array filled with 7: " + Arrays.toString(a));int[] b = new int[5];Arrays.fill(b, 1, 4, 9);System.out.println("Array partially filled with 9: " + Arrays.toString(b));}
}（4）数组排序：
以数组a为例，
《1》Arrays.sort(a)表示对数组a整体正向排序。
《2》Arrays.sort(a，form，to)表示对数组a从位置form到to（不包括to）正向排序。
import java.util.Arrays;public class ArraySort {public static void main(String[] args) {int[] a = {4, 2, 7, 1, 9};Arrays.sort(a);System.out.println("Sorted array: " + Arrays.toString(a));int[] b = {4, 2, 7, 1, 9};Arrays.sort(b, 1, 4);System.out.println("Partially sorted array: " + Arrays.toString(b));}
}
（5）数组查找（仅限于有序数组）：
以数组a为例
《1》Arrays.binaryseach(a，target)表示在数组a整体中查找target。注意此方法有返回值，返回值为int型，即target对应数组的下标。
《2》Arrays.binaryseach(a，form，to，tag
Rget)表示对数组a从位置form到to（不包括to）区间内查找，返回值同上。
import java.util.Arrays;public class ArraySearch {public static void main(String[] args) {int[] a = {1, 2, 3, 4, 5};int target = 3;int index = Arrays.binarySearch(a, target);System.out.println("Index of target: " + index);int[] b = {1, 2, 3, 4, 5};int indexPartial = Arrays.binarySearch(b, 1, 4, target);System.out.println("Index of target in partial array: " + indexPartial);}
}
（6）数组元素复制：以数组a为例
《1》Arrays.copyOf(a,b)表示从数组a中从第一个元素开始复制b个元素到新数组，b为新数组长度。注意此方法返回值为跟原数组数据类型相同的数组，若复制的元素个数超过a数组，则b数组中除了a数组的部分用默认值补齐。
《2》Arrays.copyOfRange(a,form,to)表示在数组a从位置form到to（不包括to）区间内进行复制，返回值为跟原数组数据类型相同的数组。
《3》system.arrayscopy(a,i,b,j,length)表示在数组a中从i的下标位置复制length个元素到数组b中，开始复制的位置为j。
import java.util.Arrays;public class ArrayCopy {public static void main(String[] args) {int[] a = {1, 2, 3, 4, 5};// 使用 Arrays.copyOfint[] b = Arrays.copyOf(a, 3);System.out.println("Copied array using Arrays.copyOf: " + Arrays.toString(b));// 使用 Arrays.copyOfRangeint[] c = Arrays.copyOfRange(a, 1, 4);System.out.println("Copied array using Arrays.copyOfRange: " + Arrays.toString(c));// 使用 System.arraycopyint[] d = new int[5];System.arraycopy(a, 1, d, 2, 3);System.out.println("Copied array using System.arraycopy: " + Arrays.toString(d));}
}
（7）数组内容比较是否相同：Arrays.equals(a,b)表示数组a和数组b内容比较相同，返回值为boolean型。
import java.util.Arrays;public class ArrayEquals {public static void main(String[] args) {int[] a = {1, 2, 3, 4, 5};int[] b = {1, 2, 3, 4, 5};int[] c = {1, 2, 3, 4, 6};boolean isEqual = Arrays.equals(a, b);System.out.println("Arrays a and b are equal: " + isEqual);boolean isNotEqual = Arrays.equals(a, c);System.out.println("Arrays a and c are equal: " + isNotEqual);}
}