一、数组的常见操作
1、定义一个int类型的数组，里面包含10个元素，分别赋一些随机数，然后求出这10个元素的最大值、最小值、总和、平均值。
注：随机数公式：(数据类型)(最小值+Math.random()*(最大值-最小值+1))
public static void test01(){
//创建一维数组
int[] arrList = new int[10];
//赋区间随机值
for (int i = 0; i < arrList.length; i++) {
arrList[i] = (int)(Math.random() * (99 - 10 + 1) + 10);
}
//求最大值
int max = arrList[0]; //为了避免出现问题，最好将默认值设为数组中的一个元素
for (int i = 0; i < arrList.length; i++) {
if(arrList[i] > max){
max = arrList[i];
}
}
//求最小值
int min = arrList[0];
for (int i = 0; i < arrList.length; i++) {
if(arrList[i] < max){
min = arrList[i];
}
}
//求总和
double sum = 0;
for (int i = 0; i < arrList.length; i++) {
sum += arrList[i];
}
//求平均值
double average = sum / arrList.length;
//首先输出这个数组
System.out.print("这个数组序列为:");
for (int i = 0; i < arrList.length; i++) {
System.out.print(arrList[i] + "\t");
}
System.out.println("");
System.out.println("最大值为:" + max);
System.out.println("最小值为:" + min);
System.out.println("总和为:" + sum);
System.out.println("平均值为:" + average);
}
2、数组元素的赋值
案例1：使用二维数组打印一个10行的杨辉三角
代码如下所示：
/**
* 杨辉三角
* 规律：
* 第一列全部是1，每一行的最后一个元素为1
* 每一行从第二个元素开始，它的值等于头上两个数之和（偏左的两个数）
*
* */
public static void test04(){
//创建10行的二维数组
int[][] yangHui = new int[10][];
//初始化外层数组元素并且赋值
/**
* 给数组元素赋值
* 1、给每行的首末元素赋值为1（在创建数组的时候就进行赋值）
* 2、给非首末元素赋值：就是每一行从第二个元素开始，它的值等于头上两个数之和（偏左）
* */
for (int i = 0; i < yangHui.length; i++) {
yangHui[i] = new int[i + 1];
//给首末元素赋值
yangHui[i][0] = 1; //每行的首个元素为1
yangHui[i][i] = 1; //每行的末尾元素为1
//给非首末行元素赋值
for (int j = 1; j < yangHui[i].length-1; j++) {
yangHui[i][j] = yangHui[i-1][j] + yangHui[i-1][j-1]; //杨辉三角的规律
}
}
//遍历此时的二维数组，输出杨辉三角
for (int i = 0; i < yangHui.length; i++) {
for (int j = 0; j < yangHui[i].length; j++) {
System.out.print(yangHui[i][j] + "\t");
}
System.out.println();
}
}
案例2：创建一个长度为6的int类型的数组，要求数组元素的值都在1-30之间，且是随机赋值。同时满足数组里面的各个元素互不相同。
/**
* 解决思路：如果后面那个元素等于前面那个元素，就重新赋值
* */
public static void test05() {
//创建一维数组
int[] arr = new int[6];
//给一维数组赋值，按照条件赋值
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * (30 - 1 + 1) + 1);
if (i != 0) {
//如果后面那个元素等于前面那个元素，就重新赋值
while (arr[i - 1] == arr[i]) {
arr[i] = (int) (Math.random() * (30 - 1 + 1) + 1);
}
}
}
//输出此时的一维数组
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + "\t");
}
}
案例3：回形数
例：从键盘输入一个整数（1-20），则以该数字为矩阵的大小，把1,2,3..n^2的数字按照顺时针螺旋的形式填入举证中。
例如：输入数字4，则输出：
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
3、数组元素的复制、反转
4、数组的扩容与缩容
二、关于数组的常见算法
1、二分查找
代码如下：
/**
* 二分查找
* 前提：序列是有序的
*/
public static void test06() {
//给出一个有序数组
int[] a = new int[]{1, 5, 7, 9, 13, 18, 21, 26, 29, 30};
//给出需要查找的目标数据
int target = 7;
//给出首末索引
int head = 0; //首索引
int end = a.length - 1; //末索引
//结束条件是首索引小于等于末索引（或者定义判断的标志）
boolean isFind = false; //判断标志
int index = 0; //记录查找元素的下标
while (!isFind) {
//定义中间元素的索引
int middle = (head + end) / 2;
if (target == a[middle]) {
index = middle;
isFind = true;
break;
} else if (target > a[middle]) { //如果目标元素比中间元素大，就让首指针指向后一个元素
head = middle + 1;
} else {
end = middle - 1;
}
}
if (isFind) {
System.out.println("查找的目标元素为:" + a[index] + " 它在数组中的索引为:" + index);
} else {
System.out.println("没有找到相关元素!");
}
}
2、排序
衡量排序算法的优劣
时间复杂度!
空间复杂度：需要使用的辅助内存空间的大小
稳定性：若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的
2.1冒泡排序
==时间复杂度：O（n^2）==
代码如下所示：
/**
* 冒泡排序
* 动图可见如下博客：http://t.csdn.cn/7dIJi
*/
public static void test07() {
//生成一个随机10位的随机序列
int[] a = new int[10];
for (int i = 0; i < a.length; i++) {
a[i] = (int) (Math.random() * (100 - 1 + 1) + 1);
}
System.out.print("排序前的序列为:");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + "\t");
}
System.out.println();
//然后对这个序列进行冒泡升序排序
for (int i = 0; i < a.length; i++) {
boolean flag = true; //用于判断原序列是否已经排好序，假设已排好
for (int j = 0; j < a.length - i - 1; j++) {
int temp = 0;
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
//进入if判断语句，则说明原序列没有排好序，则需要修改排序判断标志
flag = false;
}
}
//如果flag为true，说明没有进入if判断语句里面，即没有进行排序，说明原序列已经是有序
if(flag){
break;
}
}
//循环输出排序后的序列
System.out.print("排序后的序列为:");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + "\t");
}
System.out.println();
}
2.2快速排序：20世纪十大算法之一
==时间复杂度：O（nlog2 n）==
基本思想:在一个序列中，随机挑选出一个数字（假设挑选第一个），然后将序列中的数字与它比较，比它小的放右边，比它大的放左边，然后在左右两边的序列中又各找一个数字出来，分别再次执行上述操作，直到最后排列完成
具体实现代码如下：
public class quickSub {
public static void main(String[] args) {
int[] arr = {3,5,2,1,43,33,22,64,74,25,13,27,98,56,100,21,7};
quickSort(arr);
for(int x : arr){
System.out.print(x + " ");
}
}
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array, int left, int right) {
//递归结束条件:这里代表只有一个根 大于号：有可能没有子树 1 2 3 4 1为基准，pivot-1就越界了
if(left >= right){
return;
}
int pivot = partition(array, left, right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
public static int partition(int[] array,int start, int end){
int i = start;//这里存开始时基准的下标，为了循环结束后，相遇值和基准值交换时能找到基准值的下标
int key = array[start];//这是基准
while (start < end){
while (start < end && array[end] >= key){
end--;
}
while (start < end && array[start] <= key){
start++;
}
swap(array,start,end);
}
//到这里s和e相遇，把相遇值和基准值交换
swap(array,start,i);
return start;//返回基准下标
}
public static void swap(int[] array, int n, int m){
int temp = array[n];
array[n] = array[m];
array[m] = temp;
}
}