1.一维数组
1.1数组的定义
数组是一个具有相同数据类型，且按一定次序排列的一组变量的集合体。即用一个变量名表示一批数据。Java为数组在内存中分配的是一段连续的空间，这段空间中存储数据的个数是固定的。
1.1.1数组元素
构成一个数组的每一个数据称为数组元素。
1.1.2数组下标
下标是数组元素在数组中的位置。在一个数组中，数组下标是用整数表示的，从0开始，依次加1。
1.1.3数组大小
数组中，元素的个数被称作数组的大小，也叫作数组的长度。
1.2数组的使用
1.2.1定义数组
public static void main(String[] args) {
int arr[]; //或者 int[] arr;
}
1.2.2为数组元素分配内存
arr = new int[3];
1.2.3数组元素初始化
arr[0] = 35;
arr[1] = 26;
arr[2] = 43;
数组初始化指为数组中的数组元素进行第一次赋值。如果没有对数组变量进行初始化，数组元素也会有相对应得默认初始值，各类型数组元素默认初始值如下：
| 数组元素类型 | 默认初始值 |
|---|---|
| byte,short,int,long | 0 |
| float,double | 0.0 |
| char | '\u0000' |
| boolean | false |
| 引用数据类型 | null |
1.2.4使用数组
例：求班级五个同学成绩的平均值
public static void main(String[] args) {
//第一步：定义数组，数组的名称是score
int[] score;//或者int score[]
//第二步：为数组元素分配内存
score =new int[5];
//第三步：为数组元素初始化
Random random =new Random();
for (int i =0; i < score.length; i++) {
score[i] = random.nextInt(40) +60;
}
//第四步：使用数组元素
int sum =0;
for (int i =0; i < score.length; i++) {
sum += score[i];
}
System.out.println(sum / score.length);
}
1.3一维数组的常用算法
1.3.1创建一个成绩的数据，统计最大值，最小值，平均值，求和
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int []score = new int[5];
//成绩初始化
for (int i = 0; i < score.length; i++) {
System.out.println("请输入第"+(i+1)+"个学生的成绩");
score[i]= s.nextInt();
}
//求最高分，求最低分
int max = score[0];
int min = score[0];
for (int i = 1; i < score.length; i++) {
if(max<score[i]){
max = score[i];
}
if(min>score[i]){
min = score[i];
}
}
System.out.println("最高分为"+max);
System.out.println("最低分为"+min);
//总分
int sum = 0;
for (int i = 0; i < score.length; i++) {
sum += score[i];
}
System.out.println("班级总分："+sum);
System.out.println("班级平均分"+sum/score.length);
}
1.3.2冒泡排序
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这样，最后的元素就会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
例：输入5个人的身高，用冒泡排序进行升序排列
public static void main(String[] args) {
//储存五个人的身高
int height[] =new int[5];
Scanner scanner =new Scanner(System.in);
//循环输入五个人的身高
for (int i =0; i < height.length; i++) {
System.out.println("请输入" + (i+1) +"个人的身高：");
height[i] = scanner.nextInt();
}
//定义临时变量
int temp;
//进行冒泡排序
for (int i =0; i < height.length; i++) {
for (int j =0; j < height.length -1 - i; j++) {
if (height[j]>height[j+1]){
temp = height[j];
height[j] = height[j+1];
height[j+1] = temp;
}
}
}
//将排序后的结果进行输出
System.out.println("5个人的身高从低到高依次是：");
for (int i =0; i < height.length; i++) {
System.out.print(height[i] +" ");
}
}
1.3.3选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
例：对80000个80000以内的随机数进行选择排序
public static void main(String[] args) {
//选择排序
int []arr =new int[80000];
Random random =new Random();
for (int i =0; i < arr.length; i++){
arr[i] =random.nextInt(80000);
}
for (int i =0; i < arr.length-1; i++) {
//每次循环都会找出最小的数
int minIndex = i;//记录最小的下表
int min = arr[i];//记录最小数
for (int j = i+1; j < arr.length; j++) {
if (arr[j]<min){
//如果当前数比最小数小，则更新最小数
min = arr[j];//更新最小数
minIndex = j;//更新最小数的下标
}
}
int temp = arr[i];
arr[i] = arr[minIndex];//将最小数放到最前面
arr[minIndex] = temp;
}
System.out.println(Arrays.toString(arr));
}
1.3.4插入排序
插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序。
例：对80000个80000以内的随机数进行插入排序
public static void main(String[] args) {
//插入排序
int[] arr =new int[80000];
for (int i =0; i <80000; i++) {
arr[i] =(int)(Math.random()*80000);
}
for (int i =1; i < arr.length; i++) {
int j = i;
while (j >0){
if (arr[j] < arr[j-1]){
int temp;
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
j--;
}else {
break;
}
}
}
System.out.println(Arrays.toString(arr));
}
1.3.5快速排序
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
例：对80000个80000以内的随机数进行快速排序
public static void main(String[] args) {
//快速排序
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++){
arr[i] = (int)(Math.random() * 80000);
}
//打印开始排序时的时间
long s = System.currentTimeMillis();
quickSort(arr,0,arr.length-1);
//打印排序结束时的时间
long e = System.currentTimeMillis();
System.out.println(e - s);
}
private static void quickSort(int[] arr, int first, int last) {
if (first >= last){
return;
}
int low = first;
int high = last;
//如果mid_value = arr[last]的话，下面的两个内部while循环就要换一下顺序
int mid_value = arr[first];
while (low < high){
while (low < high && arr[high] >= mid_value){
high -= 1;
}
arr[low] = arr[high];
while (low < high && arr[low] < mid_value){
low += 1;
}
arr[high] = arr[low];
}
arr[high] = mid_value;
//递归对左右两边的数据排序
quickSort(arr, first, low-1);
quickSort(arr, low+1, last);
}
1.3.6二分查找
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
例：
public static void main(String[] args) {
int num[] = {3,9,12,48,67};
int index = binarySearch(num,9);
System.out.println(index);
}
private static int binarySearch(int[] srcArray, int des) {
//定义初始最小、最大索引
int start = 0;
int end = srcArray.length - 1;
//确保不会出现重复查找，越界
while (start <= end){
//计算出中间索引值
int middle = (end + start)>>>1;//防止溢出
if (des == srcArray[middle]){
return middle;
//判断下限
}else if (des < srcArray[middle]){
end = middle - 1;
//判断上限
}else {
start = middle + 1;
}
}
//若没有，则返回-1
return -1;
}
1.4Arrays类的应用
JDK中提供了一个专门用于操作数组的工具类，即Arrays类，位于java.util包中。该类提供了一系列的方法来操作数组，如排序，比较，查询等。Arrays类常用方法如下表：
| 方法 | 返回类型 | 说明 |
|---|---|---|
| equals(array1,array2) | boolean | 比较两个数组是否相等 |
| sort(array) | void | 对数组array的元素进行排序 |
| toString(array) | String | 将一个数组array转换成一个字符串 |
| fill(array,val) | void | 把数组array的所有元素都赋值成val |
| copyOf(array,length) | 与array数据类型一致 | 把数组array复制成一个长度为length的新数组 |
| binarySearch(array,val) | int | 查询元素值val在数组array中的下标 |
1.4.1 比较两个数组是否相等equals()
public static void main(String[] args) {
//比较两个数组是否相等（equals）
int[] arr1 = {10,50,40,30};
int[] arr2 = {10,50,40,30};
int[] arr3 = {60,50,85};
System.out.println(Arrays.equals(arr1,arr2));//判断arr1和arr2的长度及元素是否相等
System.out.println(Arrays.equals(arr1,arr3));//判断arr1和arr3的长度及元素是否相等
}
1.4.2 对数组元素进行升序排序sort()
public static void main(String[] args) {
//对数组元素进行升序排列(sort)
int[][] score = new int[][] {{67,75},{78,93,82},{72,71}};
for (int i = 0; i < score.length; i++) {
String str = (i+1) + "班";
Arrays.sort(score[i]);
System.out.println(str + "排序后:");
for (int j = 0; j < score[i].length; j++) {
System.out.println(score[i][j]);
}
}
}
1.4.3 将数组转换成字符串toString()
public static void main(String[] args) {
//将数组转换成字符串(toString)
int[] arr = new int[]{10,50,40,30};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
}
1.4.4 将数组所有元素赋值为相同的值fill(array,vall)
public static void main(String[] args) {
//将数组所有元素赋值为相同的值(fill(array,vall))
int[] arr =new int[]{10,50,40,30};
Arrays.fill(arr,40);
System.out.println(Arrays.toString(arr));
}
1.4.5 将数组赋值成一个长度为设定值的新数组copy()
public static void main(String[] args) {
//将数组赋值成一个长度为设定值的新函数(copy)
int[] arr1 = new int[]{10,50,40,30};
//将arr1复制成长度为3的新数组arr2
int[] arr2 = Arrays.copyOf(arr1,3);
System.out.println(Arrays.toString(arr2));
//将arr1复制成长度为3的新数组arr2
int[] arr3 = Arrays.copyOf(arr1,4);
System.out.println(Arrays.toString(arr3));
//将arr1复制成长度为3的新数组arr3
int[] arr4 = Arrays.copyOf(arr1,6);
System.out.println(Arrays.toString(arr4));
}
1.4.6查询元素在数组中的下标binary(Object[],Object key)
public static void main(String[] args) {
//查询元素在数组中的下标(binary(Object[],Object key))
int[] arr = new int[]{10,50,40,30};
Arrays.sort(arr);//排序后：10,30,40,50
int index =Arrays.binarySearch(arr,40);
System.out.println(index);
index =Arrays.binarySearch(arr,0);
System.out.println(index);
index =Arrays.binarySearch(arr,45);
System.out.println(index);
index =Arrays.binarySearch(arr,90);
System.out.println(index);
}
2.二维数组
2.1二维数组的结构
例：分别计算每个人班级学生的总成绩
public static void main(String[] args) {
int[][] score = {
{65,75},
{78,82,93},
{71,72}
};
//定义保存总成绩的变量total
int total;
//遍历二维数组，计算每个班的总成绩
for (int i = 0; i < score.length; i++) {
String str = (i+1) + "班";
total = 0;
for (int j = 0; j < score[i].length; j++) {
total += score[i][j];
}
System.out.println(str + "总成绩" + total);
}
}
3.利用数组解决的问题
3.1 从键盘输入班级学员的数量，然后输入每一位学员的成绩，最后将成绩按从大到小进行排序输出，并计算平均值。
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入学员人数：");
int sum = 0;
int i =scanner.nextInt();
int score[] = new int[i];//定义数组
//数组初始化
for (i = 0; i < score.length; i++) {
System.out.println("请输入第" + (i+1) + "个学员的成绩：");
score[i] = scanner.nextInt();
}
//对数组元素进行排序
for (int j = 0; j < score.length-1; j++) {
for (int k = 0; k < score.length-j-1; k++) {
if (score[k]<score[k+1]){
int temp = score[k];
score[k] = score[k+1];
score[k+1] = temp;
}
}
}
System.out.println((i+1) + "个人的成绩从大到小依次是：");
for (int j = 0; j < score.length; j++) {
System.out.print(score[j] + " ");
}
System.out.println();
//计算总成绩
for (int j = 0; j < score.length; j++) {
sum += score[j];
}
System.out.println("该班级的总成绩为：" + sum);
}
3.2 定义如下数组 int[] array1=new int[]{34,45,56} ，编程实现向数组中再增加一个数字67。
public static void main(String[] args) {
int array1[] =new int[]{34,45,56};
int array2[] = Arrays.copyOf(array1,4);
array2[3] = 67;
System.out.println(Arrays.toString(array2));
}
3.3 将二维 int 类型的数组中每一行中最小的值取出，放到新的数组中。
public static void main(String[] args) {
int arr1[][] ={
{5,6,1,3},
{9,2,7,4},
{0,10,8}
};
int arr2[] = new int[arr1.length];
for (int i = 0; i < arr1.length; i++) {
Arrays.sort(arr1[i]);
arr2[i] = arr1[i][0];
}
System.out.println(Arrays.toString(arr2));
}
3.4 将二维 int 类型的数组中每一列中最小的值取出，放到新的数组中。
public static void main(String[] args) {
//定义二维数组arr1
int arr1[][] ={
{5,6,1,4},
{9,2},
{7,0,4,32},
{6,15}
};
//获取二维数组的最大行数
int max=0;
for (int i = 0; i < arr1.length; i++) {
if (max < arr1[i].length){
max = arr1[i].length;
}
}
//进行行列转换获得数组arr2
int arr2[][]=new int[max][arr1.length];
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr1[i].length; j++) {
arr2[j][i]=arr1[i][j];
}
}
//对每一行进行升序排列，并将每一行最小且不为0的值赋给一维数组arr3
int arr3[] = new int[arr2.length];
for (int i = 0; i < arr2.length; i++) {
Arrays.sort(arr2[i]);
for (int j = 0; j < arr2[i].length; j++) {
if (arr2[i][j] != 0){
arr3[i] = arr2[i][j];
break;
}
}
}
//将arr1中原本为0的且为其列最小的元素赋给arr3
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr1[i].length; j++) {
if (arr1[i][j] == 0){
if (arr3[j] > 0)
arr3[j] = 0;
}
}
}
System.out.println(Arrays.toString(arr3));
}
