-
什么是数组？
（1）数组是计算机中最基本的数据结构之一，我们会用一些名为索引的数字来标识每项数据在数组中的位置。
（2）大多数编程语言中索引是从0开始的。
（3）数组在内存中是存在连续的地址中的。 -
数组的特点
（1）计算机可以一步跳到任意一个内存地址上。
（2）数组本身会记有第一个内存的地址，因此计算机知道数组的开头在哪里。
（3）数组索引从0开始算起。 -
数组查找
数组查找某个值的时候只能从前往后线性查找。 -
数组插入
（1）如果只是在数组末尾插入，直接算出最后一个内存地址 插入。
（2）如果是在开头或者结尾插入，则需要移动其他元素的位置，腾出准备插入元素的位置。 -
数组删除
同数组插入相同
（1）如果只是在数组末尾插入，直接算出最后一个内存地址 插入。
（2）如果是在开头或者结尾插入，则需要移动其他元素的位置，腾出准备插入元素的位置。 -
集合
集合是一种不允许元素重复的数据结构。 -
集合查找
同数组的查找相同。数组查找某个值的时候只能从前往后线性查找。 -
集合插入
在插入时要先查找，确认集合中没有要插入的元素。
（1）如果只是在数组末尾插入，直接算出最后一个内存地址 插入。
（2）如果是在开头或者结尾插入，则需要移动其他元素的位置，腾出准备插入元素的位置。 -
集合删除
同数组删除相同。
（1）如果只是在数组末尾插入，直接算出最后一个内存地址 插入。
（2）如果是在开头或者结尾插入，则需要移动其他元素的位置，腾出准备插入元素的位置。 -
常见的排序列表
-
各类排序算法java实现
public class Test {public static void main(String[] args) {int[] arr= {11,2,5,7,4,0,3,6,89,5,9,8,1,45};Test ts=new Test();System.out.print("原数组：");ts.toString(arr); long before=System.currentTimeMillis();//记录当前时间(毫秒),算法开始时间System.out.print("选择排序：");ts.selectSort(arr);
// System.out.print("冒泡排序：");
// ts.bubbleSort(arr);
// System.out.print("插入排序：");
// ts.insertSort(arr);
// System.out.print("快速排序：");
// ts.quickSort(arr);
// ts.toString(arr,0,arr.length);
// System.out.print("归并排序：");
// ts.mergeSort(arr);
// ts.toString(arr,0,arr.length);
// System.out.print("堆排序：");
// ts.heapSort(arr);
// System.out.print("希尔排序：");
// ts.shellSort(arr);
// System.out.print("基数排序：");//鲁棒性不强,需要数组中元素都为相同的位数
// ts.radixtSort();
// System.out.print("计数排序：");
// ts.countSort(arr);
// System.out.print("桶排序：");
// ts.bucketSort(arr);long after=System.currentTimeMillis();//算法结束时间long time=after-before;//时间差作为算法消耗时间System.out.println("算法所用时间："+time);//打印}//选择排序 平均时间复杂度：n^2 不稳定 空间复杂度：1public void selectSort(int[] arr) {for(int i=0;i<arr.length-1;i++) {int minPos=i;//假设最小值最初在0的位置for(int j=i+1;j<arr.length;j++) {
// if(arr[i]<arr[minPos]) {
// minPos=i;
// }//优化minPos=arr[j]<arr[minPos] ? j:minPos;}swap(arr,i,minPos);}toString(arr);}//冒泡排序 平均时间复杂度n^2 稳定 空间复杂度：1public void bubbleSort(int[] arr) {for(int i=0;i<arr.length-1;i++) {for(int j=i+1;j<arr.length;j++) {if(arr[i]>arr[j]) {swap(arr,i,j);}}}toString(arr);}//插入排序 平均时间复杂度n^2 稳定 空间复杂度：1public void insertSort(int[] arr) {for(int i=1;i<arr.length;i++){for(int j=i;j>0;j--) {if(arr[j]<arr[j-1]) {swap(arr,j,j-1);}}}toString(arr);}//快速排序 平均时间复杂度 n log2(n) 不稳定 空间复杂度：log2(n)public void quickSort(int[] arr,int left,int right) {if(left>=right) return;int mid=partition(arr,left,right);quickSort(arr,left,mid-1);quickSort(arr,mid+1,right);}public int partition(int[] arr ,int left,int right) {int pivot=arr[right];int l=left;int r=right;while(l<r) {while(l<=r && arr[l]<=pivot) l++;while(l<=r && arr[r]>pivot) r--;if(l<r) swap(arr,l,r);}arr[l]=pivot;return l;}//归并排序 平均时间复杂度 n log2(n) 稳定 空间复杂度：npublic void mergeSort(int[] arr,int left,int right) {//将基本有序的数组进行合并//java 和python内部都是用的该方法if(left>=right) return;//分成两半int mid=(right+left)/2;//左边排序mergeSort(arr,left,mid);//右边排序mergeSort(arr,mid+1,right);//左右归并merge(arr,left,mid,right);}public void merge(int[] arr,int left,int mid,int right) {int[] temp=new int[right-left+1];int i=left;int j=mid+1;int k=0;//计数，统计存入新数组的元素个数// 把较小的数先移到新数组中while(i<=mid && j<=right) {temp[k++]=arr[i]<arr[j]?arr[i++]:arr[j++];}// 把左边剩余的数移入数组 while(i<=mid) {temp[k++]=arr[i++];}// 把右边边剩余的数移入数组while(j<=right) {temp[k++]=arr[j++];}for(int m=0;m<temp.length;m++) {arr[left+m]=temp[m];} }//堆排序 平均时间复杂度 n log2(n) 不稳定 空间复杂度：1public void heapSort(int[] arr) {toString(arr);}//希尔排序 平均时间复杂度 n^1.3 不稳定 空间复杂度：1public void shellSort(int[] arr) {//按照一定的间隔排序,其他地方同插入排序相同
// int gap=4;//设定初始间隔 ——》增加for循环，优化代码int h=1;while(h<=arr.length/3) {h=h*3+1;}for(int gap=h;gap>0;gap=(gap-1)/3) {for(int i=gap;i<arr.length;i++) {for(int j=i;j>0;j--) {if(arr[j]<arr[j-1])swap(arr,j,j-1);}}}toString(arr);}//基数排序平均时间复杂度 n+k 稳定 空间复杂度：n+kpublic void radixtSort() {//待完善,有bugint[] arr= {412,240,115,305,430,124,11,25};int[] result=new int[arr.length];//先求最高位数int max=arr[0];//初始最大值int maxIndex=0;//初始化最大值位数//获取最大值for (int c=0;c<arr.length;c++) {if(max<arr[c]) {max=arr[c];}}//获取最大值位数while(max!=0) {max=max/10;maxIndex++;}for(int i=0;i<maxIndex;i++) {int devision=(int)Math.pow(10, i);int[] count=new int[10];for(int j=0;j<arr.length;j++) {int num=arr[j]/devision%10;count[num]=count[num]+1;//存储每个元素的位数}for(int m=1;m<count.length;m++) {count[m]=count[m]+count[m-1];}for(int n=arr.length-1;n>=0;n--) {int num=arr[n]/devision%10;result[--count[num]]=arr[n];} }toString(result);}//计数排序平均时间复杂度 n+k 稳定 空间复杂度：n+kpublic void countSort() {//同基数排序不同,鲁棒性不强int[] arr= {5,2,1,6,9,4,5};int[] result=new int[arr.length];int[] count=new int[10];for(int i=0;i<arr.length;i++) {count[arr[i]]++;}for(int i=1;i<count.length;i++) {count[i]=count[i]+count[i-1];}for(int i=arr.length-1;i>=0;i--) {result[--count[arr[i]]]=arr[i];}toString(result);}//桶排序平均时间复杂度 n+k 稳定 空间复杂度：n+kpublic void bucketSort(int[] arr) {toString(arr);}//打印数组函数public void toString(int[] arr) {for (int i=0;i<arr.length;i++) {System.out.print(arr[i]);if(i<arr.length-1) {System.out.print(",");}else {System.out.println();}}}//转化函数public void swap(int[] arr,int i,int j) {int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}
}
![[网鼎杯 2020 白虎组]PicDown(任意文件读取)](https://img-blog.csdnimg.cn/a14cb4dd6ec5410dbbd7d561c2a2ae4d.png)
