数组相关简单算法
目录
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] + " ");
}
}
}快速排序，归排序，堆排序用前突击即可，想要做到和以上算法一样熟悉，需要经过一定的练习，因此本文暂时并不提供这三种算法的相关知识。