Java算法和集合

1. 排序

1.1. 排序概述

1.2. 冒泡排序

1. 整个数列分成两部分：前面是无序数列，后面是有序数列
2. 初始状态，整个数列都是无序的，有序数列为空
3. 如果一个数列有n个元素，至多需要n-1趟循环才能保证数列有序
4. 每一趟循环可以让无序数列中最大数排到最后
5. 每一趟循环都从数列的第一个元素开始比较，依次比较相邻的两个元素，比较到无序数列的末尾为止
6. 如果前一个大于后一个，交换
   

public class TestBubbleSort1 {
    public static void main(String[] args) {
        int [] arr = {75,87,56,45,89,100,76,34,89,97};
        // n个元素排序，最多比较n-1次
        for (int i = 0; i < arr.length - 1; i++) {
            // 假设有序
            boolean flag = true;
            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;
                    // 发生交换了，数组无序
                    flag = false;
                }
            }
            // 有序，直接退出循环
            if(flag) break;
        }
        System.out.println(Arrays.toString(arr)); // [34, 45, 56, 75, 76, 87, 89, 89, 97, 100]
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.3. 选择排序

1. 整个数列分成两部分：前面是有序数列，后面是无序数列
2. 初始状态下，整个数列都是无序的，有序数列为空
3. 一共n个数，需要n-1趟循环
4. 每比较完一趟，有序数量+1，无序数量-1
5. 每趟假设无序数列的第1个元素（整个数列的第i个元素）是最小的，从第i+1个元素开始比较，直到最后一个元素，如果找到更小的数，则假设找到的这个数就是最小数
6. 一趟比较结束后，将发现最小数，和无序数列的第一个数交换
   

public class TestSelectSort {
    public static void main(String[] args) {
        int [] scoreArr = {75,87,56,45,89,100,76,34,89,97};
        // scoreArr.length个元素排序，需要比较scoreArr.length-1趟
        for (int i = 0; i < scoreArr.length - 1; i++) {
            // 第i趟，假设第i个最小
            int minIndex = i;
            // 从第i+1个数开始比较，使用第i和每个数相比较，比到最后
            for (int j = i + 1; j < scoreArr.length; j++) {
                // 找到了更小的数，更新第i个的最小值
                if(scoreArr[minIndex] > scoreArr[j]) {
                    minIndex = j;
                }
            }
            // 一趟比较完成后，如果最小值的索引改变了，则交换
            if(minIndex != i) {
                int temp = scoreArr[i];
                scoreArr[i] = scoreArr[minIndex];
                scoreArr[minIndex] = temp;
            }
        }
        System.out.println(Arrays.toString(scoreArr)); // [34, 45, 56, 75, 76, 87, 89, 89, 97, 100]
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 注意
  • 冒泡排序最多比较n-1趟循环，最少1趟；选择排序必须比较n-1趟循环
  • 冒泡排序中最多的操作就是比较和交换，一趟循环中可能发生多次交换；选择排序中最多的操作是比较，一趟比较结束后发现更小的值才交换
  • 如果数组元素不是基本数据类型，而是对象，进行比较时，让相应的类实现Comparable接口并调用compareTo()方法进行比较
  • 快速排序是冒泡排序的完整版，都是基于交换排序的，是基于比较的排序算法中效率最高的，用到了分治和递归的思想

2. 递归和折半查找

2.1. 递归

2.1.1. 阶乘

public class TestRecursion1 {
    public static void main(String[] args) {
        int n = 6;
        int result = fac(n);
        System.out.println(result); // 720
    }
    public static int fac(int n) {
        int result;
        if(n == 1) result = 1;
        else result = n * fac(n - 1);
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.1.2. 斐波那契数列

F(1) = 1, F(2) = 1, F(n) = F(n - 1) + F(n - 2)

public class TestRecursion2 {
    public static void main(String[] args) {
        int n = 40;
        int result = fibo(n);
        System.out.println(result); // 102334155
    }
    public static int fibo(int n) {
        int result = 0;
        if(n == 1 || n == 2) result = 1;
        else result = fibo(n - 1) + fibo(n - 2);
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 递归的缺点
  • 占用大量系统堆栈，耗内存
  • 调用层次过多速度比循环慢得多

2.2. 折半查找

折半查找又称二分查找，使用折半查找的查找表必须使用顺序存储结构且按关键字大小有序排列

• key = 21的查找过程
  
• key = 85的查找过程
  

2.2.1. 非递归方式

public class BinarySearch {
    public static void main(String[] args) {
        int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        System.out.println(searchLoop(array, 8)); // 7
    }
    public static int searchLoop(int[] array, int findValue) {
        if(array == null) return -1;
        int start = 0;
        int end = array.length - 1;
        while(start <= end) {
            // 中间位置
            int middle = (start + end) / 2;
            // 中间值
            int middleValue = array[middle];
            if(findValue == middleValue) return middle;
            // 小于中间值，在中间位置前面找
            else if(findValue < middleValue) end = middle - 1;
            // 大于中间值，在中间位置后面找
            else start = middle + 1;
        }
        // 没有找到，返回-1
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.2.2. 递归方式

public class BinarySearch2 {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(binSearch(array, 8)); // 7
    }
    public static int binSearch(int[] array, int key) {
        int start = 0;
        int end = array.length - 1;
        return binSearch(array, start, end, key);
    }
    public static int binSearch(int[] array, int start, int end, int key) {
        int mid = (start + end) / 2;
        if(start > end) return -1;
        if(array[mid] == key) return mid;
        else if(key > array[mid]) return binSearch(array, mid + 1, end, key);
        else return binSearch(array, start, mid - 1, key);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3. 集合引入和ArrayList

3.1. 引入集合

3.1.1. 集合和数组比较

• 相同点：都可以存储多个对象，对外作为一个整体存在
• 数组的缺点
  • 长度必须在初始化时确定，且固定不可变
  • 采用连续的存储空间，删除和添加效率低
  • 无法直接保存映射关系
  • 缺乏封装，操作繁琐

3.1.2. 集合框架

java集合框架提供了一套性能优良、使用方便的接口和类，位于java.util包中。存放在集合中的数据，被称为元素

• 集合架构
  • Collection接口存储一组不唯一、无序的对象
  • List接口存储一组不唯一、有序(索引顺序)的对象
  • Set接口存储一组唯一、无序的对象
  • Map接口存储一组键值对象，提供key到value的映射
    • key唯一、无序
    • value不唯一、无序

3.1.3. List的主要实现类

• List
  • 特点：有序，不唯一（可重复）
• ArrayList
  • 在内存中分配连续的空间，实现了长度可变的数组
  • 优点：遍历元素和随机访问元素，效率比较高
  • 缺点：添加和删除需大量移动元素，效率低，按内容查找效率高
    
• LinkList
  • 采用双向链表存储方式
  • 缺点：遍历和随机访问元素效率低
  • 优点：插入、删除元素效率较高（前提是必须先查询，但是查询效率低，如果插入删除发生在头尾可以减少查询次数）
    

3.2. ArrayList

3.2.1. 使用ArrayList存储多个学生的分数

import java.util.ArrayList;
import java.util.Iterator;

public class TestArrayList1 {
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add(12);
        list.add(34);
        // 加到指定位置，底层发生了元素大量后移
        list.add(2, 100);
        ArrayList list2 = new ArrayList();
        list2.addAll(0, list);
        // 使用增强for循环输出
        for (Object elem : list) {
            Integer i = (Integer)elem;
            System.out.print(i + "\t"); // 12	34	100
        }
        System.out.println();
        // 使用Interator迭代器输出
        Iterator i = list.iterator();
        // 还有元素，没有就结束循环
        while (i.hasNext()) {
            // 有，就取出
            int elem = (Integer)i.next();
            System.out.print(elem + "\t"); // 12	34	100	
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

3.2.2. 使用泛型保证集合操作的安全和便捷

import java.util.ArrayList;
import java.util.Iterator;

public class TestArrayList2 {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(1, 100);
        ArrayList<Integer> list2 = new ArrayList<Integer>();
        list2.add(3);
        list2.addAll(0, list);
        Iterator<Integer> it = list2.iterator();
        while (it.hasNext()) {
            int elem = it.next();
            System.out.print(elem + "\t"); // 1 100 3
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.2.3. ArrayList类的更多方法

import java.util.ArrayList;

public class TestArrayList3 {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.remove(new Integer(2));
        list.set(0, 65);
        // list.clear()
        System.out.println(list.contains(65)); // true
        System.out.println(list.toString()); // [65]
        list.ensureCapacity(100);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 方法
  • add(E e)：向列表的尾部添加指定的元素，返回boolean（可选操作）
  • add(int index, E element)：向列表的指定位置添加指定的元素，返回boolean（可选操作）
  • addAll(Collection<? extends E> c)： 添加指定collection中的所有元素到此列表的结尾，顺序是指定collection的迭代器返回这些元素的顺序，返回boolean（可选操作）
  • clear()：从列表中移除所有元素（可选操作）
  • contains(Object o)：如果列表包含指定元素，返回true
  • containsAll(Collection<?> c)：如果列表包含指定collection的所有元素，返回true
  • get(int index)：返回列表中指定位置的元素
  • isEmpty()：如果列表布包含元素，返回true
  • iterator()：返回按适当顺序在列表的元素上进行迭代的迭代器
  • remove(int index)：移除列表中指定位置的元素（可选操作）
  • removeAll(Collection<?> c)：从列表中移除指定collection中包含的其所有元素（可选操作）
  • retainAll(Collection<?> c)：仅在列表中保留指定collection中包含的元素（可选操作）
  • set(int index, E element)：用指定元素替换列表中指定位置的元素（可选操作）
  • size()：返回列表中的元素数量

4. ArrayList和LinkedList

4.1. 理解ArrayList源码

• ArrayList底层就是一个长度可以动态增长的Object数组

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData;
    private int size;
}
1
2
3
4
5
6
7

• 接口是可以一个方法也不提供的，比如RandomAccess, cloneable, java.io.Serializable

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}
1

• JDK1.7中，使用无参数构造方法创建ArrayList对象时，默认底层数组长度时10。JDK1.8中，使用无参数构造方法创建ArrayList对象时，默认底层数组长度是0；第一次添加元素，容量不足就要进行扩容

	public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
1
2
3
4
5
6
7
8
9

• 容量不足时进行扩容，默认扩容50%，如果扩容50%还不足容纳新增元素，就扩容为能容纳新增元素的最小数量

	private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapactiy = oldCapacity + (oldCapacity >> 1);
        if(newCapactiy - minCapacity < 0) newCapactiy = minCapacity;
        if(newCapactiy - MAX_ARRAY_SIZE > 0) newCapactiy = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapactiy);
    }
1
2
3
4
5
6
7

• ArrayList中提供了一个内部类ltr，实现Iterator接口，实现对集合元素的遍历

	public Iterator<E> iterator() {
        return new ltr();
    }
    private class ltr implements Iterator<E> {
        
    }
1
2
3
4
5
6

4.2. LinkedList的使用

4.2.1. 使用LinkedList存储和出来分数

功能：存储多个学生的分数

• 具体的执行过程
  • ArrayList：大量的后移元素
  • LinkedList：不需要大量的移动元素，修改节点的指向即可
• 使用ArrayList还是LinkedList：根据使用场合而定
  • ArrayList：大量的根据索引查询的操作，大量的遍历操作（按照索引0-n-1逐个查询）
  • LinkedList：较多的添加、删除操作
• 建议：List<Integer> list = new ArrayList<Integer>()
• 不建议：ArrayList<Integer> list = new ArrayList<Integer>()

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class TestLinkedList {
    public static void main(String[] args) {
        // 1. 创建一个ArrayList集合对象
        // ArrayList<Integer> list = new ArrayList<Integer>();
        // LinkedList<Integer> list = new LinkedList<Integer>();
        // List<Integer> list = new ArrayList<Integer>();
        List<Integer> list = new LinkedList<Integer>();
        list.add(1);
        list.add(new Integer(2));
        list.add(0, 3);
        System.out.println(list.size()); // 3
        System.out.println(list); // 3 1 2
        list.remove(1);
        System.out.println(list); // 3 2
        System.out.println(list.isEmpty()); // false
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4.3. 理解LinkedList的底层源码

• 底层结构是一个双向链表

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    // 节点的数量
    transient int size = 0;
    // 指向第一个节点
    transient Node<E> first;
    // 指向最后一个节点
    transient Node<E> last;
    public LinkedList() {
    }
}
1
2
3
4
5
6
7
8
9
10

• 有一个静态内部类Node，表示双向链表的节点

	private static class Node<E> {
        // 存储节点的数据
        E item;
        // 指向后一个节点
        Node<E> next;
        // 指向前一个节点
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

• LinkedList实现了Deque接口，所以除了可以作为线性表来使用外，还可以当作队列还栈来使用
  

4.4. Java中栈和队列的实现类

• public class Stack<E> extends Vector <E> Vetor过时了，被ArrayList替代了，Stack也就过时了
• public interface Queue<E> extends Collection <E>
• public interface Deque<E> extends Queue <E>
• Deque和Queue实现类
  • ArrayDeque：顺序栈，数组
  • LinkedList：链栈、链表

4.4.1. 理解Java中栈和队列的接口和实现类

/*
* push：入栈
* pop：出栈
* peek：获取栈顶元素
* */
public class TestLinkedList2 {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<String>();
        deque.push("wyb");
        deque.push("xz");
        System.out.println(deque.size()); // 2
        System.out.println(deque.peek()); // xz
        while (!deque.isEmpty()) {
            String elem = deque.pop();
            System.out.println(elem); // xz wyb
        }
        System.out.println(deque.size()); // 0
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19