一、数组高级练习
1.练习
(1).数组反转
/*
介绍:
数组的反转
数组中的元素颠倒顺序，例如原始数组为1,2,3,4,5，反转后的数组为5,4,3,2,1
思路:
数组最远端的元素互换位置
○ 实现反转，就需要将数组最远端元素位置交换
○ 定义两个变量，保存数组的最小索引和最大索引
○ 两个索引上的元素交换位置
○ 最小索引++，最大索引--，再次交换位置
○ 最小索引超过了最大索引，数组反转操作结束
*/
public class Test01 {
public static void main(String[] args) {
// 定义数组, 并初始化
int[] arr = {11, 22, 33, 44, 55, 66};
// 定义临时变量, 用于交换数组
int temp = 0;
// 反转数组, 只需要执行 arr.length / 次即可
for (int i = 0, j = arr.length - 1; i < arr.length / 2; i++, j--) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
System.out.println(Arrays.toString(arr));
}
}
(2).数组的动态扩容,删除,插入
/**
*
* 数组的动态操作:扩容,插入,删除
* 分析:
* 1.根据原来数组的长度创建一个新数组
* 2.进行原来数组中元素的转移
*
*/
public class Test05 {
public static void main(String[] args) {
// 定义数组, 并初始化数据
int[] arr = {51, 123, 15};
System.out.println("操作前: " + Arrays.toString(arr));
System.out.println("==========");
//扩容数据
arr = add(arr, 30);
System.out.println("扩容后: " + Arrays.toString(arr));
System.out.println("==========");
//插入数据
arr = insert(arr, 90, 1);
System.out.println("插入后: " + Arrays.toString(arr));
System.out.println("==========");
//删除数据
arr = delete(arr, 123);
System.out.println("删除后: " + Arrays.toString(arr));
}
/**
* 删除数据
* @param arr
* @param value
* @return
*/
private static int[] delete(int[] arr, int value) {
// 下标, 用来确定是否有该值
int index = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == value){
index = i;
break;
}
}
int[] deleteArr;
if (index == -1){
return arr;
}else {
deleteArr = new int[arr.length - 1];
}
// 下标, 用来确定是否有该值
for (int i = 0; i < deleteArr.length; i++) {
if (i >= index){
deleteArr[i] = arr[i + 1];
}else {
deleteArr[i] = arr[i];
}
}
return deleteArr;
}
/**
* 插入数据
* @param arr
* @param value
* @param index
* @return
*/
private static int[] insert(int[] arr, int value, int index) {
int[] insertArr = new int[arr.length + 1];
// 如果下标过大, 则排最后一个,
// 如果下标过小, 则排第一个
if (index >= insertArr.length) {
index = insertArr.length - 1;
}else if (index <= 0){
index = 0;
}
insertArr[index] = value;
for (int i = 0; i < arr.length; i++) {
if (index > i) {
insertArr[i] = arr[i];
} else {
insertArr[i + 1] = arr[i];
}
}
return insertArr;
}
/**
* 扩容数据
*
* @param arr
* @param i
* @return
*/
private static int[] add(int[] arr, int i) {
int[] addArr = new int[arr.length + 1];
for (int j = 0; j < arr.length; j++) {
addArr[j] = arr[j];
}
addArr[addArr.length - 1] = i;
return addArr;
}
}
2.十大内部排序算法
选择排序:
直接选择排序、堆排序
交换排序:
冒泡排序、快速排序
插入排序:
直接插入排序、折半插入排序、Shell排序
归并排序
捅式排序
基数排序
(1).冒泡排序
/*
原理
冒泡排序的原理非常简单, 它重复地走访过要排序的数列, 一次比较两个元素, 如果他们的顺序错误就把他们交换过来
思路
1.比较相邻的元素, 如果第一个比第二个大(升序), 就交换他们两个
2.对每一对相邻元素做同样的工作, 从开始第一对到结尾的最后一对, 这步做完后, 最后的元素会是最大的数
3.针对所有的元素重复以上的步骤, 除了最后一个
4.持续每次对越来越少的元素重复上面的步骤, 直到没有任何一对数字需要比较为止
*/
public class Test02 {
public static void main(String[] args) {
// 定义一个数组, 并初始化
int[] arr = {1,321,51,-3,-4,55,63,94};
// 进行数组排序
getArrayToSort(arr);
// 把最大的值排到最后
System.out.println(Arrays.toString(arr));
}
/**
* 用于冒泡排序
*/
private static void getArrayToSort(int[] arr) {
//定义一个变量, 用于交换数据
int temp;
// 进行循环, 冒泡排序
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]){
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
(2).选择排序
原理:
每一趟从待排序的数据中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕 。
思路:
给定数组：int[] arr={里面n个数据}；
第一趟排序，在待排序数据1~n中选出最小的数据，将它与数据1交换；
第二趟，在待排序数据2~n中选出最小的数据，将它与数据2交换；
以此类推，第i趟在待排序数据数据i~n中选出最小的数据，将它与数据i交换，直到全部排序完成。
public class Test09 {
public static void main(String[] args) {
// 定义数组, 并初始化数据
int[] arr = {1, 2, 8, 4, 9, 5, 5, 2, 8, 4, 9, 1};
// 选择排序
selectSort(arr);
// 排序后数据
System.out.println("排序后: " + Arrays.toString(arr));
}
private static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int index = i; //定义当前下标
// 因为要把最小的放在前面, 所以已经放在前的数可以不用在循环
for (int j = 1 + i; j < arr.length; j++) {
if (arr[index] > arr[j]){
// 如果下标位置大于 循环j的位置, 则改变index下标, 记录最小数的位置
index = j;
}
}
if (index != i){
// 如果index下标改变了, 则与i的位置进行交换, 把最小的数, 放在数组前面
int temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
}
}
}
(3).快速排序: 快!
介绍:
○ 快速排序由图灵奖获得者Tony Hoare发明, 被列为20世纪十大算法之一, 是迄今为止所有哦内排序算法中速度最快
的一种. 冒泡排序的升级版, 交换排序的一种, 快速排序的时间复杂度为O(nlog(n))
排序思想:
1.从数列中挑出一个元素, 称为"基准"(pivot)
2.重新排序数列, 所有元素比基准值小的摆放在基准前面, 所有元素比基准值大的摆在基准的后面(相同的数可以放
到任意一边), 在这个分区结束之后, 该基准就处于数列的中间位置, 这个称为分区(partition)操作
3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序
4.递归的最底部情形, 是数列的大小是零或一, 也就是永远都已经被排序好了, 虽然一直递归下去, 但是这个算法
总会结束, 因为在每次的迭代(iteration)中, 它至少会把一个元素摆到它最后的位置去
public class QuickSort {
private static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
private static void subSort(int[] data, int start, int end) {
if (start < end) {
int base = data[start];
int low = start;
int high = end + 1;
while (true) {
while (low < end && data[++low] - base <= 0)
;
while (high > start && data[--high] - base >= 0)
;
if (low < high) {
swap(data, low, high);
} else {
break;
}
}
swap(data, start, high);
subSort(data, start, high - 1);//递归调用
subSort(data, high + 1, end);
}
}
public static void quickSort(int[] data){
subSort(data,0,data.length-1);
}
public static void main(String[] args) {
int[] data = { 9, -16, 30, 23, -30, -49, 25, 21, 30 };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
quickSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
3.查找算法
(1).线性查找法: 慢!
// 一个数一个数的比较
public class Test03 {
public static void main(String[] args) {
// 定义数组, 并初始化数据
int[] arr = {11, 22, 33, 44, 55, 66};
int index = getIndexAsArray(arr, 44);
if (index == -1) {
System.out.println("没有找到该数据");
} else {
System.out.println("下标为: " + index);
}
}
private static int getIndexAsArray(int[] arr, int temp) {
for (int i = 0; i < arr.length; i++) {
if (temp == arr[i]) {
return i;
}
}
return -1;
}
}
(2).二分查找法:前提有序
/*
二分查找
对折对折再对折
要求
要求数组元素必须支持比较大小，并且数组中的元素已经按大小排好序
*/
public class Test04 {
public static void main(String[] args) {
// 定义一个数组, 并初始化
int[] arr = {10, 20, 30, 40, 50, 60, 70}; // 7 + 4 / 2 5
// 要查找的值
int value = 40;
// 判断是否找到了 , false 没有找到
int valueIndex = isFlag(arr, value);
if (valueIndex == -1) {
System.out.println("没有找到!!!");
} else {
System.out.println("找到了,下标为: " + valueIndex);
}
}
private static int isFlag(int[] arr, int value) {
//开始坐标
int start = 0;
// 结尾坐标
int end = arr.length - 1;
// 判断是否找到指定数据
int valueIndex = -1;
while (start <= end) {
int index = (start + end) / 2; //中间的下标
if (value == arr[index]) {
valueIndex = index;
break;
} else if (value > arr[index]) {
start = index + 1;
} else if (value < arr[index]) {
end = index - 1;
}
}
return valueIndex;
}
}
二、数组和方法的综合应用
1.可变参数
可变参数(JDK5.0)
含义:
在程序中,以实参为元素进行隐式静态初始化的数组
格式:
数据类型... 可变参数名
注意:
1.当方法除外可变参数外还有其他参数时,需要将可变参数声明在形参列表的最后一个位置,否则编译报错
2.一个方法最多只能有一个可变参数
修饰符 返回值类型 方法名(数据类型... 形参名){}
??其实与这个书写完全等价
修饰符 返回值类型 方法名(数据类型[] 形参名){}
使用方法注意：
??如果在方法书写时，这个方法拥有多参数，参数中包含可变参数，可变参数一定要写在参数列表的末尾位置。
2.方法形式参数和实际参数的特点
● 形参:
○ 在定义方法时方法名后面括号中的变量名称称为形式参数（简称形参），即形参出现在方法定义中。
● 实参:
○ 调用者方法中调用另一个方法时，方法名后面括号中的参数称为实际参数（简称实参），即实参出现在调用者方法中。
● 形式参数和实际参数的特点:
○ 方法的形参是基本数据类型时，形参值的改变不会影响实参；
○ 方法的形参是引用数据类型时，形参地址值的改变不会影响实参，但是形参地址值里面的数据的改变会影响实参。
三、二维数组
1.二维数组介绍
含义:
数组中的元素依旧是数组的数组
分类:
二维元素: 一维数组中的元素依然是一维数组
三维元素
四维元素
...
2.二维数组初始化
声明:
数据类型[][] 数组名; (推荐)
数据类型 数组名[][];
数据类型[] 数组名[];
初始化
动态初始化
格式1:
数据类型[][] 数组名 = new 数据类型[x][y];
格式2:
数据类型[][] 数组名 = new 数据类型[x][];
静态初始化
格式:
数据类型[][] 数组名 = {{N, N, N, ...}, {N, N, N, ...}, ...};
3.二维数组的元素访问和遍历
格式:
数据类型[x][y]
解释:
x: 元素所在一维数组在二维数组中的位置
y: 元素在一维数组中的索引
例如:
int[][] arr = {{1,2,3},{4,5},{6,7,8,9}};
arr[0][0] = 1;
arr[1][1] = 5;
遍历二维数组
for(int i = 0; i < arr.length; i++){
for(int j = 0; j < arr[i].length; j++){
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
4.操作二维数组的注意点
操作二维数组不应使用常数来控制维数。具体方法是array.length表示行数，
array[row].length来表示row行的列数。这样当数组行数和列数不相等时，代码可以自动调整为正确的值。
|