Java数组简述
数组
在定义数据的时候，大部分都是用变量来存储数据，如果程序中出现大量的数据，连续输入多个数字，连续输入多个坐标点，一般而言会创建多个变量存储这些数据，但是比较麻烦。
这些变量基本上类型是共通的，那我们就可以用一个容器将所有的数字进行管理，类似于字符串，字符串其实就是若干个字符的容器。
“abc”可以通过索引/角标来获取其中某一个字符。
[1，2，3，4，5]类似字符串也能够通过索引/角标来获取其中某一个数字，这样的一个容器我们就称之为数组。
为了方便，数组每一个空间都有角标。我们可以通过角标访问数据。
数组的定义
数组主要解决什么？
多变量多数据的存储问题，方便程序后期统一维护操作数据。
数组的本质
数组就是一系列空间大小相等且地址连续的一片空间。
为什么空间大小相等？
为了方便统一维护我们的数据，必须保证数据之间的类型是一样的。（多个同类型的空间连在一起组成的结构叫数组）
为什么空间的地址是连续？
为了方便统一操作我们的数据。
总结
- 数组就是一片地址连续且空间大小一致的空间
- 数据存在于堆内存中，但凡在堆内存中存储的数据称之为对象，数组也是对象的一种。但凡在堆内存中创建的对象都会有默认初始值：整数类型默认0、浮点数类型默认0.0、布尔类型默认false、引用数据类型（对象）默认null
- 数组提供角标来访问数组当中的元素
- 数组变量存的就是数组在堆内存中首元素的地址
- 数组通过角标来访问元素的具体计算方式是:所要访问的地址=首元素地址+角标*数据类型大小
- 数组一旦定义下来，其长度不可改变；数组中有几个地址就看数组中有几个元素空间
- 创建数组时必须明确规定大小或内容
数据类型[] 数组名=new 数组类型[长度]；创建数组只指定长度不指定内容
数据类型[] 数组名=new 数组类型{1，2，3，4，5}；创建数组指定内容（指定长度）
数据类型[] 数组名=new {1，2，3，4，5}；创建数组指定内容（指定长度）
[]表示一维数组
[] []表示两维数组
数组的内存分析
数组常见错误
ArrayIndexOutOfBoundsException 数组角标越界
超过了数组的长度，没有那一个角标
NullPointerException 空指针异常
数组对象没有任何变量引用它，数组对象在堆内存中就没有意义，所以该对象变成垃圾，有垃圾回收器（时JVM中的一个程序）处理。垃圾的处理不是即时的，由gc控制，当垃圾堆攒到一定程度时由gc处理。
基本数据操作
遍历
数组只有length一个属性
public static void bianli(){
int[] arr={1,2,3,4,5,6,7,8,9};//[0,8]
//数组只有一个唯一的属性 length 数组的长度
System.out.println(arr.length);
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
赋值
public static void fuzhi(){
Scanner scanner=new Scanner(System.in);
// System.out.print("请输入10个数字：");
int[] arr2=new int[10];
for(int i=0;i<arr2.length;i++){
System.out.print("请输入1个数字：");
arr2[i]=scanner.nextInt();
}
for(int i=0;i<arr2.length;i++){
System.out.print(arr2[i]+" ");
}
}
最大值/最小值
public static void maxormin(){
//计算最大值或最小值的 值
//计算最大值或最小值的 角标
//需求 获取最大的值10 获取最小值的角标4
int[] arr={10,2,8,3,1,6,4,7,9,5};
int max=arr[0];
int min_index=0;
for(int i=0;i<arr.length;i++){
if(arr[i]>max){
max=arr[i];
}
if(arr[i]<arr[min_index]){
min_index=i;
}
}
System.out.println("最大值"+max);
System.out.println("最小值角标"+min_index);
}
扩容
查找操作
查找某一个元素在数组中的位置
线性查找
public static void linearSearch(){
/*
最好情况 查10 1次就出来了
最坏情况 查5 10次才出来
当数组的长度越大的话 最坏情况越差
时间复杂度(最坏情况) O(n) 线性阶
*/
int[] arr={10,2,8,3,1,6,4,7,9,5};
int key=11;
int index=-1; //key元素不存在
for(int i=0;i<arr.length;i++){
if(arr[i]==key){
index=i;
break;
}
}
System.out.println(index);
}
二分查找
public static void binarySearch(){
//二分查找有个前提 数组必须有序
/*
最好情况 查46 1次就出来了
最坏情况 查12/60 O(logn)
*/
int[] arr={12,17,21,32,38,41,46,49,50,50,51,59,60};
int key=46;
int index=-1;
int min_index=0;
int max_index=arr.length-1;
int mid_index=(min_index+max_index)/2;
while(arr[mid_index]!=key){
if(key<arr[mid_index]){
max_index=mid_index-1;
}
if(arr[mid_index]<key){
min_index=mid_index+1;
}
if(min_index>max_index){
index=-1;
break;
}
mid_index=(min_index+max_index)/2;
}
System.out.println(mid_index);
}
斐波那契查找
排序操作
选择排序
当前元素和之后所有元素进行比较，如果当前大于后者，则交换。
每两个元素之间进行比较，将大的放在后面。
这样能够系统的将数据按大小进行排序，思路也比较清晰，但是会产生很多次比较。
public static void selectSort(){
int[] arr={8,5,9,2,7,4,6,1,3};
for(int i=0;i<arr.length-1;i++){//-1是因为没有必要进行最后一个数字的比较
for(int j=i+1;j<arr.length;j++){
if(arr[i]>arr[j]){
swap(arr,i,j);//即用-即释放
}
}
}
show(arr);
}
冒泡排序
从左到右两者之间依此进行比较，当前者比后者大时，前者和后者互换位置。
第一轮就可以确定最大值，第二轮再从新开始倒数第二的最大值找出来。
其实比较思想和计数排序相差不远，思路也比较清晰，但是也需要很多次的比较。
也有比较好的优化方法，在两两互比中，如果前者大于后者，前者在与后者后面依此计较。能够减少换位的次数。
public static void bubbleSort(){
int[] arr={8,5,9,2,7,4,6,1,3};
for(int i=0;i<arr.length-1;i++){//-1是少一轮比较
for(int j=0;j<arr.length-1-i;j++){//-1避免重复比较和角标越界
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
show(arr);
}
插入排序
如果当前的数字的左边有数字的话且左边的数字大于当前数字交换，再将小的数字依次与前边的进行比较直到小于时放在比它小的数字的后面。
这种方法类似于用两个指针，先确定一个数字，再与之前的数字进行比较。能够减少一定的比较和换位的次数。
public static void insertSort(){
int[] arr={8,5,9,2,7,4,6,1,3};
int e;
int j;
for(int i=1;i<arr.length;i++){
e=arr[i];
for(j=i;j>0&&arr[j-1]>e;j--){
arr[j]=arr[j-1];
}
arr[j]=e;
}
show(arr);
}
希尔排序
归并排序
快速排序
计数排序
先建立数组，将每一个空间的角标代表一个数字，在空间里存储对应角标的数据出现的次数。将数字和角标进行规整。
上述三个排序都是根据数据之间的大小关系进行比较排序的。
计数、基数和桶都是根据数据本身的特性比较，与大小无关的排序。
这些排序只针对整数。是利用空间去排序。
数字太大的话就会占用很多空间。
public static void countSort(){
int[] arr={8,5,9,2,7,4,6,1,3,10,-3,-2,-10};
int min=arr[0];
int max=arr[0];
for(int i=0;i<arr.length;i++){//O(n)
if(arr[i]>max){
max=arr[i];
}
if(arr[i]<min){
min=arr[i];
}
}
int[] nums=new int[max-min+1];
int offset=min;
for(int i=0;i<arr.length;i++){//O(n)
nums[arr[i]-offset]++;
}
int index=0;
for(int i=0;i<nums.length;i++){//O(m)
if(nums[i]!=0){
for(int j=0;j<nums[i];j++){
arr[index++]=i+offset;
}
}
}
show(arr);
}
二路快排
三路快排
基数排序
桶排序
二维数组