排序查找算法，Map集合，集合的嵌套，Collections工具类
排序查找算法
冒泡排序算法
冒泡排序：将一组数据按照升序规则进行排列冒泡排序原理：相邻的数据两两比较，小的放前面，大的放后面。
注意 :
1 如果有n个数据进行排序，总共需要比较n-1轮次2 每一次比较完毕，下一次的比较就会少一个数据参与
public class BubbleSort {public static void main(String[] args) {//数组int[] arr = {3, 5, 2, 1, 4};// 比较：n-1轮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]){int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]);//12345}//使用Arrays工具类进行排序
// Arrays.sort(arr);
//for(int num:arr){
// System.out.print(num+" ");//1 2 3 4 5
//}}
}
选择排序算法
依次选取未排序的元素中最小的元素排序public static void main(String[] args) {//数组 （二分查找要求数组必须是有序的）int[] arr = {4,8,66,52,34};//排序n-1轮for (int i = 0; i < arr.length-1; i++) {for (int j = i+1; j < arr.length; j++) {if(arr[i]>arr[j]){int temp =arr[i];arr[i] = arr[j];arr[j] =temp;}}}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+" ");//4 8 34 52 66}//System.out.println(Arrays.toString(arr));//[4, 8, 34, 52, 66]}
}
二分查找算法
步骤：1，定义两个变量，表示要查找的范围。默认min = 0 ， max = 最大索引
2，循环查找，但是min <= max
3，计算出mid的值
4，判断mid位置的元素是否为要查找的元素，如果是直接返回对应索引
5，如果要查找的值在mid的左半边，那么min值不变，max = mid -1.继续下次循环查找
6，如果要查找的值在mid的右半边，那么max值不变，min = mid + 1.继续下次循环查找
7，当 min > max 时，表示要查找的元素在数组中不存在，返回-1.
public class BinarySearch {public static void main(String[] args) {//数组int[] arr = {1,2,3,4,5,6,7,8,9,10};//要查找的元素int key = 13;boolean flag = searchKey(arr,key);System.out.println(flag);//false}public static boolean searchKey(int[] arr , int key){//定义两个变量，分别记录：最小索引，最大索引int min = 0;int max = arr.length-1;int mid ;boolean flag = false;//循环while (min<=max){mid = (max+min)/2;int num = arr[mid];if(num == key){flag = true;break;}else if (num > key){max = mid -1;}else if(num < key){min = mid + 1;}}return flag;}
}Map集合
三大集合：List、Set、Map
1. List （单列集合： 集合在存储元素时，一次只能存储一个元素）-
Map （双列集合：集合在存储元素时，一次存储两个元素[key元素 、 value元素]）
-
Set （单列集合）
使用场景：
凡是要表示一一对应的数据时就可以Map集合。map集合的特点：
-
可以存储两个元素（键值对元素）
-
key元素不能重复， value元素允许重复
-
一个key元素只能对应一个value元素（一 一对应）//通过key可以找到value[（键 + 值） 一起是一个整体 我们称之为“键值对”或者“键值对对象”，在Java中叫做“Entry对象”。]
-
存取元素不保证顺序
-
没有索引
Map集合常用子类
HashMap：底层使用哈希表（键唯一，无序）
注意：要达到去重效果，需要重写hashCode和equals方法
public class Student {private String name;private int age;public Student() {}public Student(String name, int age) {this.name = name;this.age = age;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Student student = (Student) o;return age == student.age && Objects.equals(name, student.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}@Overridepublic String toString() {return "Student{" +"name='" + name + '\'' +", age=" + age +'}';}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}
}
public class MapDemo4 {//使用HashMap存储自定义对象（key)public static void main(String[] args) {//创建map集合HashMap<Student,String> studentMap = new HashMap<>();//添加元素（key元素：自定义对象）studentMap.put(new Student("zs",23),"北京");studentMap.put(new Student("ls",24),"上海");studentMap.put(new Student("zs",23),"北京");//学生对象中重复内容//遍历集合Set<Student> keys = studentMap.keySet();for(Student key : keys){System.out.println(key+"--------"+studentMap.get(key));//通过key找value}/*** Student{name='ls', age=24}--------上海* Student{name='zs', age=23}--------北京* Student{name='zs', age=23}--------北京* 会打印重复内容*/
//要达到去重效果，需要重写hashCode和equals方法}
}LinkedHashMap：底层使用哈希表+链表（去重，有序）
特点 :
1 元素唯一2 元素有序
public class LinkedHashMapDemo1 {public static void main(String[] args) {//创建Map集合LinkedHashMap<String,String> map = new LinkedHashMap<>();//添加元素map.put("周瑜","小乔");map.put("孙策","大乔");map.put("刘备","孙尚香");map.put("诸葛亮","黄月英");map.put("周瑜","小乔2");//遍历Set<Map.Entry<String,String>> entries = map.entrySet();for(Map.Entry<String,String> entry : entries){String key = entry.getKey();String value = entry.getValue();System.out.println(key+"-----------"+value);/*** 周瑜-----------小乔2* 孙策-----------大乔* 刘备-----------孙尚香* 诸葛亮-----------黄月英*/}}
}
TreeMap：底层使用红黑树（去重，通过键排序）
特点：
去重，排序排序方法：
1.自然排序public class TreeMapDemo1 {public static void main(String[] args) {//创建TreeMap集合TreeMap<Integer,String> treeMap = new TreeMap<>();//向集合中添加元素treeMap.put(11,"Java");treeMap.put(7,"masql");treeMap.put(10,"html");treeMap.put(9,"css");System.out.println(treeMap);//升序{7=masql, 9=css, 10=html, 11=Java}}
}
2.自定义比较器排序
public class TreeMapDemo2 {public static void main(String[] args) {//创建TreeMap集合，指定比较器排序方式TreeMap<Integer,String> treeMap = new TreeMap<>(new Comparator<Integer>() {@Overridepublic int compare(Integer n1, Integer n2) {return n2-n1;}});//向集合中添加元素treeMap.put(11,"Java");treeMap.put(7,"masql");treeMap.put(10,"html");treeMap.put(9,"css");System.out.println(treeMap);//降序{11=Java, 10=html, 9=css, 7=masql}}
}public class TreeMapDemo3 {public static void main(String[] args) {//创建TreeMap集合，指定比较器排序方式TreeMap<Student,String> treeMap = new TreeMap<>(new Comparator<Student>() {@Overridepublic int compare(Student stu1, Student stu2) {//先比较年龄int result = stu2.getAge()-stu1.getAge();
// 年龄相同if(result==0){//比较姓名result = stu2.getName().compareTo(stu1.getName());}return result;}});//向集合中添加元素treeMap.put(new Student("ccc",12),"Java");treeMap.put(new Student("bbb",14),"masql");treeMap.put(new Student("aaa",11),"html");treeMap.put(new Student("ddd",12),"css");System.out.println(treeMap);/*** {Student{name='bbb', age=14}=masql,* Student{name='ddd', age=12}=css,* Student{name='ccc', age=12}=Java,* Student{name='aaa', age=11}=html}*/}
}Map集合中常用方法
//创建Map集合名称为map- map.put//把指定的键与指定的值添加到Map集合中。
- map.get//根据指定的键，在Map集合中获取对应的值
- map.remove//把指定的键 所对应的键值对元素 在Map集合中删除，返回被删除元素的值。
- map.keyset//获取Map集合中所有的键，存储到Set集合中
- map.containsKey//判断该集合中是否有此键
- map.entrySet//先获取所有的键值对对象（Map.Entry), Set<Map.Entry<String ,String>> entries = map.entrySet();
public class MapDemo1 {public static void main(String[] args) {//创建Map集合Map<String,String> map = new HashMap<>();//向map集合中添加元素（key，value）map.put("Java","Java从入门到放弃");map.put("Java","Java就业攻略");//当key元素相同时，会使用新的value元素覆盖旧的元素map.put("mysql","数据库之海");map.put("masqleea","之海");//key元素不同 ，添加map.put("masqlea","之海");//value可以重复System.out.println(map);//{masqlea=之海, Java=Java就业攻略, masqleea=之海, masql=数据库之海}//删除集合中元素（根据key元素名称删除map.remove("Java");System.out.println(map);//{masqlea=之海, masqleea=之海, masql=数据库之海}//通过key,获取集合中的value元素String mysql = map.get("mysql");System.out.println(mysql);//数据库之海if(map.containsKey("masqleea")){//判断集合中是否存在masqleea，存在就进行删除map.remove("masqleea");}System.out.println(map);//{masqlea=之海, mysql=数据库之海}}
}Map集合遍历方式：
Map集合不能直接遍历（只能间接性实现遍历操作）1. 键找值 :
获取Map集合中所有的key元素，遍历所有的key元素，通过key元素找到对应的value元素 Set 存储所有key的Set集合对象 = map集合.keySet();
public class MapDemo2 {//遍历：键找值public static void main(String[] args) {//创建Map集合Map<String,String> map = new HashMap<>();//添加元素map.put("周瑜","小乔");map.put("孙策","大乔");map.put("刘备","孙尚香");map.put("诸葛亮","黄月英");//遍历：先获取所有的key元素，遍历所有的key元素，通过key找value//先获取所有的key元素Set<String> keys = map.keySet();//遍历所有的key元素for (String key: keys) {//通过key找valueString value = map.get(key);System.out.println("key="+key+", value="+value);/*** 输出结果：* key=刘备, value=孙尚香* key=孙策, value=大乔* key=诸葛亮, value=黄月英* key=周瑜, value=小乔*/}}
}
2. 键值对 :
获取Map集合中所有的Map.Entry， 遍历所有的Map.Entry，通过Entry中的API方法获取到key、valueSet<Map.Entry> 存储所有键值对对象的Set集合对象 = map集合.entrySet();Map.Entry：Object getKey()Object getValue()
在Map集合中当key存储的是自定义对象时，要保证对象存储数据的唯一性，
需要：自定义对象中重写hashCode、equals方法
public class MapDemo3 {//遍历：键找值public static void main(String[] args) {//创建Map集合Map<String,String> map = new HashMap<>();//添加元素map.put("周瑜","小乔");map.put("孙策","大乔");map.put("刘备","孙尚香");map.put("诸葛亮","黄月英");//遍历：先获取所有的键值对对象（Map.Entry），遍历所有的键值对对象，通过键值对对象分别获取key， value//1.先获取所有的键值对对象（Map.Entry)Set<Map.Entry<String ,String>> entries = map.entrySet();// 2.遍历所有的键值对对象for(Map.Entry<String ,String> entry: entries){// 3.通过键值对对象分别获取key， valueString key = entry.getKey();String value = entry.getValue();System.out.println("key="+key+", value="+value);/*** 输出结果：* key=刘备, value=孙尚香* key=孙策, value=大乔* key=诸葛亮, value=黄月英* key=周瑜, value=小乔*/}}
}
Map数据统计用法
需求：字符串“aababcabcdabcde”请统计字符串中每一个字符出现的次数，并按照以下格式输出
输出结果：
a（5）b（4）c（3）d（2）e（1）
public class MapText1 {//统计字符串中每个字符出现的次数public static void main(String[] args) {String str = "aababcabcdabcde";//使用Map集合，记录每个字符出现的次数Map<Character, Integer> map = new HashMap<>();//遍历字符串for(int i = 0 ; i<str.length(); i++) {//取出每一个字符Character ch = str.charAt(i);//判断：字符在map集合中是否存在if(map.containsKey(ch)){Integer value = map.get(ch);value++;map.put(ch,value);}else{map.put(ch,1);}// 存在：通过key取出value的值，对value值进行+1运算，把+1运算后的结果，再次存储到相同key的value下//不存在：直接把字符存储到map集合中，value值初始化为1}System.out.println(map);//{a=5, b=4, c=3, d=2, e=1}//获取map集合中键值对对象Set<Map.Entry<Character,Integer>> entries =map.entrySet();for (Map.Entry<Character, Integer> entry : entries) {Character key = entry.getKey();Integer value = entry.getValue();System.out.print(key+"("+value+") ");//a(5) b(4) c(3) d(2) e(1)}System.out.println();}
}
集合的嵌套
List嵌套List
/*使用场景举例：一年级有多个班级，每个班级有多名学生。要求保存每个班级的学生姓名，保存一个年级所有的班级信息思路：可以使用List集合保存一个班级的学生可以使用List集合保存所有班级因此我们可以定义集合如下：班级：List<String>举例 :List<String> 一班 = {迪丽热巴 , 古力娜扎 ,马尔扎哈 ,欧阳娜娜}List<String> 二班 = {李小璐 , 白百何 , 马蓉}List<String> 三班 = {林丹 ,文章, 陈赫}年级：List<List<String>>举例 :List<List<String>> 年级 = {一班 , 二班 , 三班}
*/
public class ListNestingListDemo {public static void main(String[] args) {//班级1List<String> classes1 = new ArrayList<>();classes1.add("迪丽热巴");classes1.add("古力娜扎");classes1.add("马尔扎哈");classes1.add("欧阳娜娜");
//班级2List<String> classes2 = new ArrayList<>();classes2.add("李小璐");classes2.add("白百何");classes2.add("马蓉");
//班级3List<String> classes3 = new ArrayList<>();classes3.add("林丹");classes3.add("文章");classes3.add("陈赫");
//年纪：存储多个班级List<List<String>> grade = new ArrayList<>();grade.add(classes1);grade.add(classes2);grade.add(classes3);
//遍历嵌套集合for (List<String> classes : grade) {//遍历班级for(int i = 0; i < classes.size(); i++){String name = classes.get(i);System.out.println(name);}}}
}
/**List嵌套Map
/*List嵌套Map :使用场景举例：一年级有多个班级，每个班级有多名学生。要求保存每个班级的学生姓名，姓名有与之对应的学号，保存一年级所有的班级信息。思路：1 可以使用Map集合保存一个班级的学生（键是学号，值是名字）2 可以使用List集合保存所有班级因此我们可以定义集合如下：班级：Map<String,String> 键是学号，值是姓名举例 :Map<String,String> 一班 = {it001 = 迪丽热巴 , it002 = 古力娜扎 ,it003 = 马尔扎哈 ,it004 = 欧阳娜娜}Map<String,String> 二班 = {it001 = 李小璐 , it002 = 白百何 , it003 = 马蓉}Map<String,String> 三班 = {it001 = 林丹 ,it002 = 文章, it003 = 陈赫}年级：List<Map<String,String>>保存每个班级的信息举例 :List<Map<String,String>> 年级 = {一班 , 二班 , 三班}*/
public class ListNestingMapDemo {public static void main(String[] args) {Map<String, String> clases1 = new HashMap<>();clases1.put("it001", "迪丽热巴");clases1.put("it002", "古力娜扎");clases1.put("it003", "马尔扎哈");clases1.put("it004", "欧阳娜娜");Map<String, String> clases2 = new HashMap<>();clases2.put("it001", "李小璐");clases2.put("it002", "白百何");clases2.put("it003", "马蓉");Map<String, String> clases3 = new HashMap<>();clases3.put("it001", "林丹");clases3.put("it002", "文章");clases3.put("it003", "陈赫");//在List集合中存储Map集合List<Map<String, String>> grade = new ArrayList<>();grade.add(clases1);grade.add(clases2);grade.add(clases3);//遍历嵌套集合for (Map<String, String> classes : grade) {//遍历班级// Set<String> keys = classes.keySet();for (String key : classes.keySet()) {String value = classes.get(key);System.out.println(key+"--"+value);}System.out.println("----------------");}}
}Map嵌套Map
/*Map嵌套Map使用场景举例：一个年级有多个班级，每个班级有多名学生。要求保存每个班级的学生姓名，姓名有与之对应的学号，保存一年级所有的班级信息，班级有与之对应的班级名称。思路：可以使用Map集合保存一个班级的学生（键是学号，值是名字）可以使用Map集合保存所有班级（键是班级名称，值是班级集合信息）因此我们可以定义集合如下：班级： Map<String,String> 键：学号，值：姓名举例 :Map<String,String> 一班 = {it001 = 迪丽热巴 , it002 = 古力娜扎 ,it003 = 马尔扎哈 ,it004 = 欧阳娜娜}Map<String,String> 二班 = {it001 = 李小璐 , it002 = 白百何 , it003 = 马蓉}Map<String,String> 三班 = {it001 = 林丹 ,it002 = 文章, it003 = 陈赫}年级： Map<String , Map<String,String>> 键：班级名称，值：具体班级信息举例:Map<String, Map<String,String>> 年级 = {"一班" = 一班 , "二班" = 二班 , "三班" = 三班 }*/
public class MapNestingMapDemo {public static void main(String[] args) {Map<String, String> classes1 = new HashMap<>();classes1.put("it001", "迪丽热巴");classes1.put("it002", "古力娜扎");classes1.put("it003", "马尔扎哈");classes1.put("it004", "欧阳娜娜");Map<String, String> classes2 = new HashMap<>();classes2.put("it001", "李小璐");classes2.put("it002", "白百何");classes2.put("it003", "马蓉");Map<String, String> classes3 = new HashMap<>();classes3.put("it001", "林丹");classes3.put("it002", "文章");classes3.put("it003", "陈赫");//Map集合中存储Map集合Map<String, Map<String, String>> grade = new HashMap<>();grade.put("一班", classes1);grade.put("二班", classes2);grade.put("三班", classes3);//遍历//遍历年级for(String classesName : grade.keySet()){System.out.println(classesName+"信息： ");//通过key找到valueMap<String, String> classMap = grade.get(classesName);//遍历班级for(Map.Entry<String,String> classes : classMap.entrySet()){String code = classes.getKey();String name = classes.getValue();System.out.println(name+ "="+code);}System.out.println("---------------------------");}}
}可变参数
在java语言提供了一种特殊的参数：可变参数（可以改变的参数）在调用方法时，传递的参数可以是任意个（底层：是使用数组）
语法格式：public 返回值类型 方法名(参数类型... 参数名){//... 就是可变参数的语法表示形式}
public class ChangeableParameterDemo1 {//演示：可变参数的基本使用public static void main(String[] args) {
//调用带有可变参数的方法int sum = getSum(10,20,30);System.out.println(sum);//60}/**** @param args 可变参数（本质是数组），只能写在参数的末尾* @return*/public static int getSum(int... args){int sum = 0;//把可变参数当数组使用for (int i = 0; i < args.length; i++) {sum = sum+args[i];}return sum;}//可以使用可变参数，简化方法定义
// public static int getSum(int num1,int num2,int num3){
// return num1+num2+num3;
// }
public class ChangeableParameterDemo2 {//可变参数的应用：Collections工具类的addAll方法public static void main(String[] args) {//创建List集合对象List<String> list = new ArrayList<>();//使用Collections工具类，向List集合存储数据Collections.addAll(list,"hyuih","hdjksahldy");//向List集合添加数据list.add("Java");list.add("myaql");System.out.println(list);//[hyuih, hdjksahldy, Java, myaql]}
}
Collections工具类
Collections工具类：
不能创建对象提供了静态方法
针对List、Set集合进行相关操作（排序、二分查找、添加元素、…）
添加
Collections.addAll( List或Set集合 ， 元素1,元素2,...... );//把给定的元素添加到指定的集合中排序
Collections.sort( 集合 );//对集合中的元素进行排序（自然排序、比较器）public class SortDemo {// 练习：定义List集合，存储若干整数，进行排序public static void main(String[] args) {
//创建集合对象List<Integer> list = new ArrayList<>();//向集合中添加元素Collections.addAll(list,4, 3, 5, 1, 2, 6);Collections.sort(list);//排序，元素自己具备自然排序System.out.println(list);//[1, 2, 3, 4, 5, 6]//比较器排序：降序Collections.sort(list, new Comparator<Integer>() {@Overridepublic int compare(Integer n1, Integer n2) {return n2-n1;}});System.out.println(list);//[6, 5, 4, 3, 2, 1]}
}
打乱
Collections.shuffle( 集合 );//对集合中的元素随机打乱顺序public class ShufferDemo {//需求 : 定义一个List集合，里面存储若干整数。对集合进行乱序public static void main(String[] args) {//创建集合对象List<Integer> list = new ArrayList<>();//向集合中添加元素Collections.addAll(list,1,2,3,4,5,6);//打乱集合中元素的顺序Collections.shuffle(list);System.out.println(list);//[1, 6, 4, 5, 2, 3]}
}注意：
(List<?> list)1.只能打乱List集合
2.集合中的元素可以任意类型