【Java小白图文教程】-05-数组和排序算法详解

 精品专题：

01.《C语言从不挂科到高绩点》课程详细笔记

https://blog.csdn.net/yueyehuguang/category_12753294.html?spm=1001.2014.3001.5482

02. 《SpringBoot详细教程》课程详细笔记

https://blog.csdn.net/yueyehuguang/category_12789841.html?spm=1001.2014.3001.5482

03.《SpringBoot电脑商城项目》课程详细笔记

https://blog.csdn.net/yueyehuguang/category_12752883.html?spm=1001.2014.3001.5482

04.《VUE3.0 核心教程》课程详细笔记

https://blog.csdn.net/yueyehuguang/category_12769996.html?spm=1001.2014.3001.5482

================================

||     持续分享系列教程，关注一下不迷路 ||

||                视频教程：墨轩大楼               ||

================================

1. 容器的概述

 如果需要完成一个学生成绩管理系统，有50名学生，需要计算50名学生的平均成绩，目前为止，可能考虑到的解决方法：定义50个变量分别表示每个 学生的成绩，然后将50个变量全部累加，除以总人数。针对于以上问题的解决方案显示是不合适的，因此需要有一个能够存储50个相同数据类型的容器

容器：是一种存储结构，现实生活中的容器：杯子，教室，公交车。。。

有关容器的概念关联一门课程：数据结构(数据存储的一种表现方式)

其中数据结构中最为简单的就是数组

2.数组入门

2.1 概述

数组是一种容器，用来存储一组相同数据类型的容器，是一种引用数据类型，从数据结构上来说数组是一种典型的线性结构

2.2 数组声明的语法

数据类型[] 数组名称

int a;//用来存储一个整形数据
//数组的声明
int[] arr;//用来存储一组整形数据
int arr2[];//用来存储一组整形数据(不推荐)double[] brr;
String[] strs;

2.3 数组的初始化

任何的局部变量再未初始化时是无法使用的，数组同理，也必须初始化之后才能使用，数组的初始化分为两种方式

1. 静态初始化
2. 动态初始化

2.3.1. 静态初始化

静态初始化指的是再声明数组的同时为数组指定元素：

int[] b = {1,2,3,4};

{}之间每个值都是数组中的一个元素，中间用逗号隔开(标点符号为英文输入法下的符号)

注意事项

以下声明方式是错误的

int[] arr;//用来存储一组整形数据
arr = {1,2,3,4};

以上的写法需要改为

int[] arr;//用来存储一组整形数据
arr = new int[]{1,2,3,4};

2.3.2 动态初始化

动态初始化即再声明数组的时候只指定数组的容量(空间大小)，但是不为数组指定具体的每一个元素

int[] c = new int[4];
//int[] d = new int[];//编译错误，使用动态初始化的时候必须给让容量

以上的写法，表示定义了一个容量为4的数组，数组中的每一个元素只能是整数

动态初始化一定要指定容量，否则编译错误

特别注意：数组一旦声明，他的容量是不可改变的

2.4 获取数组中的元素

2.4.1 数组的索引

数组中的每一个元素都有一个独一无二的索引(下标)位置，索引从0开始； 如果需要获取数组中的指定元素或者为数组中的指定元素赋值，都必须通过索引来完成，任何一个数组都有一个length(数组的元素的个数，也叫做数组的长度)属性

获取元素

通过数组名称加上对应位置的索引

数组名[索引]

//1.静态初始化
int[] b = {1,2,3,4};//2.动态初始化
int[] c = new int[4];int x = c[1];
int y = b[1];
System.out.println(x);
System.out.println(y);

在获取数组中元素的时候要注意索引的范围：0~ length -1，数组中元素的个数为length，最大的索引值为length-1，如果使用了一个超出范围的索引去获取元素，那么语法上是不会有问题，但是在运行过程中会出现java.lang.ArrayIndexOutOfBoundsException 异常(该异常表示数组下标越界异常)

数组元素赋值

使用数组索引除了可以获取元素之外，也可以通过索引为数组的指定位置赋值

//数组c的第三个元素赋值为100
c[2] = 100;
System.out.println(c[2]);

注意：数组元素的赋值过程中，你所赋值的元素一定要和数组中所存放的数据类型匹配

2.4.2 数组的遍历

在实际开发过程中经常需要将数组中的所有元素都获取到，如果我们单独的使用每一个元素的索引一个个 的去获取这样效率太低；已知数组的索引从0开始，并且数组的长度是有length属性的，因此使用循环语句就能轻松的实现对数组进行遍历

String[] strs = {"强哥","苍#null","翠花","凤姐"};for (int i = 0; i < strs.length; i++) {System.out.println(strs[i]);}
int i = 0;
while(i < strs.length){System.out.println(strs[i]);i++;
}int x = 0;
do{System.out.println(strs[x]);x++;
}while(x<strs.length);int[] arrs = {1,2,5,8,10,15,13,20};
//遍历出数组中不是5的倍数的元素
for (int j = 0; j < arrs.length; j++) {if(arrs[j]%5 != 0){System.out.println(arrs[j]);}
}

以上对数组的遍历方式都是使用常规的循环语句解决，在JDK1.5的时候，引进了一种全新的循环方式：增强for循环(forEach循环)，语法规则

for(数组中单个元素的数据类型 变量名:需要遍历的数组名){循环体
}

String[] strs = {"强哥","苍#null","翠花","凤姐"};
//这种forEach遍历方式就和索引没有什么直接关系了
for (String name:strs){System.out.println(name);
}

增强for循环的实现原理为:迭代器(类似于栈结构的线性存储结构)；元素的获取不需要通过索引完成，而是在使用迭代器的指针(游标)，依次往下迭代获取元素

forEach实际上是一种针对迭代器的语法糖技术

2.5 数据拷贝

由于数组存在弊端:数组的长度一旦定义就无法改变；但是对于一些特殊的需求，无法确定数组中元素的具体个数；针对这个问题，解决方案只有一种:初始化一个固定容量的数组，存储元素，一旦存储空间不足，则创建一个更大容量的新数组，将源数组中的元素拷贝到新的数组中，后续的元素向新数组中添加即可。因此以上的问题解决方案的关键在与:组数的拷贝

1. 使用传统循环实现数组的拷贝

int[] a = {3,4,5,6};
//{3,4,5,6,7}
//定义一个比原数组容量大一个的新数组
int[] b = new int[a.length+1];
//从原数组中每一个元素取出来赋值到新的数组的对应位置
for (int i = 0; i < a.length; i++) {b[i] = a[i];
}
//将新元素赋值到新数组的最后一个位置
b[b.length-1] = 7;
for (int x:b) {System.out.println(x);
}

1. 数组拷贝的方法

//原数组
int[] a = {3,4,5,6};
//新数组
int[] b = new int[7];
/*
参数1：原始数组对象
参数2：原始数组的初始拷贝位置(索引位置)
参数3：目标数组对象
参数4：目标数组的起始位置(索引位置)
参数5：拷贝的元素的个数
*/
System.arraycopy(a,0,b,0,a.length);
b[b.length-1] = 100;
for (int x:b) {System.out.println(x);
}

2.6 数组练习

1. 完成一个抽奖系统，要求从一组候选的名单中随机抽取一名幸运儿，表示中奖了，要求可以反复抽取，但是不能抽取到重复的幸运儿。

//自定义一个抽奖候选名单 0  1      2      3     4
String[] names = {"亮亮","佳文","雨立","豪哥","阿虎儿"};
//{"亮亮","佳文","豪哥","阿虎儿"}
//获取总人数
int con = names.length;
Scanner scanner = new Scanner(System.in);
//循环抽奖
while(con>0){System.out.println("按回车键抽取");scanner.nextLine();//获取一个随机索引int index = (int)(Math.random()*con);//获取幸运观众String name = names[index];System.out.println("恭喜你,"+name+"喜提编程题500道！！！");con--;//数组拷贝System.arraycopy(names,index+1,names,index,names.length-index-1);
}
System.out.println("抽奖结束");

1. 有一组数组{6，3，4，2，1，9，10，8}，按照元素的大小顺序从小到大输出 （排序）

3. 数组的排序

3.1 排序分类

1. 冒泡排序

算法思路：

1. 比较相邻的元素，如果第一个比第二个大，就交换位置
2. 对每一对相邻的元素做同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的元素
3. 针对所有的元素重复以上操作，除了最后一个
4. 重复盘1~3，直到排序完成

int[] arr = {6,3,4,2,1,9,10,8};
System.out.println("排序前：" + Arrays.toString(arr));for(int j = 1;j<arr.length;j++){//控制比较的轮数for (int i = 0;i<arr.length-j;i++){//每轮儿比较的次数//声明一个变量用作辅助int temp;if(arr[i]>arr[i+1]){//换位置temp = arr[i];arr[i] = arr[i+1];arr[i+1] = temp;}}System.out.println("第"+j+"轮结束：" + Arrays.toString(arr));
}//第一轮比较
/*for (int i = 0;i<arr.length-1;i++){//声明一个变量用作辅助int temp;if(arr[i]>arr[i+1]){//换位置temp = arr[i];arr[i] = arr[i+1];arr[i+1] = temp;}}System.out.println("第一轮结束：" + Arrays.toString(arr));//第二轮for (int i = 0;i<arr.length-2;i++){//声明一个变量用作辅助int temp;if(arr[i]>arr[i+1]){//换位置temp = arr[i];arr[i] = arr[i+1];arr[i+1] = temp;}}System.out.println("第二轮结束：" + Arrays.toString(arr));//第三轮for (int i = 0;i<arr.length-3;i++){//声明一个变量用作辅助int temp;if(arr[i]>arr[i+1]){//换位置temp = arr[i];arr[i] = arr[i+1];arr[i+1] = temp;}}System.out.println("第三轮结束：" + Arrays.toString(arr));*/

2. 插入排序

从第二个元素开始，每次都与前一个元素两两相比，若符合条件就交换位置

int[] arr = {6,3,4,2,1,9,10,8};
System.out.println("排序前：" + Arrays.toString(arr));for(int j=1;j<arr.length;j++){for(int i=j;i>0;i--){int temp;if(arr[i]<arr[i-1]){temp = arr[i];arr[i] = arr[i-1];arr[i-1] = temp;}}System.out.println("第"+j+"轮结束:" + Arrays.toString(arr));
}//第一轮
/*for(int i=1;i>0;i--){int temp;if(arr[i]<arr[i-1]){temp = arr[i];arr[i] = arr[i-1];arr[i-1] = temp;}}System.out.println("第一轮结束:" + Arrays.toString(arr));//第二轮for(int i=2;i>0;i--){int temp;if(arr[i]<arr[i-1]){temp = arr[i];arr[i] = arr[i-1];arr[i-1] = temp;}}System.out.println("第二轮结束:" + Arrays.toString(arr));*/

3. 选择排序

从第一个元素开始和后面的每一个元素做比较，符合条件就交换位置，一直比到最后一个，第二次就是从第二个元素开始和后面的每一个元素作比较，依次类推

int[] arr = {6,3,4,2,1,9,10,8};
System.out.println("排序前：" + Arrays.toString(arr));for(int j=0;j<arr.length-1;j++){for (int i=j;i<arr.length-1;i++){int temp;if(arr[j] > arr[i+1]){temp = arr[j];arr[j] = arr[i+1];arr[i+1] = temp;}}System.out.println("第"+j+"轮结束：" + Arrays.toString(arr));
}/*for (int i=0;i<arr.length-1;i++){int temp;if(arr[0] > arr[i+1]){temp = arr[0];arr[0] = arr[i+1];arr[i+1] = temp;}}System.out.println("第一轮结束：" + Arrays.toString(arr));for (int i=1;i<arr.length-1;i++){int temp;if(arr[1] > arr[i+1]){temp = arr[1];arr[1] = arr[i+1];arr[i+1] = temp;}}System.out.println("第二轮结束：" + Arrays.toString(arr));for (int i=2;i<arr.length-1;i++){int temp;if(arr[2] > arr[i+1]){temp = arr[2];arr[2] = arr[i+1];arr[i+1] = temp;}}System.out.println("第三轮结束：" + Arrays.toString(arr));
*/

4. 归并排序

算法思路： 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

1、把长度为n的输入序列分成两个长度为n/2的子序列；

2、对这两个子序列分别采用归并排序；

3、将两个排序好的子序列合并成一个最终的排序序列。

5. 快速排序

算法思路： 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。

1. 从数列中挑出一个元素，称为 “基准”（pivot）；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

6. 堆排序

算法思路：

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

7. 希尔排序

算法思路：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度