int []arr = new int[] {}; //标准格式
数组是最基本的数据结构,一张表,线性表(在这张表当中,数据元素之间是一对一的关系,除了第一个和最后一个之外,其余元素都是首尾连接的)
好处 简单便于理解》但时间复杂度较高
package com.jsoft.morning; import java.util.Scanner; public class Ch01 { public static void main(String[] args) { // 找出一个数在数组中的位置 // 在数组中是否存在,如果存在返回下标,如果不存在返回-1 // 如果找到了,则把下标保存起来,显示你要找的数是xxx,在目标数组中的下标是xxx;如果没找到,则显示你要找的数是xxx,在目标数组中不存在 int []arr = new int[] {1,34,56,6,78,9,10}; Scanner sc = new Scanner(System.in); System.out.println("请输入第一个数 : "); int num=sc.nextInt(); int index = -1; for (int i = 0; i < arr.length; i++) { if (arr[i] == num) { index = i; break; } } if (index != -1) { System.out.println("你要找的数是:" + num + "," + "在目标数组中的下标是:" + index); }else{ System.out.println("你要找的数是:" + num + "," + "在目标数组中不存在"); } } }
二分法的思路非常重要
如果要使用二分法查找数字,前提是这个数组必须有顺序
package com.jsoft.morning; import java.util.Scanner; public class Ch02 { public static void main(String[] args) { int [] arr = new int[]{1,2,3,4,5,6,7}; Scanner sc = new Scanner(System.in); System.out.println("请输入要查找的数字:"); int target = sc.nextInt(); // 最左边的下标 int left = 0; // 最右边的下标 int right = arr.length - 1; if (target < arr[left] || target > arr[right]){ System.out.println(target + "在目标数组中不存在"); } else { // 用来保存找到的下标的值 int res = -1; while (left <= right){ // 找出中间位置 int middle = (left + right) / 2; if (arr[middle] == target) { // 中间的数恰巧就是我们要找的数 res = middle; // left = arr.length; break; } else if (arr[middle] > target) { // 说明我们要找的数在数组的前半区 // 如果在前半区》维护left和right,left不需要动的 right应该移位到中间位置 right = middle - 1; } else{ // 条件实际上就是arr[middle] < target..说明在后半区》right是不需要动的,left应该向右移位到中间位置 left = middle + 1; } } System.out.println(target + "在目标数组中,它的下标是:" + res); } } }
从小到大->冒泡排序思路分析
先拿第一个数和后面的数一一比较大小,冒泡排序需要两层循环 for外层循环走一次,内存循环走一圈
外层for循环控制的是需要各个数之间比较几轮,内层for循环控制的是每个数的真正比较
第一轮比较后,最大的数归位
第二轮比较后,第二大的数归位
......
n个数字经过n-1轮排序后,顺序自然排出
//普通写法 package com.jsoft.morning; public class Ch03 { public static void main(String[] args) { int []arr = new int[] {1,34,56,6,78,9,-10}; // 1 34 6 56 9 -10 78 // 1 6 34 9 -10 56 78 // 1 6 -9 -10 34 56 78 // 1 6 -10 9 34 56 78 // 1 -10 6 9 34 56 78 // -10 1 6 9 34 56 78 for (int i = 0; i < arr.length - 1; i++) { // 已经控制好了比较的次数,比较的次数=数组的长度 - 1 for (int j = 0; j < arr.length - 1 - i; j++) { if(arr[j] > arr[j+1]){ // 如果前面的比后面的大,换位 int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } System.out.print("第" + (i+1) + "轮的比较结果是"); for (int i1 : arr) { System.out.print(i1 + "、"); } System.out.println(); } } }
//冒泡排序的简便操作 package com.jsoft.morning; import java.lang.reflect.Array; import java.util.Arrays; import java.util.FormatFlagsConversionMismatchException; public class Ch04 { public static void main(String[] args) { int []arr = new int[] {1,34,56,6,78,9,-10}; Arrays.sort(arr); for (int i : arr) { System.out.println(i); } } }
思路分析
1.从第一个元素开始,假设该元素已经被排过序了
2.取出下一个元素,在已经排序好的元素的序列中向前扫描
3.如果该元素(已排序)大于后面的元素,将该元素移到下一个位置
4.将新元素插入到原来元素的位置
......以此类推
package com.jsoft.afternoon; public class Ch02 { public static void main(String[] args) { /* 第一轮: i=0,current=arr[1],int preIndex=0, while(0 >= 0 && 25 < arr[0]){}不成立,while循环不启动 arr[0+1] = arr[0+1] 第二轮: i=1,current=arr[2]=48,int preIndex=1 while(1 >= 0&&48<25){}不成立,while循环不启动 arr[1+1] = arr[1+1] 第三轮: i=2,current=arr[3]=12,int preIndex=2 while(2 >=0 && 12 < 48){ arr[3] = arr[2] 2--; } preIndex=1; while(1 >=0 && 12 < 25){ arr[2] = arr[1]; 1--; } preIndex = 0; while(0 >=0 && 12 < 1){}不成立,while完事 arr[1] = 12; 1,12,25,48,10,-8,127,56 第四轮: i=3,current = arr[4] = 10,int preIndex = 3, while(3>=0 && 10 < 48){ arr[4] = arr[3]; 1,12,25,48,48,-8,127,56 3--; } preIndex = 2; while(2>=0 && 10 < 25){ arr[3] = arr[2]; 1,12,25,25,48,-8,127,56 2--; } preIndex = 1; while(1>=0&& 10 < 12){ arr[2] = arr[1]; 1,12,12,25,48,-8,127,56 1--; } preIndex = 0; while(0>=0&&10 < 1){}不成立,while完事 arr[1] = current = 10; 1,10,12,25,48,-8,127,56 */ int[]arr = new int[]{1,25,48,12,10,-8,127,56}; // 定义参照物 int current; for (int i = 0; i < arr.length - 1; i++) { current = arr[i+1]; // 定义上一个元素的下标 int preIndex = i; // 当上一个数的下标有效不能小于0 // 并且还要保证当前的数比它上一个数小 // 这时候,才能让当前位置的数向前移位 while (preIndex >= 0 && current < arr[preIndex]){ // 移位 // 前面的数后移一位 arr[preIndex + 1] = arr[preIndex]; // preIndex --; } arr[preIndex + 1] = current; } for (int i : arr) { System.out.println(i + "、"); } } }
选最小的往前放,这个比较大的往后换
package com.jsoft.afternoon; public class Ch01 { public static void main(String[] args) { /* 第一轮 i=0,minIndex=0,里层的for循环int j = 1;j < 7; if(arr[0] > arr[1]){}。由于if不满足,则继续下一次的比较。 j = 2,if(arr[0] > arr[2]){}。由于if不满足,则继续下一次的比较。 j = 3,if(arr[0] > arr[3]){}。由于if不满足,则继续下一次的比较。 j = 4,if(arr[0] > arr[4]){}。由于if不满足,则继续下一次的比较。 j = 5,if(arr[0] > arr[5]){}。由于if满足条件,执行了minIndex = 5. j = 6,if(arr[5] > arr[6]){}。由于if不满足,则继续下一次的比较。 j = 7,if(arr[5] > arr[7]){}。由于if不满足,则继续下一次的比较。 到此为止,里层的for循环执行完毕。minIndex = 5。执行的 int temp = arr[5]; arr[5] = arr[0]; arr[0] = temp; i=0的这次外层循环执行完毕。 数组变成了-8、25、48、12、10、1、127、56 第二轮 i=1,minIndex = 1, j = 2,if(arr[1] > arr[2]){}。由于if不满足,则继续下一次的比较。 j = 3,if(arr[0] > arr[3]){}。由于if满足,minIndex = 3; j = 4,if(arr[3] > arr[4]){}。由于if满足,minIndex = 4; j = 5,if(arr[4] > arr[5]){}。由于if满足,minIndex = 5; j = 6,if(arr[5] > arr[6]){}。由于if不满足,则继续下一次的比较。 j = 7,if(arr[5] > arr[7]){}。由于if不满足,则继续下一次的比较。 到此为止,里层的for循环执行完毕。minIndex = 5。执行的 int temp = arr[5]; arr[5] = arr[1]; arr[1] = temp; 数组变成了-8、1、48、12、10、25、127、56 第三轮 i=2; */ int [] arr = new int[]{1,25,48,12,10,-8,127,56}; for (int i = 0; i < arr.length; i++) { // 假设最小数的下标 int minIndex = i; for (int j = i + 1; j < arr.length; j++) { if(arr[minIndex]>arr[j]){ // 找到了最小值 minIndex = j; //保存最小值的下标 } } int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; System.out.print("第" + (i+1) + "次比较结果是:"); for (int i1 : arr) { System.out.print(i1 + "、"); } System.out.println(); } // for (int i : arr) { // System.out.print(i + "、"); // } } }
1.创建一个等长的数组,把当前数组中的每一个元素倒着添加到新数组里,新数组里赋值给老数组
2.利用交换的方式
package com.jsoft.afternoon; import java.time.temporal.Temporal; import java.util.Arrays; //数组的反转 public class Ch03 { public static void main(String[] args) { int[]arr = new int[]{1,25,48,12,10,-8,127,56}; // 思路1:创建一个等长的数组,把当前数组中的每一个元素倒着添加到新数组里,新数组里赋值给老数组 // int [] newArr = new int[arr.length]; // for (int i = arr.length-1; i >= 0; i--) { // newArr[i] = arr[arr.length-1-i]; // } // 思路1.1: // for (int i1 : newArr) { // System.out.print(i1 + " "); // } // 思路1.2: // arr = newArr; // for (int i : arr) { // System.out.println(i); // } //// 思路2:利用交换的方式 // for (int i = 0; i < arr.length / 2; i++) { //// temp存储的是最后一位 // int temp = arr[arr.length-1 - i]; // arr[arr.length-1 - i] = arr[i]; // arr[i] = temp; // } // for (int i : arr) { // System.out.print(i + " "); // } // Arrays操作数组的一个工具类 } }
package com.jsoft.afternoon; import java.util.Arrays; public class Ch04 { public static void main(String[] args) { int []nums = new int[]{3,4,6}; // 定义一个新的临时数组 int[] temp = new int[6]; for (int i = 0; i < nums.length; i++) { temp[i] = nums[i]; } nums = temp; System.out.println(Arrays.toString(nums)); } }
双向链表 上一个和下一个的关系都需要去维护
单向链表 只需要维护下一个的关系
分为深度遍历和广度遍历
-> 先完成需要要求的功能
-> 根据程序运行的结果进行优化处理
-> 研究代码的重构(让代码量更少)
-> 提升效率(算法)
1.算法如:插入排序和选择排序有点接收失败!!线性查找、二分法查找和冒泡排序没能完全消化-->sad