数组的CRUD操作 和 排序 查询算法【重点】
CRUD:
Read 查询:
1. int[] arr = {1, 2, 4, 5, 6, 7, 8, 9, 10};
静态创建数组。请用代码告诉我元素3的下标是多少???
2. 用户输入10个数保存到数组中(函数)， 利用函数找出数组中，最大值所在下标(唯一最大
值)以及最大值是什么?
3. 找出数组中的最大值，放到数组中下标为0的元素位置。 (选择排序算法推演)
4. 找出数组中的所有的最大值下标
.
Update 修改
项目中来讲修改！！！
Create 增加
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 0};
要求:
1. 数组是排序完整的，从小到大排序
2. 0是无效元素!!!
3. 增加数据，不能影响原本的数组从小到大的排列顺序1
添加操作:
情况1:
添加一个 10，放入到原本是11的位置，也就是说在9之后
{1, 3, 5, 7, 9, 10, 11, 13, 15, 17};
10在index = 5 之后的元素整体向右移动 移动了4个数据
情况2:
添加一个9，放入到原本是11的位置
{1, 3, 5, 7, 9, 9, 11, 13, 15, 17};
9在index = 5，之后的元素整体向右移动 移动了4个数据
情况3:
添加一个20，放入到17之后，数组中没有任何元素大于20
{1, 3, 5, 7, 9, 11, 13, 15, 17, 20};
20在index = 9 ，数组不用移动任何元素
添加流程:
1. 确定数据放入的位置
找出数组中第一个比要插入数据大的元素，该元素所在下标就是要放入数据的位置
如果没有任何一个元素大于要插入的数据，那么这个数据放入到数组的末尾
2. 考虑数组的移动问题
移动的方式，是从最后一个元素开始，到目标位置，从后往前挨个向右移动一位
如果该数是放入到数组的末尾，那么不需要移动操作
3. 把要插入的数据，放入到数组中
Delete 删除
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
要求:
1. 0是无效元素，可以在删除过程中，用于填充空位
2. 删除操作，不能影响原本数据的排列
删除操作:
情况1:
删除 17 index = 8 之后的元素要向左移动 1位
{1, 3, 5, 7, 9, 11, 13, 15, 19, 0};
情况2:
删除 11 index = 5 之后的元素要向左移动 4位
{1, 3, 5, 7, 9, 13, 15, 17, 19, 0};
情况3:
删除19 index = 9 不需要 向左移动
{1, 3, 5, 7, 9, 11, 13, 15, 17, 0};
情况4:
删除 2 没有该数据，无法删除
删除流程:
1. 要找到删除数所在下标
存在该数，不存在该数
2. 删除操作
3. 最后的数据换成0 占位，表示无效数据
class Demo1 {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int index = indexOf(null, 11);
if (index != -1) {
System.out.println("index = " + index);
} else {
System.out.println("Not Found!");
}
int[] array = {1, 3, 5, 7, 9, 2, 4, 6, 8};
int maxIndex = getIndexOfMaxInArray(array);
if (maxIndex != -1) {
System.out.println("Max is " + array[maxIndex] + " at " + maxIndex);
} else {
System.out.println("函数运行GG!");
}
}
/*
找出数组中最大值以及下标
*/
/**
*找出数组中最大值所在下标
*@param arr 要查询最大值所在下标的int类型数组
*@return int 类型，返回最大值所在下标，返回-1，表示函数运行失败
* 失败原因：1. 传入的地址为null, 2. 数组的元素个数为0
*/
public static int getIndexOfMaxInArray(int[] arr) {
//参数合法性判断
if (null == arr || arr.length == 0) {
System.out.println("传入参数不合法!");
return -1; //函数运行失败
}
//假设下标为0的元素是最大值所在下标
int index = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[index] < arr[i]) {
index = i; //找出比index下标大于的元素所在下标，保存到index 中
}
}
return index;
}
/*
在数组array中，找到目标数据find
*/
/**
*在目标int类型数组array中，找出指定的数据find所在下标
*@param array 要进行查询操作的int类型数据
*@param find 要查找的int类型数据
*@return 返回值是int类型，返回大于等于0的数据，表示找到了find
* 所在下标，如果返回-1，表示函数运行失败或者没有找到
* 失败原因：1. 传入的地址为null, 2. 数组的元素个数为0
*/
public static int indexOf(int[] array, int find) {
//参数合法性判断
if (null == array || array.length == 0) {
System.out.println("传入参数不合法!");
return -1; //表示函数运行失败
}
//定义一个变量
int index = -1;
for (int i = 0; i < array.length; i++) {
if (find == array[i]) { //找到了对应元素
index = i; //把下标保存到index
break; //终止循环
}
}
return index;
}
}
import java.util.Scanner;
class Demo2 {
public static void main(String[] args) {
int[] arr = new int[10];
//1 2 3 4 5 6 7 8 9 10
System.out.println("请输入10个数:");
getNumberFromKeyboard(arr);
/*putMaxAtZeroIndex(arr);
putRestOfMaxAtOneIndex(arr);
putRestOfMaxAtTwoIndex(arr);*/
selectSort(arr);
printIntArray(arr);
}
/*
SelectSort 选择排序算法 (五大常用排序算法第三) 5 ~ 6
*/
/**
*选择排序算法
*@param int[] 要进行选择排序的数组
*@return boolean 返回true表示函数运行成功
* 返回false表示函数运行失败
*/
public static boolean selectSort(int[] arr) {
//参数合法性判断
if (null == arr || arr.length == 0) {
System.out.println("Input param is invalid!");
return false;
}
//for i 外层循环控制要进行查询交换的次数
for (int i = 0; i < arr.length - 1; i++) {
int index = i; //假设的最大值位置，同时i值也是目标数据要放入的位置
//找出剩余为排序数据的最大值
for (int j = i + 1; j < arr.length; j++) {
if (arr[index] < arr[j]) {
index = j;
}
}
//2. 判断，交换位置
if (index != i) {
int temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
}
return true;
}
/*
剩余元素中的最大值放到下标为2的位置
*/
/**
*找出当前数组中剩余元素的最大值放到下标为2的位置
*@param int[] 要处理的数组
*@return boolean 返回true表示函数运行成功，
* 返回false表示函数运行失败
* 失败原因: 1. 传入的数据为null，2. 数组的元素个数为0
*/
public static boolean putRestOfMaxAtTwoIndex(int[] arr) {
//参数合法性判断
if (null == arr || arr.length == 0) {
System.out.println("Input param is invalid!");
return false;
}
//1, 从下标为2开始
int index = 2;
for (int i = 3; i < arr.length; i++) {
if (arr[index] < arr[i]) {
index = i;
}
}
//2. 判断交换
if (index != 2) {
int temp = arr[index];
arr[index] = arr[2];
arr[2] = temp;
}
return true;
}
/*
剩余元素中的最大值放到下标为1的位置
*/
/**
*找出当前数组中剩余元素的最大值放到下标为1的位置
*@param int[] 要处理的数组
*@return boolean 返回true表示函数运行成功，
* 返回false表示函数运行失败
* 失败原因: 1. 传入的数据为null，2. 数组的元素个数为0
*/
public static boolean putRestOfMaxAtOneIndex(int[] arr) {
//参数合法性判断
if (null == arr || arr.length == 0) {
System.out.println("Input param is invalid!");
return false;
}
//1. 参照物为下标为1的元素
int index = 1;
for (int i = 2; i < arr.length; i++) {
if (arr[index] < arr[i]) {
index = i;
}
}
//2. 判断交换
if (index != 1) {
int temp = arr[index];
arr[index] = arr[1];
arr[1] = temp;
}
return true;
}
/*
找出数组中的最大值，放到下标为0的位置
*/
/**
*找出int数组arr中的最大值，放到下标为0的位置
*@param int[] 要处理的数组
*@return boolean 返回true表示函数运行成功，
* 返回false表示函数运行失败
* 失败原因: 1. 传入的数据为null，2. 数组的元素个数为0
*/
public static boolean putMaxAtZeroIndex(int[] arr) {
//参数合法性判断
if (null == arr || arr.length == 0) {
System.out.println("Input Param is Invalid!");
return false; //函数运行失败!
}
//1. 找出最大值所在下标
int index = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[index] < arr[i]) {
index = i;
}
}
//2. 判断，交换位置
if (index != 0) {
int temp = arr[index];
arr[index] = arr[0];
arr[0] = temp;
}
return true;
}
public static boolean getNumberFromKeyboard(int[] arr) {
if (null == arr || arr.length ==0) {
return false;
}
Scanner sc = new Scanner(System.in);
for (int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
return true;
}
public static boolean printIntArray(int[] arr) {
if (null == arr || arr.length == 0) {
return false;
}
for (int i = 0; i < arr.length; i++) {
System.out.println("arr[" + i + "] = " + arr[i]);
}
return true;
}
}
class Demo3 {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 1, 3, 5, 7, 1};
int[] indexes = new int[arr.length];
//count是找到的最大值个数
int count = findAllMaxIndexesInArray(arr, indexes);
for (int i = 0; i < count; i++) {
System.out.println("Max is " + arr[indexes[i]] + " at "
+ indexes[i]);
}
}
/*
找出数组中的所有的最大值下标
分析:
函数的返回值只能返回一个，不能是多个。不能用返回值返回
多个最大值的下标。PASS
用另一个数组保存最大值的下标
返回值，返回找到的最大值的个数。
*/
/**
*从数组arr中找出所有的最大值下标，放入到indexes中数组中，返回找到
*最大值个数。
*@param arr int类型数组，查询最大值的数组
*@param indexes 用于保存最大值所在下标
*@return int 返回找到的最大值个数，如果返回-1，表示运行失败
*/
public static int findAllMaxIndexesInArray(int[] arr, int[] indexes) {
//参数合法性判断
if (null == arr || null == indexes || arr.length == 0
|| indexes.length == 0) {
System.out.println("Input param is invalid!");
return -1; //表示函数运行失败
}
//1. 确定最大值是谁?
int max = 0;
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
//2. 利用循环找出所有最大值的下标，保存到indexes数组中
int count = 0; //计数，最大值个数
//2. 1在arr数组中循环，找到和max一样的元素，得到下标
for (int i = 0; i < arr.length; i++) {
if (max == arr[i]) { //i就是最大值的下标
//2. 2 把当前的i值放入到indexes数组中
indexes[count] = i;
count++; //count 第一是统计个数，第二是indexes下标位置
}
}
return count;
}
}
/*
添加流程:
1. 确定数据放入的位置
找出数组中第一个比要插入数据大的元素，该元素所在下标就是要放入数据的位置
如果没有任何一个元素大于要插入的数据，那么这个数据放入到数组的末尾
2. 考虑数组的移动问题
移动的方式，是从最后一个元素开始，到目标位置，从后往前挨个向右移动一位
如果该数是放入到数组的末尾，那么不需要移动操作
3. 把要插入的数据，放入到数组中
*/
class Demo4 {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 0};
insertNumberIntoArray(arr, -5);
printIntArray(arr);
}
/**
*arr是一个已经排序完成的数组，从小到大。要将insert数据在不影响数组
*排序的情况下，放入到数组中
*@param arr int类型从小到大排序的数组
*@param insert 要插入的int类型数据
*@return boolean 返回true表示函数运行成功，返回false表示函数运行失败
*/
public static boolean insertNumberIntoArray(int[] arr, int insert) {
//参数合法性判断
if (null == arr || arr.length == 0) {
System.out.println("Input param is invalid!");
return false;
}
//1. 确定数据放入的位置
//1.1 假设在数组中没有比insert 大的数据
int index = arr.length - 1; //数组中最大的下标位置
//1.2 利用循环遍历数组，在数组中找出比insert大的第一个数据
for (int i = 0; i < arr.length; i++) {
if (arr[i] > insert) {
index = i; //插入数据要放入的下标位置
break;
}
}
//2. 考虑数组的移动问题
/*
{1, 3, 5, 7, 9, 11, 13, 15, 17, 0};
放入: 10 index = 5 >>> 4
arr[9] = arr[8]
arr[8] = arr[7]
arr[7] = arr[6]
arr[6] = arr[5]
放入: 2 index = 1 >>> 8
放入: 19 index = 9 >>> 0
移动时是从后往前移动 arr[9] = arr[8] arr[8] = arr[7]
arr[i] = arr[i - 1] or arr[i + 1] = arr[i]
*/
for (int i = arr.length - 1; i > index; i--) {
arr[i] = arr[i - 1];
}
//3. 把要插入的数据，放入到数组中
arr[index] = insert;
return true;
}
public static boolean printIntArray(int[] arr) {
if (null == arr || arr.length == 0) {
return false;
}
for (int i = 0; i < arr.length; i++) {
System.out.println("arr[" + i + "] = " + arr[i]);
}
return true;
}
}
/*
1. 要找到删除数所在下标
存在该数，不存在该数
2. 删除操作
3. 最后的数据换成0 占位，表示无效数据
*/
class Demo5 {
public static void main(String[] args) {
int[] arr = {1, 3, 5 ,7, 9, 11, 13, 15, 17, 19};
deleteNumberInArray(arr, 12);
printIntArray(arr);
}
/**
*删除在已排序数组arr中的delete数据，有可能无法删除
*@param arr int类型已经排序的数组，从小到大排序
*@param delete 要进行删除操作的数
*@return boolean 返回true 表示运行成功，返回false表示运行失败
*/
public static boolean deleteNumberInArray(int[] arr, int delete) {
//参数合法性判断
if (null == arr || arr.length == 0) {
System.out.println("Input param is invalid!");
return false;
}
//1. 要找到删除数所在下标 存在该数，不存在该数
//1.1 假设该数不存在
int index = -1;
//1.2 利用循环，遍历整个数组，找到delete在数组中下标，有可能找不到
for (int i = 0; i < arr.length; i++) {
if (delete == arr[i]) {
index = i;
break;
}
}
//2. 删除操作
if (index != -1) {
//删除操作部分
/*
{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}
删除 1: index = 0 <<< 9
删除 11: index = 5 <<< 4
arr[5] = arr[6]
arr[6] = arr[7]
arr[7] = arr[8]
arr[8] = arr[9]
删除 19: index = 9 <<< 0
arr[i] = arr[i + 1]
*/
for (int i = index; i < arr.length - 1; i++) {
arr[i] = arr[i + 1];
}
//3. 最后的数据换成0 占位，表示无效数据
arr[arr.length - 1] = 0;
} else {
//没有这个数据，无法删除
System.out.println("查无此数据，无法删除!");
}
return true;
}
public static boolean printIntArray(int[] arr) {
if (null == arr || arr.length == 0) {
return false;
}
for (int i = 0; i < arr.length; i++) {
System.out.println("arr[" + i + "] = " + arr[i]);
}
return true;
}
}