[关闭]
@CLSChen 2019-09-22T11:34:02.000000Z 字数 24793 阅读 1869

Java进阶

Java 编程

第19章 泛型

Java泛型详解：https://www.cnblogs.com/coprince/p/8603492.html

  1. Generic<T>  //泛型类
  2. T           //泛型类型参数

使用泛型可以提前检测出错误

  1. List arrayList = new ArrayList();
  2. arrayList.add("aaaa");
  3. arrayList.add(100);
  5. for(int i = 0; i< arrayList.size();i++){
  6.     String item = (String)arrayList.get(i);
  7.     Log.d("泛型测试","item = " + item);
  8. }
  10. // 运行结果
  11. java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String
  12. 在运行的时候检测出来，不可以将Integer类转换成String，报错。
  1. List arrayList<String>= new ArrayList<>();
  2. arrayList.add("aaaa");
  3. arrayList.add(100);
  4. // 编辑器报错，不可以向其中添加Integer。
  1. ArrayList<Integer> intList = new ArratList<>();
  2. intList.add(100);// 可以直接用100，而不用new Integer(100)

泛型使用[类型消除]

  1. // 未给ArrayList声明对象类型
  3. ArrayList dates = new ArrayList()；
  4. dates.add(new Date());
  5. // 因此要进行强制类型转换
  6. Date date1 = (Date)dates.get(0);
  1. // 声明ArrayList泛型的对象为Date,ArrayList知道自己储存的是Date对象。
  3. ArrayList<Date> dates = new ArrayList<>();
  4. dates.add(new Date());
  5. // 可以直接读取
  6. Date date1 = dates.get(0);
  1. ArrayList<String> list1 = new ArrayList<>;
  2. ArrayList<Integer> list2 = new ArrayList<>;
  1. list1 instanceof ArrayList;
  2. list2 instanceof ArrayList;
  1. list1 instanceof ArrayList<String>; 
  1. // 不能使用[泛型类型参数]创建对象和数组
  2. E test = new E();
  3. E[] testarray = new E[5];
  5. // 可以使用强制类型转换配合object类来做，但是仍然会有警告。
  6. E[] testarray = (E[])new object[5];
  8. ---
  10. // 使用[泛型类]创建对象是可以的
  11. ArrayList<String> test = new ArrayList<String>;
  13. // 但是使用[泛型类]创建数组也是不允许的
  14. ArrayList<String>[] testarray = new ArrayList<String>[];
  15. // 同样也可以使用强制类型转换，但是也会有警告
  16. ArrayList<String>[] testarray = (ArrayList<String>[])new ArrayList<String>[];
  18. ---
  20. // 静态方法和异常类不能是泛型的。

泛型通配符

泛型类的声明和构造方法

  1. // 泛型类定义
  2. class Generic<T>{
  3. // 构造方法
  4.     public Generic();
  5. }
  6. // 创造类实例
  7. new Generic<String>

泛型方法的声明

  1. public static <T> void print(E[] list){};
  1. public class GenericTest {
  2.    //这个类是个泛型类，在上面已经介绍过
  3.    public class Generic<T>{     
  4.         private T key;
  6.         public Generic(T key) {
  7.             this.key = key;
  8.         }
  11.         //我想说的其实是这个，虽然在方法中使用了泛型，但是这并不是一个泛型方法。
  12.         //这只是类中一个普通的成员方法，只不过他的返回值是在声明泛型类已经声明过的泛型。
  13.         //所以在这个方法中才可以继续使用 T 这个泛型。
  14.         public T getKey(){
  15.             return key;
  16.         }
  19.     /** 
  20.      * 这才是一个真正的泛型方法。
  21.      * 首先在public与返回值之间的<T>必不可少，这表明这是一个泛型方法，并且声明了一个泛型T
  22.      * 这个T可以出现在这个泛型方法的任意位置.
  23.      * 泛型的数量也可以为任意多个 
  24.      * 如：public <T,K> K showKeyName(Generic<T> container){
  25.      *    ...
  26.      *    }
  27.      */
  28.     public <T> T showKeyName(Generic<T> container){
  29.         System.out.println("container key :" + container.getKey());
  30.         T test = container.getKey();
  31.         return test;
  32.     }
  35.      /**
  36.      * 这个方法是有问题的，编译器会为我们提示错误信息："UnKnown class 'E' "
  37.      * 虽然我们声明了<T>,也表明了这是一个可以处理泛型的类型的泛型方法。
  38.      * 但是只声明了泛型类型T，并未声明泛型类型E，因此编译器并不知道该如何处理E这个类型。*/
  39.     public <T> T showKeyName(Generic<E> container){
  40.         ...
  41.     }  
  44.     /**
  45.      * 这个方法也是有问题的，编译器会为我们提示错误信息："UnKnown class 'T' "
  46.      * 对于编译器来说T这个类型并未项目中声明过，因此编译也不知道该如何编译这个类。
  47.      * 所以这也不是一个正确的泛型方法声明。*/
  48.     public void showkey(T genericObj){
  50.     }
  52. }

泛型方法不受类的限制

  1. public class GenericFruit {
  2.     class Fruit{
  3.         @Override
  4.         public String toString() {
  5.             return "fruit";
  6.         }
  7.     }
  9.     class Apple extends Fruit{
  10.         @Override
  11.         public String toString() {
  12.             return "apple";
  13.         }
  14.     }
  16.     class Person{
  17.         @Override
  18.         public String toString() {
  19.             return "Person";
  20.         }
  21.     }
  23.     class GenerateTest<T>{
  24.         public void show_1(T t){
  25.             System.out.println(t.toString());
  26.         }
  28.         //在泛型类中声明了一个泛型方法，使用泛型E，这种泛型E可以为任意类型。可以类型与T相同，也可以不同。
  29.         //由于泛型方法在声明的时候会声明泛型<E>，因此即使在泛型类中并未声明泛型，编译器也能够正确识别泛型方法中识别的泛型。
  30.         public <E> void show_3(E t){
  31.             System.out.println(t.toString());
  32.         }
  34.         //在泛型类中声明了一个泛型方法，使用泛型T，注意这个T是一种全新的类型，可以与泛型类中声明的T不是同一种类型。
  35.         public <T> void show_2(T t){
  36.             System.out.println(t.toString());
  37.         }
  38.     }
  40.     public static void main(String[] args) {
  41.         Apple apple = new Apple();
  42.         Person person = new Person();
  44.         GenerateTest<Fruit> generateTest = new GenerateTest<Fruit>();
  45.         //apple是Fruit的子类，所以这里可以
  46.         generateTest.show_1(apple);
  47.         //编译器会报错，因为泛型类型实参指定的是Fruit，而传入的实参类是Person
  48.         //generateTest.show_1(person);
  50.         //使用这两个方法都可以成功
  51.         generateTest.show_2(apple);
  52.         generateTest.show_2(person);
  54.         //使用这两个方法也都可以成功
  55.         generateTest.show_3(apple);
  56.         generateTest.show_3(person);
  57.     }
  58. }

静态方法直接声明为泛型方法

  1. public static <T> void print(T t){}
  2. // 注意static位置在<T>前

受限泛型类型

  1. Public static <T extends Generic> void print(T t){}

示例：对一个对象数组进行排序。

  1. package chapter19;
  3. public class GenericSort {
  4.     public static void main(String[] args) {
  5.         // Create an Integer array
  6.         Integer[] intArray = { new Integer(2), new Integer(4), new Integer(3) };
  8.         // Create a Double array
  9.         Double[] doubleArray = { new Double(3.4), new Double(1.3), new Double(-22.1) };
  11.         // Create a Character array
  12.         Character[] charArray = { new Character('a'), new Character('J'), new Character('r') };
  14.         // Create a String array
  15.         String[] stringArray = { "Tom", "Susan", "Kim" };
  17.         // Sort the arrays
  18.         sort(intArray);
  19.         sort(doubleArray);
  20.         sort(charArray);
  21.         sort(stringArray);
  23.         // Display the sorted arrays
  24.         System.out.print("Sorted Integer objects: ");
  25.         printList(intArray);
  26.         System.out.print("Sorted Double objects: ");
  27.         printList(doubleArray);
  28.         System.out.print("Sorted Character objects: ");
  29.         printList(charArray);
  30.         System.out.print("Sorted String objects: ");
  31.         printList(stringArray);
  32.     }
  35.     /** Sort an array of comparable objects */
  36. ●   public static <E extends Comparable<E>> void sort(E[] list) {
  37.         E currentMin;
  38.         int currentMinIndex;
  40.         for (int i = 0; i < list.length - 1; i++) {
  41.             // Find the minimum in the list[i..list.length-1]
  42.             currentMin = list[i];
  43.             currentMinIndex = i;
  45.             for (int j = i + 1; j < list.length; j++) {
  46.                 if (currentMin.compareTo(list[j]) > 0) {
  47.                     currentMin = list[j];
  48.                     currentMinIndex = j;
  49.                 }
  50.             }
  52.             // Swap list[i] with list[currentMinIndex] if necessary;
  53.             if (currentMinIndex != i) {
  54.                 list[currentMinIndex] = list[i];
  55.                 list[i] = currentMin;
  56.             }
  57.         }
  58.     }
  60.     /** Print an array of objects */
  61.     public static void printList(Object[] list) {
  62.         for (int i = 0; i < list.length; i++)
  63.             System.out.print(list[i] + " ");
  64.         System.out.println();
  65.     }
  66. }

通配泛型

  1. // 非受限通配
  2. <?>
  3. // 受限通配
  4. <? extends SuperClass>
  5. // 下限通配
  6. <? super T>

第20章 线性表List、栈Stack、队列Queue和优先队列Priority Queue

接口->抽象类->具体类

迭代器 Iterator<E>

  1. // 创建一个列表alist 
  2. ArrayList<String> alist = new ArrayList<String>();
  3. alist.add("new york")
  4. alist.add("new york2")
  6. // 为alist生成一个迭代器
  7. Iterator<String> alistRator = alist.iterator();
  9. // 使用迭代器来访问列表
  10. while(alistRator.hasNext()){
  11.     System.out.println("iterator.next().toUpperCase()" + " ");
  12. }
  14. //输出:new york new york2
foreach可以用于Iterator的任何实例。
  1. ArrayList<String> alist = new ArrayList<String>();
  2. alist.add("new york")
  3. alist.add("new york2")
  5. for(String a:alist){
  6.     System.out.println("a.toUpperCase()" + " ");
  7. }

线性表 List接口

List接口中的通用方法

数组线性表类ArrayList和链表类LinkedList

微信截图_20190418153729.jpg-84.4kB

微信截图_20190418154125.jpg-118.2kB

  1. // 非常低效
  2. for (int i = 0; i < list.size(); i++){
  3.     a = get(i);
  4. }
  6. // 高效
  7. for(int i : list){
  8.     a = i;
  9. }

Comparator接口（不是comparable！）

  1. // 如果前面的小于后面的，返回一个负值，相等为0，大于为正值。
  2. public int compare(T element1, T element2)
  1. // 注意，该方法实现了Serializable接口来进行序列化,在实现comparator接口的地方最好都在后面跟上Serializable接口。
  2. public class Geocom 
  3. ●       implements Comparator<GeometricObject>, java.io.Serializable{
  4.     public int compare(GeometricObject o1, GeometricObject o2){
  5.         double area1 = o1.getArea();
  6.         double area2 = o2.getArea();
  8.         if(area1 > area2)
  9.             return 1;
  10.         else if(area1 < area2)
  11.             return 0;
  12.         else
  13.     }
  14. }

线性表和合集的静态方法

微信截图_20190419144926.jpg-248.9kB

  1. // 使用Arrays的静态asList方法来方便的创建列表
  2. List<String> list = Arrays.asList("red","green","blue");
  4. // 使用sort静态方法来排序
  5. Collections.sort(list);
  7. // 使用重载的sort方法来调用reverseOrder比较器来倒序排序
  8. Collections.sort(list, Collections.reverseOrder);
  1. List<String> list1 = Arrays.asList("red","green","blue");
  2. List<String> list2 = Arrays.asList("yellow");
  4. Collections.copy(list1,list2);
  5. // list1 : yellow green blue

向量类Vector和栈类Stack

微信截图_20190421142422.jpg-249.2kB

微信截图_20190421143257.jpg-100.3kB

队列Queue和优先队列

双端队列接口Deque和链表类LinkedList

2.jpg-88.4kB

  1. import java.util.*;
  3. public class PriorityQueueDemo {
  4.     public static void main(String[] args) {
  5. ●       PriorityQueue<String> queue1 = new PriorityQueue<>();
  6.         queue1.offer("Oklahoma");
  7.         queue1.offer("Indiana");
  8.         queue1.offer("Georgia");
  9.         queue1.offer("Texas");
  11.         System.out.println("Priority queue using Comparable:");
  12.         while (queue1.size() > 0) {
  13.             System.out.print(queue1.remove() + " ");
  14.         }
  16. ●       PriorityQueue<String> queue2 = new PriorityQueue<>(4, Collections.reverseOrder());
  17.         queue2.offer("Oklahoma");
  18.         queue2.offer("Indiana");
  19.         queue2.offer("Georgia");
  20.         queue2.offer("Texas");
  22.         System.out.println("\nPriority queue using Comparator:");
  23.         while (queue2.size() > 0) {
  24.             System.out.print(queue2.remove() + " ");
  25.         }
  26.     }
  27. }
  28. //输出结果：
  29. > Priority queue using Comparable:
  30. > Georgia Indiana Oklahoma Texas 
  31. > Priority queue using Comparator:
  32. > Texas Oklahoma Indiana Georgia

第21章 集合(set)和映射表(map)

集合

image.png-752.2kB

HashSet哈希集合 负载系数

  1. Set<String> hashSet = new HashSet<>();
  2. // 等价于
  3. Set<String> hashSet = new HashSet<>(16, 0.75);

LinedSet、TreeSet

image.png-1133.8kB

  1. Ser<GeometricObject> set = new TreeSet<>(new GeoComparator);

映射表（Map）

image.png-694.4kB
TIM图片20190503162623.png-382.4kB

HashMap哈希表、LinkedHashMap、TreeMap

  1. // 默认按插入顺序排序
  2. Map<String,Integer> linkmap = new LinkedHashMap<>();
  3. // 按照访问顺序排序（最后访问的在最后面）
  4. Map<String,Integer> linkmap = new LinkedHashMap<>(16, 0.75, true);
  1. Map<String, Integer> tmap = new TreeMap<>();
  2. Map<String, Integer> tmap = new TreeMap<>(new Comparator);

image.png-615.6kB

单元素与不可变的合集和映射表

image.png-530.7kB

第22章 开发高效算法

时间复杂度

image.png-363.6kB

动态编程思想

  1. public static int fib(int n){
  2.     if(n == 0)
  3.         return 0;
  4.     else if (n <= 2)
  5.         return 1;
  6.     else
  7.         return fib(n - 1) + fib(n - 2);
  8. }
  1. public static int fib(int n){
  2.     int f0 = 0;
  3.     int f1 = 1;
  4.     int f2 = 1;
  6.     if(n == 0)
  7.         return 0;
  8.     else if (n <= 2)
  9.         return 1;
  11.     for(int i = 3; i < n; i++){
  12.         f0 = f1;
  13.         f1 = f2;
  14.         f2 = f0 + f1;
  15.     }
  16. }
  1. public static int fib(int n, int ppre, int pre){
  2.     if(n <= 1)
  3.         return ppre;
  4.     else
  5.         return fib(int n - 1, int pre, int ppre + pre);
  6. }
  7. main{
  8.     fib(5, 1, 1);
  9. }

使用欧几里得算法求解最大公约数。

  1. 用gcd(m, n)表示求m和n的最大公约数。
  2. 如果m % n=0，那么gcd(m, n)为n。
  3. 否则，gcd(m, n)就是gcd(n, m % n)。
  5. // 时间复杂度为O(logn)
  6. public static int gcd(int m, int n){
  7.     if(m % n == 0)
  8.         return n;
  9.     else
  10.         return gcd(n, m % n);
  11. }

for循环的小技巧

  1. // 计算很多次
  2. for(int i = 0; i < (int)math.sqrt(number); i++)
  4. // 整个for循环只计算一次
  5. int sqrtnum = (int)math.sqrt(number);
  6. for(int i = 0; i < sqrtnum; i++)

排序

插入排序 InsertionSort O(n^2)

  1. public static void main(String[] args) {
  2.         int[] a = {1, 3, 5, 7, 24, 73, 72, 2};
  3.         int[] b = new int[8];// b数组的大小要和a一样。
  4.         int cur = 0;
  6.         for (int i = 0; i < a.length; i++) {
  7.             cur = a[i];
  8.             int j;
  9.             // important
  10.             for (j = i; j > 0 && b[j - 1] > cur; j--) { // 4
  11.                 b[j] = b[j - 1];
  12.             }
  13.             b[j] = cur; // 5
  14.         }
  16.         for (int x : b) {
  17.             System.out.print(x + " ");
  18.         }
  19. }
  1. // 注意，这段代码的精妙之处就在于不需要创建子数组。
  3. public static void insertionSort(int[] list){
  4.         for (int i = 0; i < list.length; i++) {
  5.             int cur = list[i];
  6.             int j;
  8.             // 注意，当i == j == 0时，for循环并不会执行，但是j = i仍然会发生，结果就是将第一个插入元素直接插入第一位。而这里并没有新数组，因此就是将list[0]的值赋给list[0]的无意义操作。
  9.             for (j = i; j > 0 && list[j - 1] > cur; j--) {
  10.                 list[j] = list[j - 1];
  11.             }
  12.             list[j] = cur;
  14.         }
  16.         for (int x:list
  17.              ) {
  18.             System.out.print(x + " ");
  19.         }
  20. }
  22. public static void main(String[] args) {
  23.         int[] a = {1, 3, 5, 7, 24, 73, 72, 2};
  24.         insertionSort(a);
  25. }

冒泡排序 BubbleSort O(n^2)

  1. public class BubbleSort {
  2.     public static void main(String[] args) {
  3.         int[] a = {6, 5, 7, 2, 9, 1, 0};
  4.         boolean b = true;
  6.         // 如果上次仍有排序，则继续循环，设置排序序号为false
  7.         for (int j = 0; j < a.length && b; j++) {
  8.             b = false; 
  10.             //注意每次循环次数减一
  11.             for (int i = 1; i < a.length - j; i++) { 
  12.                 if (a[i - 1] > a[i]) {
  13.                     // 交换元素
  14.                     int temp = a[i];
  15.                     a[i] = a[i - 1];
  16.                     a[i - 1] = temp;
  18.                     // 若本次仍存在冒泡，则继续大循环。
  19.                     // 否则默认终止循环。
  20.                     b = true;
  21.                 }
  22.             }
  23.         }
  24.         for (int x : a) {
  25.             System.out.print(x + " ");
  26.         }
  28.     }
  29. }

在最佳情况下，冒泡排序的时间为O(n),即一次全部冒泡成功。
最差情况为每次都要冒泡，为O(n^2)。

归并排序（MergeSort）O(nlogn)

微信截图_20190508193832.jpg-287.1kB

  1. import java.util.Arrays;
  3. public class MergeSort {
  4.     public static void main(String[] args) {
  5.         int[] a = {1, 3, 5, 2, 8};
  6.         mergeSort(a);
  7.         for (int x : a) {
  8.             System.out.print(x + " ");
  9.         }
  10.     }
  12.     public static void mergeSort(int[] list) {
  13.         if (list.length > 1) { // 递归结束条件
  14.             int[] firstHalf = new int[list.length / 2];
  15.             int[] secondHalf = new int[list.length - firstHalf.length];
  16.             // System里的数组复制方法，注意复制后半部分的时候，要从firstHalf.length开始复制（第二个参数），长度是secondHalf.length（最后一个参数）。
  17.             System.arraycopy(list, 0, firstHalf, 0, firstHalf.length);
  18.             System.arraycopy(list, firstHalf.length, secondHalf, 0, secondHalf.length);
  20.             mergeSort(firstHalf);
  21.             mergeSort(secondHalf);
  22.             merge(firstHalf, secondHalf, list);
  23.         }
  24.     }
  26.     public static void merge(int[] list1, int[] list2, int[] temp) {
  27.         int index1 = 0;
  28.         int index2 = 0;
  29.         int index3 = 0;
  31.         // 选取两个数组中较小的数放入最终数组，并在某个数组被读取完后停止。
  32.         while (index1 < list1.length && index2 < list2.length) {
  33.             if (list1[index1] < list2[index2])
  34.                 temp[index3++] = list1[index1++];
  35.             else
  36.                 temp[index3++] = list2[index2++];
  37.         }
  39.         // 将剩下的数直接复制进最终数组。
  40.         while (index1 < list1.length) {
  41.             temp[index3++] = list1[index1++];
  42.         }
  43.         while (index2 < list2.length) {
  44.             temp[index3++] = list2[index2++];
  45.         }
  46.     }
  47. }

快速排序

  1. package demo2;
  3. public class QuickSort {
  4.     public static void quickSort(int[] list) {
  5.         quickSort(list, 0, list.length - 1);
  6.     }
  8.     public static void quickSort(int[] list, int first, int last) {
  9.         // 对于每个快速排序，last必须大于first，如果last=-1，就结束递归。
  10.         if (last > first) {
  11.             // 返回主元的位置，然后通过主元分割前后两端，并依次进行快速排序。
  12.             int indexOfPivot = partition(list, first, last);
  13.             quickSort(list, first, indexOfPivot - 1);
  14.             quickSort(list, indexOfPivot + 1, last);
  15.         }
  16.     }
  18.     // 返回主元的正确位置，并交换处于不正确位置的元素，使得主元的前面都小于主元，后面都大于主元。
  19.     public static int partition(int[] list, int first, int last) {
  20.         int pivot = list[first];
  21.         int start = first++;
  22.         int temp = 0;
  23.         while (first < last) {
  24.             // 当发现前后两个特例之后，将他们交换。
  25.             // 如果只有小数列有特例，那么last会一直往前，越过大数列，停在小数列的最后一个位置。
  26.             // 这种情况大数列本身就是排好序的，因此将小数列中的特例与小数列的最后一位交换。
  27.             while (first < last && list[first] < pivot)
  28.                 first++;
  29.             while (first < last && list[last] > pivot)
  30.                 last--;
  31.             if (first < last) {
  32.                 temp = list[last];
  33.                 list[last] = list[first];
  34.                 list[first] = temp;
  35.             }
  36.         }
  38.         // last的数小于等于pivot时停下。相当于将last放置在小数列的最后一个位置上，即大数列的第一个之前的那个位置。
  39.         while (list[last] > pivot) {
  40.             last--;
  41.         }
  42.         // 然后将last的数和第一个数（pivot）交换。
  43.         list[start] = list[last];
  44.         list[last] = pivot;
  46.         // 返回last现在所在的位置，也就是主元现在的位置。
  47.         return last;
  48.     }
  50.     public static void main(String[] args) {
  51.         int[] a = {5, 2, 9, 3, 8, 4, 0, 1, 6, 7};
  52.         quickSort(a);
  53.         for (int x : a) {
  54.             System.out.print(x + " ");
  55.         }
  56.     }
  57. }

堆排序 (HeapSort) O(nlogn)

  1. package demo2;
  3. public class Heap<E extends Comparable<E>> {
  4.     private java.util.ArrayList<E> list = new java.util.ArrayList<>();
  6.     public Heap() {
  7.     }
  9.     public Heap(E[] objects) {
  10.         for (int i = 0; i < objects.length; i++) {
  11.             add(objects[i]);
  12.         }
  13.     }
  15.     public void add(E newObject) {
  16.         list.add(newObject);
  17.         int cur = list.size() - 1;
  19.         while (cur > 0) {
  20.             int par = (cur - 1) / 2;
  21.             if (list.get(par).compareTo(list.get(cur)) < 0) {
  22.                 E temp = list.get(cur);
  23.                 list.set(cur, list.get(par));
  24.                 list.set(par, temp);
  25.             } else
  26.                 break;
  27.             // change par to cur.
  28.             cur = par;
  29.         }
  30.     }
  32.     public E remove() {
  33.         if (list.size() == 0) return null;
  35.         E removeObject = list.get(0);
  36.         list.set(0, list.get(list.size() - 1));
  37.         list.remove(list.size() - 1);
  38.         int cur = 0;
  40.         while (cur < list.size()) {
  41.             int son1 = cur * 2 + 1;
  42.             int son2 = cur * 2 + 2;
  43.             // 左子节点要严格小于list才不会越界
  44.             if (son1 >= list.size()) break;
  46.             // 找到两个子节点中比较大的
  47.             int max = son1;
  48.             if (son2 < list.size()) {
  49.                 if (list.get(son1).compareTo(list.get(son2)) > 0)
  50.                     max = son1;
  51.                 else
  52.                     max = son2;
  53.             }
  54.             if (list.get(cur).compareTo(list.get(max)) < 0) {
  55.                 E temp = list.get(cur);
  56.                 list.set(cur, list.get(max));
  57.                 list.set(max, temp);
  59.                 cur = max;
  60.             } else
  61.                 break;
  62.         }
  63.         return removeObject;
  64.     }
  66.     public int getSize() {
  67.         return list.size();
  68.     }
  70. }
  1. package demo2;
  3. public class HeapSort {
  4.     public static <E extends Comparable<E>> void heapSort(E[] list) {
  5.         // 通过list新建堆
  6.         Heap<E> a = new Heap<>(list);
  7.         // 注意，remove出来的是堆中最大的元素，因此要从后面开始遍历。
  8.         for (int i = list.length - 1; i >= 0; i--) {
  9.             list[i] = a.remove();
  10.         }
  11.     }
  13.     public static void main(String[] args) {
  14.         Integer[] a = {5, 2, 9, 3, 8, 4, 0, 1, 6, 7};
  15.         heapSort(a);
  16.         for (Integer x : a
  17.         ) {
  18.             System.out.print(x + " ");
  19.         }
  20.     }
  21. }

第24章 实现线性表、栈、队列和优先队列

线性表的通用特性

image.png-133.9kB
image.png-1424.4kB

数组线性表

image.png-483.8kB

栈和队列

优先队列

第25章 二叉搜索树

第26章 AVL树 平衡二叉搜索树

第27章 散列

散列码

反射

廖雪峰的官方网站：https://www.liaoxuefeng.com/wiki/1252599548343744/1264799402020448

第30章 多线程和并行程序设计

创建单个线程以及Thread类的一些方法

image.png-633.6kB

  1. TaskClass task = new TaskClass();// TaskClass类实现了Runnable接口
  2. Thread thread = new Thread(task);// 通过TaskClass创建一个线程
  3. thread.start();// 启动它
  1. MyThread mythread = new MyThread();// Myshread类继承了Thread类
  2. mythread.start();// 直接启动子类就好
  1. new Thread(new Runnable(){}).start();
  2. // 填充run（）方法
  3. new Thread(new Runnable(){
  4.     @Override
  5.     public void run(){
  6.         System.out.println("nihao");
  7.     }
  8. }).start();
  10. // 可以使用Lambda表达式进一步简化，将new Runnable（）{} 变成（）-> {}
  11. // 并且不用写run()的方法头！
  12. new Thread(()->{
  13.     System.out.println("nihao");
  14. }).start();

线程池 Executor接口以及Executors方法

image.png-1035.8kB

  1. ExecutorService executor = Executors.newFixedThreadPool(3);
  2. // 如果设置为1，那么三个线程将串行执行。
  3. // 如果是newCachedThreadPool(),所有任务都并发执行。
  5. executor.execute(new PrintChar('a', 100));// +execute(Runnable object):void
  6. executor.execute(new PrintChar('b', 100));
  7. executor.execute(new PrintNum(100));
  9. executor.shutdown();

线程同步 synchronized关键字

  1. synchronized(expr){ // expr必须是一个对象的引用
  2.     //...
  3. }
  5. synchronized(account){
  6.     account.toString();
  7. }
  9. 将synchronized后面的括号中填上this，就可以锁定当前对象或者当前类。

显式加锁 Lock接口

image.png-669.1kB

  1. private static Lock lock = new ReentrantLock();
  3. lock.lock();
  4. try{
  5. }catch{
  6. }finally{
  7.     lock.unlock();
  8. }
  9. 尽量把锁的释放放在finally里，这样可以确保锁被释放。

image.png-327.5kB

  1. private static Lock lock = new ReentrantLock();
  2. private static Condition newDeposit = lock.newCondition();

image.png-346.9kB

image.png-308.8kB

监视器

image.png-360.6kB

信号量

image.png-449kB

image.png-855kB

死锁

image.png-291.1kB

线程状态

image.png-706.7kB

同步合集

image.png-847.1kB

image.png-165.9kB

并行编程

https://www.cnblogs.com/cjsblog/p/9078341.html

image.png-960.8kB

image.png-382.6kB

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注