一、什么是数组
数组就是一次定义N个数据类型相同的变量
1、数组的创建与初始化
1.1数组的动态初始化
(标准写法)
数据类型[ ] 数组名称 = new 数据类型[ ] {可初始化的数据 }；
int[] arr = new int[] {1,2,3,4,5};
数据类型[ ] 数组名称 = new 数据类型[ num]； // num表当前数组的最大元素个数，
每个元素的值均为该数据类型的默认值
int[] arr = new int[100];
1.2数组的静态初始化
数据类型[ ] 数组名称 = {初始化数据}；
int[] arr = {1,2,3,4,5};
2、数组的使用
2.1获取一个数组的长度（数组的最大元素个数），使用数组名称 . length
2.2访问数组元素：使用数组名称[ 元素的索引]
数组的索引从0开始，最后一个元素的索引为
数组名称 . length -1
,若索引超出这个取值范围，则会出现数组越界异常（ArrayIndexOutOfBoundsException）。
2.3遍历数组
public class arrTest1 {
public static void main(String[] args) {
int[] arr = new int[]{1,2,3,4,5};
//for循环遍历数组
//i表示每个数组元素的索引下标
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]+" ");
}
//for-each遍历数组（增强型for循环）
//i表示对元素组的每个元素的值的拷贝
for (int i :arr) {
System.out.print(i+" ");
}
}
}注意事项：
for-each 中的i只能读取原数组中的值，无法修改
二、数组与方法的关系
1、数组作为方法的参数
public class arrTest {
//创建一个整形数组，接受任意的整型数组并打印
public static void printNum(int[] arr){
for (int i :arr) {
System.out.print(i+" ");
}
}
public static void main(String[] args) {
int[] date1 = new int[]{1,2,3,4};
int[] date2 = new int[]{2,4,6};
printNum(date1);
printNum(date2);
}
}
2、形参和实参的关系
public class arrTest1 {
public static void main(String[] args) {
//a,b是实参，位于主方法的临时变量
int a = 10;
int b = 20;
swap(a,b);
System.out.println("a ="+a +", b ="+b);
}
public static void swap(int a ,int b){//a,b是位于swap方法的临时变量
int c = a;
a = b;
b = c;
}
}
public class arrTest1 {
public static void main(String[] args) {
int[] date = new int[]{10,20};
swap(date);
System.out.println("date[0]="+date[0] +", date[1] ="+date[1]);
}
public static void swap(int[] arr ){
int a = arr[0];
arr[0] = arr[1];
arr[1] = a;
}
}
注意：
int[] date
=
new int[]{10,20}
;
1、
int[] date
表示数组的引用，就是给数组起名；保存的数值就是该数组的首元素地址。
2、
new int[] {10,20}
表示对象，在堆中存储
3、程序每次调用的过程就对应栈中一个栈帧的入栈以及出栈。当方法开始调用时入栈，方法中的局部变量都在栈中保存；当方法结束调用时，出栈，栈中的所有局部变量都会被销毁
4、看到new关键字，new出来的对象都在堆中保存
三、数组练习
1、数组对象转为字符串对象
public static void main(String[] args) {
int[] date = new int[] {1,2,3};
//JDK内置的工具类
String tmp = Arrays.toString(date);
System.out.println(tmp);
}注：Arrays 数组的工具类，包含数组转字符串的方法，数组排序的方法，等等操作数组的各种方法都在这个类中，可以直接通过类名称来调用。
public class arrPractice1 {
//数组对象转为字符串对象
public static String toString(int[] arr){
String ret = "[";
//遍历原arr数组，取出数组中每个元素的值，通过+与字符串ret拼接在一起
for (int i = 0; i < arr.length; i++) {
ret += arr[i];
//最后一个元素的值后没有",",所以要特殊处理，进行判断即可
if(i < arr.length -1){
ret += ", ";
}
}
ret += "]";
return ret;
}
public static void main(String[] args) {
int[] date = new int[] {1,2,3};
System.out.println(toString(date));
}
}
2、拷贝数组
//打印数组中的每一个值
public static void printNum(int[] arr){
for (int i:arr){
System.out.print(i+" ");
}
}
public static void main(String[] args) {
int[] date = new int[]{1,2,3};
int[] newDate = Arrays.copyOf(date,date.length);
int[] newDate1 = Arrays.copyOf(date,2);
int[] newDate2 = Arrays.copyOf(date,5);
//数组的区间拷贝，从开始位置到结束位置
int[] newDate3 = Arrays.copyOfRange(date,0,2);
printNum(newDate);
System.out.println();
printNum(newDate1);
System.out.println();
printNum(newDate2);
System.out.println();
printNum(newDate3);
}
注： int[] newDate = Arrays.copyOf(
date
,
date.length
);表示返回拷贝后的新数组
**
：表原数组名称；
**
表新数组的长度；
（1）若新数组长度小于原数组长度 ，部分拷贝，即从原数组第一个元素开始拷贝，直到达到新数组长度时停止拷贝。
（2）若新数组长度等于原数组长度，全部拷贝；
（3）若新数组长度大于原数组长度，全拷贝，剩余元素用该数据类型的默认值来补充。
public class arrPractice2 {
//数组拷贝
public static int[] copyOf(int[] arr){
int[] newArr = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
newArr[i] = arr[i];
}
return newArr;
}
//打印数组中的每一个值
public static void printNum(int[] arr){
for (int i:arr){
System.out.print(i+" ");
}
}
public static void main(String[] args) {
int[] date = new int[]{1,2,3};
int[] newDate = copyOf(date);
printNum(newDate);
}
}
3、给出一个数组，找出其中的最大值
“打擂台思想”
（在寻找数组最大值的过程中，需要从数组第一个元素开始遍历，知道最后一个元素，找到其中的最大值，且
默认以数组的第一个元素作为最大值或最小值
与其他元素进行比较）
public class arrPractice3 {
//给定一个数组，找出其中的最大值
public static int maxNum(int[] arr) {
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if(arr[i] > max){
max = arr[i];
}
}
return max;
}
public static void main(String[] args) {
int[] date = new int[]{1,5,9,2,6,3,55,44};
System.out.println(maxNum(date));
}
}
4、二分查找（只能在有序数组中使用二分查找）
在有序区间中查找一个元素toFind,不断比较待查找元素和中间位置元素的大小关系；
若toFind < arr[mid] ——>说明这个元素一定在左区间，一定小于arr[mid …right ]的所有元素，
令right = mid -1,继续判断 ；
若toFind > arr[mid] ——>说明这个元素一定在右区间，一定大于arr[left …mid ]的所有元素，
令left =mid +1，继续判断；
若toFind = arr[mid] ——>说明这个元素正好在中间，输出mid；
循环的终止条件：left > right
，说明区间中一个元素都没有了，在此区间中没有找到待查找元素，循环终止；若left == right，说明区间中还剩下一个元素没有判断
public class arrPractice4 {
//查找一个数组中是否包含指定元素，若包含，返回索引下表，若不包含，返回-1；
public static int findNum(int[] arr, int toFind ){
for (int i = 0; i <arr.length ; i++) {
if(toFind == arr[i] ){//说明找到了，返回索引
return i;
}
}
return -1;//没找到，返回-1
}
//二分查找
public static int find(int[] arr, int toFind){
int left = 0;
int right =arr.length-1;
while (left <= right){//循环的终止条件一定是left > right，注意判断的范围！！！
int mid = (left + right)/2;
if(toFind > arr[mid]){
//大于左区间的所有元素，只在右区间中查找 ;扩大左区间的取值
left = mid+1;
}else if(toFind < arr[mid]) {
//小于右区间的所有元素，只在左区间查找 ;缩小右区间的取值
right =mid-1;
}else{
//toFind == arr[mid];找到待查找元素
return mid;
}
}
//区间中没有待查找元素，return -1;
return -1;
}
public static void main(String[] args) {
int[] date =new int[] {1,3,5,7,9};
System.out.println(find(date, 3));
System.out.println(find(date, 11));
}
}5、判断一数组是否是有序数组，默认升序（找反例）
若在遍历数组的过程中，发现有一个元素比后一个元素大，找到了一个反例，说明不是有序数组
public class arrPractice5 {
//判断一个数组是否是有序数组（升序）
public static boolean judgement(int[] arr){
//取循环边界条件时，最大的取值不能越界 ；i+1<arr.length
for (int i = 0; i < arr.length-1; i++) {
if(arr[i] > arr[i+1]){
//前一个元素大于后一个元素，反例
System.out.println("不是有序数组");
return false;
}
}
System.out.println("是有序数组");
return true;
}
public static void main(String[] args) {
int[] date1 = new int[] {1,2,5,3,6};
int[] date2 = new int[] {1,2,3,4};
System.out.println(judgement(date1));
System.out.println(judgement(date2));
}
}6、冒泡排序（不断把较小值交换到数组最前端，较大值交换到数组最末端）
核心思想：假设数组中有n个元素，每进行一次遍历，就将当前数组中的最大值放到数组末尾，每进行一次遍历，就有一个元素到达了最终位置。
public class arrPractice6 {
//冒泡排序（升序）
public static void bubbleSort(int[] arr){
//外层循环表示遍历的次数，每进行一次遍历，就有一个元素到达最终位置
//-1表示待排序数组只剩下最后一个元素，整个数组已经有序，不需要再遍历进行比较了
for (int i = 0; i < arr.length-1; i++) {
// 内层循环表示每个元素待比较的次数
//最大元素的取值不能越界; j+1 < arr.length
//-i 表示已经有i个元素到达了最终位置，不需要再次进行大小关系的比较了
for (int j = 0; j < arr.length-1-i; j++) {
if(arr[j] > arr[j +1]) {
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j +1] = tmp;
}
}
}
}
public static void printNum(int[] arr) {
for (int i :arr) {
System.out.print(i+" ");
}
}
public static void main(String[] args) {
int[] date = new int[]{41,3,1,6,0,9,7};
bubbleSort(date);
printNum(date);
}
}
7、数组逆序（双引用）
public class arrPractice7 {
//数组逆序{1,2,3,4}——>{4,3,2,1}
public static void sortReverse(int[] arr) {
int left = 0;
int right = arr.length-1;
while (left < right){
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left++;
right--;
}
}
public static void printNum(int[] arr){
for (int i :arr) {
System.out.print(i+" ");
}
}
public static void main(String[] args) {
int[] date1 = new int[]{1,2,3,4,5};
int[] date2 = new int[]{1,2,3,4};
sortReverse(date1);
printNum(date1);
System.out.println();
sortReverse(date2);
printNum(date2);
}
}
8、数组的数字排列(将所有的偶数放在前半部分，所有的奇数放在后半部分)
如{1,2,3,4}——>{4,2,3,1}
核心思想：双引用，从前向后找到第一个奇数为止，从后向前找到第一个偶数为止，然后交换
public class arrPractice8 {
public static void swap(int[] arr){
int i = 0;
int j = arr.length-1;
//循环的终止条件i >= j;
while (i < j){
//从前往后，找到第一个奇数为止
while (i< j && arr[i] %2 ==0){
i++;
}
//找到第一个奇数
//从后往前，找到第一个偶数为止
while (i< j && arr[j] %2!=0){
j--;
}
//找到第一个偶数
//交换两数的值
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
public static String toString(int[] arr){
String ret = "[";
for (int i = 0; i < arr.length; i++) {
ret += arr[i];
if(i != arr.length-1){
ret +=", ";
}
}
ret += "]";
return ret;
}
public static void main(String[] args) {
int[] date = new int[]{2,3,1,4,5,6};
int[] date2 = new int[]{1,2,3,4,5};
swap(date);
System.out.println(toString(date));
swap(date2);
System.out.println(toString(date2));
}
}
注：
内层循环也要保证 i < j
,因为若数组全为偶数，根本就找不到奇数，i 就会跑到 j 的后面了；若全为奇数，根本就找不到偶数，j 就跑到 i 的前面了。不可能无限制 i++，j –,否则就会造成数组越界异常。
9、求数组中的多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
（1）双引用 + count 计数
public static int findMethod1(int[] arr){
for (int i = 0; i < arr.length; i++) {
int count = 0;
for (int j = 0; j < arr.length; j++) {
if(arr[i] == arr[j]){
count++;
}
}
if (count >= (arr.length)/2){
return arr[i];
}
}
return -1;
}（2）排序 + 找中间位置数
public static int findMethod2(int[] arr) {
//排序+最中间的数即为多数元素
bubbleSort(arr);
int mid = (arr.length)/2;
return arr[mid];
}
public static void bubbleSort(int[] arr){
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 tmp = arr[j];
arr[j] = arr[j+1];
arr[j + 1] = tmp;
}
}
}
}（3）摩尔投票法
public static int findMethod3(int[] arr){
//摩尔投票法
//默认候选人为第一个元素
int candidate = arr[0];
//自己给自己投上一票
int count = 1;
for (int i = 1; i <arr.length ; i++) {
if(arr[0] == arr[i]){
count++;
}else {
count--;
//当count = 0 时，换候选人
if (count == 0){
candidate =arr[i];
count = 1;
}
}
}
return candidate;
}
注：摩尔投票法的应用 ——众数问题
1、在一堆元素中，如果至多选择一个最多的元素，则他的票数 > n/2；
2、在一堆元素中，如果至多选择两个最多的元素，则他的票数 > n/3；
3、在一堆元素中，如果至多选择m个最多的元素，则他的票数 > n/(m +1)；