数组相关简单算法

目录

 1. 数据结构与算法

2. 数组中涉及的算法

2.1

2.2 数值型数组相关运算

 2.3 数组赋值

2.4 数组复制/反转

2.5 数组查找

 2.6 排序

---

 1. 数据结构与算法

《数据结构与算法》是大学些许专业的必修或选修课，主要包含两方面知识：

（1）数据与数据之间的逻辑关系：

集合，一对一，一对多，多对多；

（2）数据的存储结构：

集合结构：

线性结构：顺序表，链，栈，队列；

树形结构：二叉树

图状结构：

2. 数组中涉及的算法

（1）数组元素的赋值（杨辉三角，回形数等）；

（2）求数值型数组的最大值，最小值，和以及平均数；

（3）数组的复制，反转，查找（线性查找，二分法查找）；

（4）数组元素的排序算法；

算法的五大特性：

2.1

创建一个长度为 6 的 int 型数组，要求取值为 1-30，同时元素各不相同；

2.2 数值型数组相关运算

定义一个 int 型的一维数组，包含 10 个元素，分别赋一个两位数的随机整数，求出所有元素的最大值，最小值，和以及平均值；

class suanShu {public static void main(String[] args) {int [] a = new int [10];for(int i = 0;i < a.length;i++){a[i] = (int)(Math.random()*100);System.out.print(a[i]+" ");if(i==a.length-1){System.out.println(" ");}}int max = a[0] ;int min = a[0];int sum = 0;for(int i = 0;i < a.length;i++){if(max < a[i]){max = a[i];}if(min > a[i]){min = a[i];}sum += a[i];}System.out.println("最大值为："+max);System.out.println("最小值为："+min);System.out.println("和值为："+sum);System.out.println("平均值为："+(sum / a.length));}
}

 2.3 数组赋值

class ArrayExer2 {public static void main(String[] args){int array1[],array2[];//优化array1 = new int[]{2,3,5,7,11,13,17,19};for(int i = 0;i < array1.length;i++){System.out.print(array1[i]+" ");if(i==array1.length-1){System.out.println(" ");}}array2 = array1;for(int i = 0;i < array2.length;i++){if(i % 2 == 0){array2[i] = i;}}for (int i = 0;i < array1.length;i++){System.out.print(array1[i]+" ");}}
}

 注意：array1 与 array2 的地址值相同，都指向堆内存中的同一数组； 

2.4 数组复制/反转

//数组的复制/反转
class complex {public static void main(String[] args){String[] str = new String[]{"11","22","33","44","55","66","77"};String[] str1;str1 = new String[str.length];//堆中新开辟空间/*区别于数组的赋值int array1[],array2[];array1 = new int[]{2,3,5,7,11,13,17,19};array2 = array1;*/for(int i = 0;i < str.length;i++){str1[i] = str[i];System.out.print(str1[i]+" ");if(i == str.length-1){System.out.println(" ");}}//       数组反转for (int i = 0;i < str1.length / 2;i++){String temp ;temp = str1[i];str1[i] = str1[str.length-i-1];str1[str.length-i-1] = temp;}for(int i=0;i < str1.length;i++){System.out.print(str1[i]+" ");}}
}

2.5 数组查找

(1) 线性查找；

//数组线性查找
class Select{public static void main(String[] args){String[] arr = new String[]{"1","3","5","7","9","11","13","15","17","19"};String dest = "19";boolean isFlag = true;for (int i = 0;i < arr.length;i++){if(dest.equals(arr[i])){System.out.println("索引为:"+i);isFlag = false;break;}}if(isFlag){System.out.println("很遗憾，没有查找到该数据");}}
}

 （2）二分法查找；

前提：排序；

适用于大量数据

如下：在整型一维数组 a 中查找 b 的位置；

class devideS{public static void main(String[] args){int[] a = new int[]{1,3,5,7,9,11,13,15,17,19,22};int b = 17;int head = 0;int end = a.length-1;boolean isfact = true;while(head <= end){int middle = (head + end) / 2;if(a[middle] == b){System.out.println("该元素地址为：" + middle);isfact = false;break;}else if(a[middle] < b){head = middle + 1;}else if(a[middle] > b){end = middle - 1;}}if(isfact){System.out.println("很抱歉，没有找到的啦！");}}
}

 2.6 排序

1. 内部排序：在内存中完成的排序算法（10种）

选择排序：直接选择排序，堆排序

交换排序：冒泡排序，快速排序

插入排序：直接插入排序，折半插入排序，Shell排序

归并排序；

桶式排序；

基数排序；

2. 外部排序：借助外部存储设备完成的排序

冒泡排序（平均时间复杂度：O（n2））：

class MP{
//    5 30  15  2
//    第一轮: 5  15  2   30    交换三次
//    第二轮: 5  2   15  30    交换二次
//    第三轮: 2  5   15  30    交换一次    排序完毕public static void main(String[] args){int[] a = new int[]{1,5,14,9,2};
//        n个数（n-1）轮即可排完for(int i = 0;i < a.length - 1;i++){
//            每轮都会沉底一个较大数，交换次数会减少for(int j = 0;j < a.length - 1 - i;j++){int temp = 0;if(a[j] < a[j+1]){temp = a[j];a[j] = a[j+1];a[j+1] = temp;}}}for(int i = 0;i < a.length;i++){System.out.print(a[i] + " ");}}
}

 快速排序，归排序，堆排序用前突击即可，想要做到和以上算法一样熟悉，需要经过一定的练习，因此本文暂时并不提供这三种算法的相关知识。