1.数组
1.1数组的定义
数组(Array)是有序的多个元素序列。元素是数组的每一个数据，这些元素都是相同类型的，且是在内存中连续存储的，多个的。在Java中用 [] 表示数组。
1.2数组的下标
下标是数组元素在数组中的位置。在一个数组中，数组下标是用整数表示的，从0开始，依次累计加一。数组下标也叫索引(index)；数组下标的界限：0 到数组长度 - 1。数组下标如果为负数，或者下标超过了数组长度 - 1，此时会发生数组下标越界。（ArrayIndexOutOfbounds）
1.3数组的长度
数组中元素的个数，数组的长度也叫数组的大小，获取数组长度的方法：数组名.length；数据大小是在为数组元素分配内存时确定的大小，大小不可改变。如果想改变数组大小，就要重新定义一个数组。
1.4数组的使用
分为四步：
第一步：定义数组
第二部：为数组分配内存
第三步：初始化数组，也就是给数组赋值
第四步：使用数组
实列：班级5个学生，求成绩的平均分
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);
}
运行结果：84
内存的分配如下：
image.png
数组在内存中的分配情况：定义一个数组就是在栈中给它分配一个内存，在栈中数组的值其实不是真正的值，它是一个地址编号；在给数组初始化就是在堆中分配一个连续的内存空间，内存空间的首个地址编号赋值给数组。
1.5数组的数据结构
数组的数据结构也称为线性表，全名为线性存储结构。使用线性表存储数据的方式可以这样理解，即“把所有数据用一根线儿串起来，再存储到物理空间中”。
如下图就是线性表的存储结构：
image.png
数组的常用算法:
1.求最大值
2.最小值
3.平均值
4.求和。
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
//创建成绩数组和成绩初始化
int score[]= new int[]{78, 67, 90, 79, 100};
//求最高分，求最低分
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);
}
运行结果：
最高分为100
最低分为67
班级总分：414
班级平均分82
1.6数组排序：
1.冒泡排序：
对80000个随机数进行冒泡排序
public static void main(String[] args) {
//冒泡排序
int score[] = new int[80000];
Random random = new Random();
for (int i = 0; i < score.length; i++) {
score[i] = random.nextInt(80000);
}
long start = System.currentTimeMillis();
for (int i = 0; i < score.length-1; i++) {
for (int j = 0; j < score.length-i-1; j++) {
if(score[j]>score[j+1]){
int tmp = score[j];
score[j]=score[j+1];
score[j+1]= tmp;
}
}
}
long end = System.currentTimeMillis();
System.out.println(end-start);
/*for (int i = 0; i < score.length; i++) {
System.out.println(score[i]);
}*/
}
运行效率：80000个数使用选择排序大约用时8450毫秒（不同电脑运行的效率不同）
2.选择排序：
对80000个随机数进行选择排序
public static void main(String[] args) {
//选择排序
int[] arr = new int[80000];
Random r = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = r.nextInt(80000);
}
long start = System.currentTimeMillis();
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 tmp = arr[i];
arr[i] = arr[minIndex];//将最小数放到最前面
arr[minIndex] = tmp;
}
long end = System.currentTimeMillis();
System.out.println(end-start);
System.out.println(Arrays.toString(arr));
}
运行效率：80000个数使用选择排序大约用时1800毫秒（不同电脑运行的效率不同）
3.插入排序：
对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 start = System.currentTimeMillis();
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;
//System.out.println(Arrays.toString(arr));
j--;
}else {
break;
}
}
}
long end = System.currentTimeMillis();
System.out.println(end -start);
}
运行效率：80000个数使用插入排序大约用时700毫秒
4.快速排序：
对80000个随机数进行快速排序
public static void main(String[] args){
//快速排序
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int)(Math.random() * 800000);
}
//打印开始排序时的时间
long s = System.currentTimeMillis();
quickSort(arr,0,arr.length-1);
//打印排序结束时的时间
long e = System.currentTimeMillis();
System.out.println(e-s);
}
public 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);
}
运行效率：80000个数使用快排大约用时20毫秒。
分析：快速排序的运行效率最高，冒泡的运行效率最低。
5.其它排序方法：
(1)冒泡排序；
(2)选择排序；
(3)插入排序；
(4)希尔排序；
(5)归并排序；
(6)快速排序；
(7)基数排序；
(8)堆排序；
(9)计数排序；
(10)桶排序
(11)二叉树排序
6 数组中查找数据：
一般用二分查找法。
二分法查找：
public static void main(String[] args){
int num[] = {3,9,12,48,67};
int index = binarySearch(num,9);
System.out.println(index);
}
public 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;
}
2.数组的工具类java.util.Arrays类
2.1比较两个数组是否相等:Arrays.equals(数组名,数组名)
public static void main(String[] args) {
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的长度及元素是否相等
}
2.2对数组元素进行升序排序:Arrays.sort(数组名)
public static void main(String[] args){
int []arr1 = {10,50,40,30};
Arrays.sort(arr1);
for (int i = 0; i < arr1.length; i++) {
System.out.println(arr1[i]);
}
}
2.2.1数组指定下标范围排序
public static void main(String[] args){
int []arr1 = {10,50,40,30,89,67,4,678};
Arrays.sort(arr1,3,arr1.length-1);//从数组的第三个数开始排序，排到最后一个数
for (int i = 0; i < arr1.length; i++) {
System.out.println(arr1[i]);
}
}
2.3将数组所有元素赋值为相同的值:Arrays.fill(数组名，你想赋的值)
public static void main(String[] args){
int []arr1 = {10,50,40,30,89,67,4,678};
Arrays.fill(arr1,30);
System.out.println( Arrays.toString(arr1));
}
运行结果：
[30, 30, 30, 30, 30, 30, 30, 30]
2.4将数组赋值成一个长度为设定值的新数组:Arrays.copyOf(数组名，新的数组的长度)
public static void main(String[] args){
int []arr1 = new int[] {10,50,40,30 };
//将arr1复制成长度为3的新数组arr2
int []arr2 = Arrays.copyOf(arr1,3);
System.out.println(Arrays.toString(arr2));
}
运行结果：
[10, 50, 40]
2.5查询元素在数组中的下标:Arrays.binarySearch(数组名，查找的值)
public static void main(String[] args){
int []arr = new int[] {10,50,40,30 };
Arrays.sort(arr);//排序后 10 30 40 50 90
int index = Arrays.binarySearch(arr, 10);
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);
}
运行结果：
0
-1
-4
-5
分析：
1.若找到了数据，则返回该数据的下标
2.若找不到数据，则返回负数，其值为该数据在数组中排序的位置
以上讲的都是一维数组的操作，还有二维数组和多维数组。
3 二维数组
3.1二维数组的数据结构：
数组类型 [] [] 数组名
或者
数组类型 数组名 [] []
[] [] 表示二维数组，前面的[] 表示第一维，后面的[] 表示第二维
示例：
定义一个整型的二维数组
int[][]s;
为二维数组元素分配内存
int[][]s=newint[3][3];
