《小灰的算法之旅》记录

算法概述 - 空间复杂度

常见的空间复杂度有下面几种情形。

1.常量空间

当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作 O(1)。例如下面这段程序：

void fun1(int n){
    int var = 3;
    …
}

2.线性空间

当算法分配的空间是一个线性的集合（如数组），并且集合大小和输入规模 n 成正比时，空间复杂度记作 O(n)。

例如下面这段程序：

void fun2(int n){
    int[] array = new int[n];
    …
}

3.二维空间

当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模 n 成正比时，空间复杂度记作 O(n^2)。

例如下面这段程序：

void fun3(int n){
    int[][] matrix = new int[n][n];
    …
}

4.递归空间

递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或集合，但是计算机在执行程序时，会专门分配一块内存，用来存储「方法调用栈」。

「方法调用栈」包括进栈和出栈两个行为。

当进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中。

当方法返回时，执行出栈操作，把调用的方法和参数信息从栈中弹出。

下面这段程序是一个标准的递归程序：

void fun4(int n){
    if(n<=1){
        return;
    }
    fun4(n-1);
    …
}

当 n = 1 时，达到递归结束条件，执行 return 指令，方法出栈。

最终，「方法调用栈」的全部元素会一一出栈。

由上面「方法调用栈」的出入栈过程可以看出，执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性，如果递归的深度是 n，那么空间复杂度就是 O(n)。

---

数据结构基础

数组

数组对应的英文是 array，是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构。

数组的另一个特点，是在内存中 顺序存储，因此可以很好地实现逻辑上的 顺序表。

内存是由一个个连续的内存单元组成的，每一个内存单元都有自己的地址。在这些内存单元中，有些被其他数据占用了，有些是空闲的。

数组中的每一个元素，都存储在小小的内存单元中，并且元素之间紧密排列，既不能打乱元素的存储顺序，也不能跳过某个存储单元进行存储。

数组的基本操作

1.读取元素

对于数组来说，读取元素是最简单的操作。由于数组在内存中顺序存储，所以只要给出一个数组下标，就可以读取到对应的数组元素。

假设有一个名称为 array 的数组，我们要读取数组下标为 3 的元素，就写作 array[3]；读取数组下标为 5 的元素，就写作 array[5]。需要注意的是，输入的下标必须在数组的长度范围之内，否则会出现数组越界。

像这种根据下标读取元素的方式叫作随机读取。

简单的代码示例如下：

int[] array = new int[]{3,1,2,5,4,9,7,2};
//输出数组中下标为3的元素
System.out.println(array[3]);

2.更新元素

要把数组中某一个元素的值替换为一个新值，也是非常简单的操作。直接利用数组下标，就可以把新值赋给该元素。

简单的代码示例如下：

int[] array = new int[]{3,1,2,5,4,9,7,2};
//给数组下标为5的元素赋值
array[5] = 10;
//输出数组中下标为5的元素
System.out.println(array[5]);

3.插入元素

插入数组元素的操作存在 3 种情况。

• 尾部插入
• 中间插入
• 超范围插入

1 尾部插入，是最简单的情况，直接把插入的元素放在数组尾部的空闲位置即可，等同于更新元素的操作。

2 中间插入，稍微复杂一些。由于数组的每一个元素都有其固定下标，所以不得不首先把插入位置及后面的元素向后移动，腾出地方，再把要插入的元素放到对应的数组位置上。

中间插入操作的完整实现代码如下：

private int[] array;
private int size;

public MyArray(int capacity){
    this.array = new int[capacity];
    size = 0;
}

/**
 * 数组插入元素
 * * @param index 插入的位置
 * @param element 插入的元素
 */
public void insert(int index, int element) throws Exception {
    //判断访问下标是否超出范围
    if(index<0 || index>size){
        throw new IndexOutOfBoundsException("超出数组实际元素范围！");
    }
    //从右向左循环，将元素逐个向右挪1位
    for(int i=size-1; i>=index; i--){
        array[i+1] = array[i];
    }
    //腾出的位置放入新元素
    array[index] = element;
    size++;
}

/**
* 输出数组
*/
public void output(){
    for(int i=0; i<size; i++){
        System.out.println(array[i]);
    }
}

public static void main(String[] args) throws Exception {
    MyArray myArray = new MyArray(10);
    myArray.insert(0,3);
    myArray.insert(1,7);
    myArray.insert(2,9);
    myArray.insert(3,5);
    myArray.insert(1,6);
    myArray.output();
}

代码中的成员变量 size 是数组实际元素的数量。如果插入元素在数组尾部，传入的下标参数 index 等于 size；如果插入元素在数组中间或头部，则 index 小于 size。

如果传入的下标参数 index 大于 size 或小于 0，则认为是非法输入，会直接抛出异常。

3 超范围输入

假如现在有一个长度为 6 的数组，已经装满了元素，这时还想插入一个新元素。

这就涉及数组的 扩容 了。可是数组的长度在创建时就已经确定了，无法像孙悟空的金箍棒那样随意变长或变短。这该如何是好呢？

此时可以创建一个新数组，长度是旧数组的 2 倍，再把旧数组中的元素统统复制过去，这样就实现了数组的扩容。

private int[] array;
private int size;

public MyArray(int capacity){
    this.array = new int[capacity];
    size = 0;
}

/**
* 数组插入元素
* @param index 插入的位置
* @param element 插入的元素
*/
public void insert(int index, int element) throws Exception {
    //判断访问下标是否超出范围
    if(index<0 || index>size){
        throw new IndexOutOfBoundsException("超出数组实际元素范围！");
    }
    //如果实际元素达到数组容量上限，则对数组进行扩容
    if(size >= array.length){
        resize();
    }
    //从右向左循环，将元素逐个向右挪1位
    for(int i=size-1; i>=index; i--){
        array[i+1] = array[i];
    }
    //腾出的位置放入新元素
    array[index] = element;
    size++;
}
/**
* 数组扩容
*/
public void resize(){
    int[] arrayNew = new int[array.length*2];
    //从旧数组复制到新数组
    System.arraycopy(array, 0, arrayNew, 0, array.length);
    array = arrayNew;
}

/**
* 输出数组
*/
public void output(){
    for(int i=0; i<size; i++){
        System.out.println(array[i]);
    }
}
public static void main(String[] args) throws Exception {
    MyArray myArray = new MyArray(4);
    myArray.insert(0,3);
    myArray.insert(1,7);
    myArray.insert(2,9);
    myArray.insert(3,5);
    myArray.insert(1,6);
    myArray.output();
}

4.删除元素

数组的删除操作和插入操作的过程相反，如果删除的元素位于数组中间，其后的元素都需要向前挪动 1 位。

/**
 * 数组删除元素
 * @param index 删除的位置
 */
public int delete(int index) throws Exception {
    //判断访问下标是否超出范围
    if(index<0 || index>=size){
        throw new IndexOutOfBoundsException("超出数组实际元素范围！");
    }
    int deletedElement = array[index];
    //从左向右循环，将元素逐个向左挪1位
    for(int i=index; i<size-1; i++){
        array[i] = array[i+1];
    }
    size--;
    return deletedElement;
}

这样一来，无须进行大量的元素移动，时间复杂度降低为 O(1)。当然，这种方式只作参考，并不是删除元素时主流的操作方式。

数组的优势和劣势

---

链表

单向链表的结构。

链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。

单向链表的每一个节点又包含两部分，一部分是存放数据的变量 data，另一部分是指向下一个节点的指针 next。

private static class Node {
    int data;
    Node next;
}

链表的第 1 个节点被称为头节点，最后 1 个节点被称为尾节点，尾节点的 next 指针指向空。

与数组按照下标来随机寻找元素不同，对于链表的其中一个节点 A，我们只能根据节点 A 的 next 指针来找到该节点的下一个节点 B，再根据节点 B 的 next 指针找到下一个节点 C……

双向链表比单向链表稍微复杂一些，它的每一个节点除了拥有 data 和 next 指针，还拥有指向前置节点的 prev 指针。

接下来我们看一看链表的存储方式。

如果说数组在内存中的存储方式是顺序存储，那么链表在内存中的存储方式则是 随机存储。

什么叫随机存储呢？

上一节我们讲解了数组的内存分配方式，数组在内存中占用了连续完整的存储空间。而链表则采用了见缝插针的方式，链表的每一个节点分布在内存的不同位置，依靠 next 指针关联起来。这样可以灵活有效地利用零散的碎片空间。

链表的基本操作

1.查找节点

在查找元素时，链表不像数组那样可以通过下标快速进行定位，只能从头节点开始向后一个一个节点逐一查找。

例如给出一个链表，需要查找从头节点开始的第 3 个节点。

2.更新节点

如果不考虑查找节点的过程，链表的更新过程会像数组那样简单，直接把旧数据替换成新数据即可。

3.插入节点

与数组类似，链表插入节点时，同样分为 3 种情况。

• 尾部插入
• 头部插入
• 中间插入

尾部插入，是最简单的情况，把最后一个节点的 next 指针指向新插入的节点即可。

头部插入，可以分成两个步骤。

第 1 步，把新节点的 next 指针指向原先的头节点。

第 2 步，把新节点变为链表的头节点。

中间插入，同样分为两个步骤。

第 1 步，新节点的 next 指针，指向插入位置的节点。

第 2 步，插入位置前置节点的 next 指针，指向新节点。

只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要像数组那样考虑扩容的问题。

4.删除元素

链表的删除操作同样分为 3 种情况。

• 尾部删除
• 头部删除
• 中间删除

尾部删除，是最简单的情况，把倒数第 2 个节点的 next 指针指向空即可。

头部删除，也很简单，把链表的头节点设为原先头节点的 next 指针即可。

中间删除，同样很简单，把要删除节点的前置节点的 next 指针，指向要删除元素的下一个节点即可。

//头节点指针
private Node head;
//尾节点指针
private Node last;
//链表实际长度
private int size;
/**
* 链表插入元素
 * @param data 插入元素
 * @param index 插入位置
 */
public void insert(int data, int index) throws Exception {
    if (index<0 || index>size) {
        throw new IndexOutOfBoundsException("超出链表节点范围！");
    }
    Node insertedNode = new Node(data);
    if(size == 0){
        //空链表
        head = insertedNode;
        last = insertedNode;
    } else if(index == 0){
        //插入头部
        insertedNode.next = head;
        head = insertedNode;
    }else if(size == index){
        //插入尾部
        last.next = insertedNode;
        last = insertedNode;
    }else {
        //插入中间
        Node prevNode = get(index-1);
        insertedNode.next = prevNode.next;
        prevNode.next = insertedNode;
    }
    size++;
}

/**
 * 链表删除元素
 * @param index 删除的位置
 */
public Node remove(int index) throws Exception {
    if (index<0 || index>=size) {
        throw new IndexOutOfBoundsException("超出链表节点范围！");
    }
    Node removedNode = null;
    if(index == 0){
        //删除头节点
        removedNode = head;
        head = head.next;
    }else if(index == size-1){
        //删除尾节点
        Node prevNode = get(index-1);
        removedNode = prevNode.next;
        prevNode.next = null;
        last = prevNode;
    }else {
        //删除中间节点
        Node prevNode = get(index-1);
        Node nextNode = prevNode.next.next;
        removedNode = prevNode.next;
        prevNode.next = nextNode;
    }
    size--;
    return removedNode;
}
/**
* 链表查找元素
* @param index 查找的位置
*/
public Node get(int index) throws Exception {
    if (index<0 || index>=size) {
        throw new IndexOutOfBoundsException("超出链表节点范围！");
    }
    Node temp = head;
    for(int i=0; i<index; i++){
        temp = temp.next;
    }
    return temp;
}

/**
 * 输出链表
 */
public void output(){
    Node temp = head;
    while (temp!=null) {
        System.out.println(temp.data);
        temp = temp.next;
    }
}

/**
 * 链表节点
 */
private static class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
    }
}

public static void main(String[] args) throws Exception {
    MyLinkedList myLinkedList = new MyLinkedList();
    myLinkedList.insert(3,0);
    myLinkedList.insert(7,1);
    myLinkedList.insert(9,2);
    myLinkedList.insert(5,3);
    myLinkedList.insert(6,1);
    myLinkedList.remove(0);
    myLinkedList.output();
}

---

栈和队列

物理结构和逻辑结构

下面我们来讲解两个常用数据结构：栈和队列。这两者都属于逻辑结构，它们的物理实现既可以利用数组，也可以利用链表来完成。

什么是栈

假如有一个又细又长的圆筒，圆筒一端封闭，另一端开口。往圆筒里放入乒乓球，先放入的靠近圆筒底部，后放入的靠近圆筒入口。

那么，要想取出这些乒乓球，则只能按照和放入顺序相反的顺序来取，先取出后放入的，再取出先放入的，而不可能把最里面最先放入的乒乓球优先取出。

栈（stack）是一种线性数据结构，它就像一个上图所示的放入乒乓球的圆筒容器，栈中的元素只能 先入后出（First In Last Out，简称 FILO）。最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作 栈顶（top）。

栈这种数据结构既可以用数组来实现，也可以用链表来实现。

栈的数组实现如下。

栈的链表实现如下。

栈的基本操作

1.入栈

入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。

这里我们以数组实现为例。

2.出栈

什么是队列

队列（queue）是一种线性数据结构，它的特征和行驶车辆的单行隧道很相似。不同于栈的先入后出，队列中的元素只能 先入先出（First In First Out，简称 FIFO）。队列的出口端叫作 队头（front），队列的入口端叫作 队尾（rear）。

用数组实现时，为了入队操作的方便，把队尾位置规定为最后入队元素的 下一个位置。

队列的数组实现如下。

队列的链表实现如下。

队列的基本操作

对于链表实现方式，队列的入队、出队操作和栈是大同小异的。但对于数组实现方式来说，队列的入队和出队操作有了一些有趣的变化。怎么有趣呢？我们后面会看到。

1.入队

入队（enqueue）就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾。

2.出队

出队操作（dequeue）是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头。

循环队列

假设一个队列经过反复的入队和出队操作，还剩下 2 个元素，在「物理」上分布于数组的末尾位置。这时又有一个新元素将要入队。

在数组不做扩容的前提下，如何让新元素入队并确定新的队尾位置呢？我们可以利用已出队元素留下的空间，让队尾指针重新指回数组的首位。

这样一来，整个队列的元素就「循环」起来了。在物理存储上，队尾的位置也可以在队头之前。当再有元素入队时，将其放入数组的首位，队尾指针继续后移即可。

一直到 (队尾下标 + 1) % 数组长度 = 队头下标 时，代表此队列真的已经满了。需要注意的是，队尾指针指向的位置永远空出 1 位，所以队列最大容量比数组长度小 1。

private int[] array;
private int front;
private int rear;

public MyQueue(int capacity){
    this.array = new int[capacity];
}

/**
 * 入队
 * @param element 入队的元素
 */
public void enQueue(int element) throws Exception {
    if((rear+1)%array.length == front){
        throw new Exception("队列已满！");
    }
    array[rear] = element;
    rear =(rear+1)%array.length;
}

/**
* 出队
*/
public int deQueue() throws Exception {
    if(rear == front){
        throw new Exception("队列已空！");
    }
    int deQueueElement = array[front];
    front =(front+1)%array.length;
    return deQueueElement;
}

/**
* 输出队列
*/
public void output(){
    for(int i=front; i!=rear; i=(i+1)%array.length){
        System.out.println(array[i]);
    }
}
public static void main(String[] args) throws Exception {
    MyQueue myQueue = new MyQueue(6);
    myQueue.enQueue(3);
    myQueue.enQueue(5);
    myQueue.enQueue(6);
    myQueue.enQueue(8);
    myQueue.enQueue(1);
    myQueue.deQueue();
    myQueue.deQueue();
    myQueue.deQueue();
    myQueue.enQueue(2);
    myQueue.enQueue(4);
    myQueue.enQueue(9);
    myQueue.output();
}

栈的应用

栈的输出顺序和输入顺序相反，所以栈通常用于对「历史」的回溯，也就是逆流而上追溯「历史」。

例如实现递归的逻辑，就可以用栈来代替，因为栈可以回溯方法的调用链。

队列的应用

队列的输出顺序和输入顺序相同，所以队列通常用于对「历史」的回放，也就是按照「历史」顺序，把「历史」重演一遍。

例如在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的。

再如网络爬虫实现网站抓取时，也是把待抓取的网站URL存入队列中，再按照存入队列的顺序来依次抓取和解析的。

双端队列

双端队列这种数据结构，可以说综合了栈和队列的优点，对双端队列来说，从队头一端可以入队或出队，从队尾一端也可以入队或出队。

优先队列

还有一种队列，它遵循的不是先入先出，而是谁的优先级最高，谁先出队。

优先队列已经不属于线性数据结构的范畴了，它是基于二叉堆来实现的。关于优先队列的原理和使用情况，我们会在下一章进行详细介绍。

---

散列表

散列表也叫作 哈希表（hash table），这种数据结构提供了 键（Key）和 值（Value）的映射关系。只要给出一个 Key，就可以高效查找到它所匹配的 Value，时间复杂度接近于 O(1)。

通过哈希函数，把KEY和数组下标进行转换。

散列表的读写操作

1.写操作

写操作就是在散列表中插入新的键值对（在 JDK 中叫作 Entry）。

如调用 hashMap.put(“002931”, “王五”) ，意思是插入一组 Key 为 002931、Value 为 王五 的键值对。

具体该怎么做呢？

第 1 步，通过哈希函数，把 Key 转化成数组下标 5。

第 2 步，如果数组下标5对应的位置没有元素，就把这个 Entry 填充到数组下标 5 的位置。

但是，由于数组的长度是有限的，当插入的 Entry 越来越多时，不同的 Key 通过哈希函数获得的下标有可能是相同的。例如 002936 这个 Key 对应的数组下标是 2；002947 这个 Key 对应的数组下标也是 2。

这种情况，就叫作 哈希冲突。

开放寻址法

开放寻址法的原理很简单，当一个 Key 通过哈希函数获得对应的数组下标已被占用时，我们可以「另谋高就」，寻找下一个空档位置。

以上面的情况为例，Entry6 通过哈希函数得到下标 2，该下标在数组中已经有了其他元素，那么就向后移动 1 位，看看数组下标 3 的位置是否有空。

很不巧，下标 3 也已经被占用，那么就再向后移动 1 位，看看数组下标 4 的位置是否有空。

幸运的是，数组下标 4 的位置还没有被占用，因此把 Entry6 存入数组下标 4 的位置。

这就是开放寻址法的基本思路。当然，在遇到哈希冲突时，寻址方式有很多种，并不一定只是简单地寻找当前元素的后一个元素，这里只是举一个简单的示例而已。

链表法

这种方法被应用在了 Java 的集合类 HashMap 当中。

HashMap 数组的每一个元素不仅是一个 Entry 对象，还是一个链表的头节点。每一个 Entry 对象通过next指针指向它的下一个 Entry 节点。当新来的 Entry 映射到与之冲突的数组位置时，只需要插入到对应的链表中即可。

2.读操作

讲完了写操作，我们再来讲一讲读操作。读操作就是通过给定的 Key，在散列表中查找对应的 Value。

例如调用 hashMap.get(“002936”)，意思是查找 Key 为 002936 的 Entry 在散列表中所对应的值。

具体该怎么做呢？下面以链表法为例来讲一下。

第 1 步，通过哈希函数，把 Key 转化成数组下标 2。

第 2 步，找到数组下标 2 所对应的元素，如果这个元素的 Key 是 002936，那么就找到了；如果这个 Key 不是 002936 也没关系，由于数组的每个元素都与一个链表对应，我们可以顺着链表慢慢往下找，看看能否找到与 Key 相匹配的节点。

在上图中，首先查到的节点 Entry6 的 Key 是 002947，和待查找的 Key 002936 不符。接着定位到链表下一个节点 Entry1，发现 Entry1 的 Key 002936 正是我们要寻找的，所以返回 Entry1 的 Value 即可。

3.扩容（resize）

在讲解数组时，曾经介绍过数组的扩容。既然散列表是基于数组实现的，那么散列表也要涉及扩容的问题。

首先，什么时候需要进行扩容呢？

当经过多次元素插入，散列表达到一定饱和度时，Key 映射位置发生冲突的概率会逐渐提高。这样一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能都有很大影响。

1. 扩容，创建一个新的 Entry 空数组，长度是原数组的 2 倍。
2. 重新 Hash，遍历原 Entry 数组，把所有的 Entry 重新 Hash 到新数组中。为什么要重新 Hash 呢？因为长度扩大以后，Hash 的规则也随之改变。

经过扩容，原本拥挤的散列表重新变得稀疏，原有的 Entry 也重新得到了尽可能均匀的分配。

---

树

树和二叉树

在数据结构中，树的定义如下。

树（tree）是 n(n≥0) 个节点的有限集。当 n=0 时，称为空树。在任意一个非空树中，有如下特点。

有且仅有一个特定的称为根的节点。

当 n>1 时，其余节点可分为 m(m>0)个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

下面这张图，就是一个标准的树结构。

在上图中，节点 1 是 根节点（root）；节点 5、6、7、8 是树的末端，没有「孩子」，被称为叶子节点（leaf）。图中的虚线部分，是根节点 1 的其中一个子树。

同时，树的结构从根节点到叶子节点，分为不同的层级。从一个节点的角度来看，它的上下级和同级节点关系如下。

在上图中，节点 4 的上一级节点，是节点 4 的父节点（parent）；从节点 4 衍生出来的节点，是节点 4 的孩子节点（child）；和节点 4 同级，由同一个父节点衍生出来的节点，是节点 4 的兄弟节点（sibling）。

树的最大层级数，被称为树的高度或深度。显然，上图这个树的高度是 4。

什么是二叉树

二叉树（binary tree）是树的一种特殊形式。二叉，顾名思义，这种树的每个节点 最多有 2 个孩子节点。注意，这里是最多有 2 个，也可能只有 1 个，或者没有孩子节点。

二叉树的结构如图所示。

二叉树节点的两个孩子节点，一个被称为 左孩子（left child），一个被称为 右孩子（right child）。这两个孩子节点的顺序是固定的，就像人的左手就是左手，右手就是右手，不能够颠倒或混淆。

此外，二叉树还有两种特殊形式，一个叫作 满二叉树，另一个叫作 完全二叉树。

什么是满二叉树呢？

一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。

简单点说，满二叉树的每一个分支都是满的。

什么又是完全二叉树呢？完全二叉树的定义很有意思。

对一个有 n 个节点的二叉树，按层级顺序编号，则所有节点的编号为从 1 到 n。如果这个树所有节点和同样深度的满二叉树的编号为从 1 到 n 的节点位置相同，则这个二叉树为完全二叉树。

这个定义还真绕，看看下图就很容易理解了。

在上图中，二叉树编号从 1 到 12 的 12 个节点，和前面满二叉树编号从 1 到 12 的节点位置完全对应。因此这个树是完全二叉树。

完全二叉树的条件没有满二叉树那么苛刻：满二叉树要求所有分支都是满的；而完全二叉树只需保证最后一个节点之前的节点都齐全即可。

二叉树可以用哪些物理存储结构来表达呢？

1. 链式存储结构。
2. 数组。

链式存储结构

链式存储是二叉树最直观的存储方式。

上一章讲过链表，链表是一对一的存储方式，每一个链表节点拥有 data 变量和一个指向下一节点的 next 指针。

而二叉树稍微复杂一些，一个节点最多可以指向左右两个孩子节点，所以二叉树的每一个节点包含 3 部分。

• 存储数据的 data 变量
• 指向左孩子的 left 指针
• 指向右孩子的 right 指针

再来看看用 数组 是如何存储的。

使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺，则数组的相应位置也空出来。

为什么这样设计呢？因为这样可以更方便地在数组中定位二叉树的孩子节点和父节点。

假设一个父节点的下标是 parent，那么它的左孩子节点下标就是 2×parent + 1；右孩子节点下标就是 2×parent + 2。

反过来，假设一个左孩子节点的下标是 leftChild，那么它的父节点下标就是 (leftChild-1) / 2。

假如节点 4 在数组中的下标是 3，节点 4 是节点 2 的左孩子，节点 2 的下标可以直接通过计算得出。

节点 2 的下标 = (3-1)/2 = 1

显然，对于一个稀疏的二叉树来说，用数组表示法是非常浪费空间的。

什么样的二叉树最适合用数组表示呢？

我们后面即将学到的二叉堆，一种特殊的完全二叉树，就是用数组来存储的。

二叉树的应用

二叉树包含许多特殊的形式，每一种形式都有自己的作用，但是其最主要的应用还在于进行 查找操作和维持相对顺序 这两个方面。

1.查找

二叉树的树形结构使它很适合扮演索引的角色。

这里我们介绍一种特殊的二叉树：二叉查找树（binary search tree）。光看名字就可以知道，这种二叉树的主要作用就是进行查找操作。

二叉查找树在二叉树的基础上增加了以下几个条件。

• 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
• 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
• 左、右子树也都是二叉查找树

下图就是一个标准的二叉查找树。

二叉查找树的这些条件有什么用呢？当然是为了查找方便。

对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是 n，那么搜索节点的时间复杂度就是 O(log n)，和树的深度是一样的。

这种依靠比较大小来逐步查找的方式，和二分查找算法非常相似。

2. 维持相对顺序

这一点仍然要从二叉查找树说起。二叉查找树要求左子树小于父节点，右子树大于父节点，正是这样保证了二叉树的有序性。

因此二叉查找树还有另一个名字——二叉排序树（binary sort tree）。

新插入的节点，同样要遵循二叉排序树的原则。例如插入新元素 5，由于 5 < 6，5 > 3，5 > 4，所以 5 最终会插入到节点 4 的右孩子位置。

这一切看起来很顺利，然而却隐藏着一个致命的问题。什么问题呢？下面请试着在二叉查找树中依次插入 9、8、7、6、5、4，看看会出现什么结果。

怎么解决这个问题呢？这就涉及二叉树的自平衡了。二叉树自平衡的方式有多种，如红黑树、AVL 树、树堆等。由于篇幅有限，本书就不一一详细讲解了，感兴趣的读者可以查一查相关资料。

---

二叉树的遍历

二叉树，是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性的序列，以不同的方式来遍历，遍历出的序列顺序也不同

从节点之间位置关系的角度来看，二叉树的遍历分为 4 种。

1. 前序遍历。
2. 中序遍历。
3. 后序遍历。
4. 层序遍历。

从更宏观的角度来看，二叉树的遍历归结为两大类。

• 深度优先遍历（前序遍历、中序遍历、后序遍历）。
• 广度优先遍历（层序遍历）。

下面就来具体看一看这些不同的遍历方式。

深度优先遍历

深度优先和广度优先这两个概念不止局限于二叉树，它们更是一种抽象的算法思想，决定了访问某些复杂数据结构的顺序。在访问树、图，或其他一些复杂数据结构时，这两个概念常常被使用到。

所谓深度优先，顾名思义，就是偏向于纵深，「一头扎到底」的访问方式。可能这种说法有些抽象，下面就通过二叉树的前序遍历、中序遍历、后序遍历，来看一看深度优先是怎么回事吧。

1.前序遍历

二叉树的前序遍历，输出顺序是根节点、左子树、右子树。

2. 中序遍历

二叉树的中序遍历，输出顺序是左子树、根节点、右子树。

3. 后序遍历

二叉树的后序遍历，输出顺序是左子树、右子树、根节点。

/**
 * 构建二叉树
 * @param inputList 输入序列
 */
public static TreeNode createBinaryTree(LinkedList<Integer>inputList){
    TreeNode node = null;
    if (inputList == null || inputList.isEmpty()) {
        return null;
    }
    Integer data = inputList.removeFirst();
    // 这里的判空很关键：如果元素是空，则不在进一步递归
    if (data != null) {
        node = new TreeNode(data);
        node.leftChild = createBinaryTree(inputList);
        node.rightChild = createBinaryTree(inputList);
    }
    return node;
}

/**
 * 二叉树前序遍历
 * @param node 二叉树节点
 */
public static void preOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.println(node.data);
    preOrderTraveral(node.leftChild);
    preOrderTraveral(node.rightChild);
}

/**
 * 二叉树中序遍历
 * @param node 二叉树节点
 */
public static void inOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    inOrderTraveral(node.leftChild);
    System.out.println(node.data);
    inOrderTraveral(node.rightChild);
}

/**
 * 二叉树后序遍历
 * @param node 二叉树节点
 */
public static void postOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    postOrderTraveral(node.leftChild);
    postOrderTraveral(node.rightChild);
    System.out.println(node.data);
}

/**
    * 二叉树节点
    */
private static class TreeNode {
    int data;
    TreeNode leftChild;
    TreeNode rightChild;

    TreeNode(int data) {
        this.data = data;
    }
}

public static void main(String[] args) {
    LinkedList<Integer> inputList = new LinkedList<Integer>(Arrays.
              asList(new Integer[]{3,2,9,null,null,10,null,
              null,8,null,4}));
    TreeNode treeNode = createBinaryTree(inputList);
    System.out.println("前序遍历：");
    preOrderTraveral(treeNode);
    System.out.println("中序遍历：");
    inOrderTraveral(treeNode);
    System.out.println("后序遍历：");
    postOrderTraveral(treeNode);
}

二叉树用递归方式来实现前序、中序、后序遍历，是最为自然的方式，因此代码也非常简单。

这 3 种遍历方式的区别，仅仅是输出的执行位置不同：前序遍历的输出在前，中序遍历的输出在中间，后序遍历的输出在最后。

代码中值得注意的一点是二叉树的构建。二叉树的构建方法有很多，这里把一个线性的链表转化成非线性的二叉树，链表节点的顺序恰恰是二叉树前序遍历的顺序。链表中的空值，代表二叉树节点的左孩子或右孩子为空的情况。

在代码的 main 函数中，通过 {3,2,9,null,null,10,null,null,8,null,4} 这样一个线性序列，构建成的二叉树如下。

绝大多数可以用递归解决的问题，其实都可以用另一种数据结构来解决，这种数据结构就是栈。因为递归和栈都有回溯的特性。

如何借助栈来实现二叉树的非递归遍历呢？下面以二叉树的前序遍历为例，看一看具体过程。

/**
 * 二叉树非递归前序遍历
 * @param root 二叉树根节点
 */
public static void preOrderTraveralWithStack(TreeNode root){
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode treeNode = root;
    while(treeNode!=null || !stack.isEmpty()){
        //迭代访问节点的左孩子，并入栈
        while (treeNode != null){
            System.out.println(treeNode.data);
            stack.push(treeNode);
            treeNode = treeNode.leftChild;
        }
        //如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
        if(!stack.isEmpty()){
            treeNode = stack.pop();
            treeNode = treeNode.rightChild;
        }
    }
 }

广度优先遍历

如果说深度优先遍历是在一个方向上「一头扎到底」，那么广度优先遍历则恰恰相反：先在各个方向上各走出 1 步，再在各个方向上走出第 2 步、第 3 步……一直到各个方向全部走完。听起来有些抽象，下面让我们通过二叉树的层序遍历，来看一看广度优先是怎么回事。

层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点。

上图就是一个二叉树的层序遍历，每个节点左侧的序号代表该节点的输出顺序。

可是，二叉树同一层次的节点之间是没有直接关联的，如何实现这种层序遍历呢？

这里同样需要借助一个数据结构来辅助工作，这个数据结构就是 队列。

详细遍历步骤如下。

/**
 * 二叉树层序遍历
 * @param root 二叉树根节点
 */
public static void levelOrderTraversal(TreeNode root){
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while(!queue.isEmpty()){
        TreeNode node = queue.poll();
        System.out.println(node.data);
        if(node.leftChild != null){
            queue.offer(node.leftChild);
        }
        if(node.rightChild != null){
            queue.offer(node.rightChild);
        }
    }
 }

---

二叉堆

二叉堆本质上是一种完全二叉树，它分为两个类型。

1. 最大堆。
2. 最小堆。

什么是最大堆呢？最大堆的任何一个父节点的值，都 大于或等于 它左、右孩子节点的值。

什么是最小堆呢？最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值。

二叉堆的根节点叫作 堆顶。

最大堆和最小堆的特点决定了：最大堆的堆顶是整个堆中的 最大元素；最小堆的堆顶是整个堆中的 最小元素。

二叉堆的自我调整

对于二叉堆，有如下几种操作。

1. 插入节点。
2. 删除节点。
3. 构建二叉堆

这几种操作都基于堆的自我调整。所谓堆的自我调整，就是把一个不符合堆性质的完全二叉树，调整成一个堆。下面让我们以最小堆为例，看一看二叉堆是如何进行自我调整的。

1.插入节点

当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置。例如插入一个新节点，值是 0。

这时，新节点的父节点 5 比 0 大，显然不符合最小堆的性质。于是让新节点「上浮」，和父节点交换位置。

继续比较，最终新节点 0「上浮」到了堆顶位置。

2. 删除节点

二叉堆删除节点的过程和插入节点的过程正好相反，所删除的是处于堆顶的节点。例如删除最小堆的堆顶节点 1。

这时，为了继续维持完全二叉树的结构，我们把堆的最后一个节点 10 临时补到原本堆顶的位置。

接下来，让暂处堆顶位置的节点 10 和它的左、右孩子进行比较，如果左、右孩子节点中最小的一个（显然是节点 2）比节点 10 小，那么让节点 10「下沉」。

3. 构建二叉堆

构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质就是让所有非叶子节点依次「下沉」。

下面举一个无序完全二叉树的例子，如下图所示。

首先，从最后一个非叶子节点开始，也就是从节点 10 开始。如果节点 10 大于它左、右孩子节点中最小的一个，则节点 10「下沉」。

接下来轮到节点 3，如果节点 3 大于它左、右孩子节点中最小的一个，则节点 3「下沉」。

然后轮到节点 1，如果节点 1 大于它左、右孩子节点中最小的一个，则节点 1「下沉」。事实上节点 1 小于它的左、右孩子，所以不用改变。

接下来轮到节点 7，如果节点 7 大于它左、右孩子节点中最小的一个，则节点 7「下沉」。节点 7 继续比较，继续「下沉」。

经过上述几轮比较和「下沉」操作，最终每一节点都小于它的左、右孩子节点，一个无序的完全二叉树就被构建成了一个最小堆。

二叉堆的代码实现

在展示代码之前，我们还需要明确一点：二叉堆虽然是一个完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。换句话说，二叉堆的所有节点都存储在数组中。

在数组中，在没有左、右指针的情况下，如何定位一个父节点的左孩子和右孩子呢？

像上图那样，可以依靠数组下标来计算。

假设父节点的下标是 parent，那么它的左孩子下标就是 2 parent + 1；右孩子下标就是 2 parent + 2。

例如上面的例子中，节点 6 包含 9 和 10 两个孩子节点，节点 6 在数组中的下标是 3，节点 9 在数组中的下标是 7，节点 10 在数组中的下标是 8。

/**
 * “上浮”调整
 * @param array 待调整的堆
 */
public static void upAdjust(int[] array) {
    int childIndex = array.length-1;
    int parentIndex = (childIndex-1)/2;
    // temp保存插入的叶子节点值，用于最后的赋值
    int temp = array[childIndex];
    while (childIndex > 0 && temp < array[parentIndex])
    {
    //无须真正交换，单向赋值即可
        array[childIndex] = array[parentIndex];
        childIndex = parentIndex;
        parentIndex = (parentIndex-1) / 2;
    }
    array[childIndex] = temp;
 }

/**
 * “下沉”调整
 * @param array 待调整的堆
 * @param parentIndex 要“下沉”的父节点
 * @param length 堆的有效大小
 */
public static void downAdjust(int[] array, int parentIndex, length) {
    // temp保存父节点值，用于最后的赋值
    int temp = array[parentIndex];
    int childIndex = 2 * parentIndex + 1;
    while (childIndex < length) {
    // 如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
        if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
            childIndex++;
        }
    // 如果父节点小于任何一个孩子的值，则直接跳出
        if (temp <= array[childIndex])
            break;
    //无须真正交换，单向赋值即可
        array[parentIndex] = array[childIndex];
        parentIndex = childIndex;
        childIndex = 2 * childIndex + 1;
    }
        array[parentIndex] = temp;
}

/**
* 构建堆
* @param array 待调整的堆
*/
public static void buildHeap(int[] array) {
    // 从最后一个非叶子节点开始，依次做“下沉”调整
    for (int i = (array.length-2)/2; i>=0; i--) {
        downAdjust(array, i, array.length);
    }
}

public static void main(String[] args) {
    int[] array = new int[] {1,3,2,6,5,7,8,9,10,0};
    upAdjust(array);
    System.out.println(Arrays.toString(array));

    array = new int[] {7,1,3,10,5,2,8,9,6};
    buildHeap(array);
    System.out.println(Arrays.toString(array));
}

代码中有一个优化的点，就是在父节点和孩子节点做连续交换时，并不一定要真的交换，只需要先把交换一方的值存入 temp 变量，做单向覆盖，循环结束后，再把 temp 的值存入交换后的最终位置即可。

---

优先队列

队列的特点是什么？

在之前的章节中已经讲过，队列的特点是 先进先出（FIFO）。

入队列，将新元素置于队尾。出队列，队头元素最先被移出：。

优先队列不再遵循先入先出的原则，而是分为两种情况。

最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队
最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队

例如有一个最大优先队列，其中的最大元素是 8，那么虽然8并不是队头元素，但出队时仍然让元素8首先出队。

最大堆的堆顶是整个堆中的最大元素。

因此，可以用最大堆来实现最大优先队列，这样的话，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。

入队操作 具体步骤如下

插入新节点 5。

新节点 5「上浮」到合适位置。

出队操作 具体步骤如下。

让原堆顶节点 10 出队。

把最后一个节点 1 替换到堆顶位置。

节点 1「下沉」，节点 9 成为新堆顶。

private int[] array;
private int size;
public PriorityQueue(){
    //队列初始长度为32
    array = new int[32];
}
/**
 * 入队
 * @param key 入队元素
 */
public void enQueue(int key) {
    //队列长度超出范围，扩容
    if(size >= array.length){
        resize();
    }
    array[size++] = key;
    upAdjust();
}
/**
 * 出队
 */
public int deQueue() throws Exception {
    if(size <= 0){
        throw new Exception("the queue is empty !");
    }
    //获取堆顶元素
    int head = array[0];
    //让最后一个元素移动到堆顶
    array[0] = array[--size];
    downAdjust();
    return head;
}
/**
 * “上浮”调整
 */
private void upAdjust() {
    int childIndex = size-1;
    int parentIndex = (childIndex-1)/2;
    // temp保存插入的叶子节点值，用于最后的赋值
    int temp = array[childIndex];
    while (childIndex > 0 && temp > array[parentIndex])
    {
        //无须真正交换，单向赋值即可
        array[childIndex] = array[parentIndex];
        childIndex = parentIndex;
        parentIndex = parentIndex / 2;
    }
    array[childIndex] = temp;
}
/**
 * “下沉”调整
 */
private void downAdjust() {
    // temp保存父节点的值，用于最后的赋值
    int parentIndex = 0;
    int temp = array[parentIndex];
    int childIndex = 1;
    while (childIndex < size) {
        // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
        if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
            childIndex++;
        }
        // 如果父节点大于任何一个孩子的值，直接跳出
        if (temp >= array[childIndex])
            break;
        //无须真正交换，单向赋值即可
        array[parentIndex] = array[childIndex];
        parentIndex = childIndex;
        childIndex = 2 * childIndex + 1;
    }
    array[parentIndex] = temp;
}

/**
 * 队列扩容
 */
private void resize() {
    //队列容量翻倍
    int newSize = this.size * 2;
    this.array = Arrays.copyOf(this.array, newSize);
}

public static void main(String[] args) throws Exception {
    PriorityQueue priorityQueue = new PriorityQueue();
    priorityQueue.enQueue(3);
    priorityQueue.enQueue(5);
    priorityQueue.enQueue(10);
    priorityQueue.enQueue(2);
    priorityQueue.enQueue(7);
    System.out.println("出队元素：" + priorityQueue.deQueue());
    System.out.println("出队元素：" + priorityQueue.deQueue());
}

上述代码采用数组来存储二叉堆的元素，因此当元素数量超过数组长度时，需要进行扩容来扩大数组长度。

---

排序算法

引言

根据时间复杂度的不同，主流的排序算法可以分为 3 大类。

1. 时间复杂度为 O(n^2)的排序算法

   • 冒泡排序

   • 选择排序

   • 插入排序

   • 希尔排序（希尔排序比较特殊，它的性能略优于 O(n^2)，但又比不上 O(nlog n)，姑且把它归入本类）

1. 时间复杂度为 O(nlog n) 的排序算法

   • 快速排序

   • 归并排序

   • 堆排序

2. 时间复杂度为线性的排序算法

   • 计数排序

   • 桶排序

   • 基数排序

当然，以上列举的只是最主流的排序算法，在算法界还存在着更多五花八门的排序，它们有些基于传统排序变形而来；有些则是脑洞大开，如鸡尾酒排序、猴子排序、睡眠排序等。

此外，排序算法还可以根据其稳定性，划分为稳定排序和不稳定排序。

即如果值相同的元素在排序后仍然保持着排序前的顺序，则这样的排序算法是稳定排序；如果值相同的元素在排序后打乱了排序前的顺序，则这样的排序算法是不稳定排序。

---

冒泡排序

冒泡排序之所以叫冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。

按照冒泡排序的思想，我们要 把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。详细过程如下。

这样一来，元素 9 作为数列中最大的元素，就像是汽水里的小气泡一样，「漂」到了最右侧。

这时，冒泡排序的第 1 轮就结束了。数列最右侧元素 9 的位置可以认为是一个有序区域，有序区域目前只有 1 个元素。

后续的交换细节，这里就不详细描述了，第 3 轮到第 7 轮的状态如下。

冒泡排序是一种稳定排序，值相等的元素并不会打乱原本的顺序。由于该排序算法的每一轮都要遍历所有元素，总共遍历（元素数量 - 1）轮，所以平均时间复杂度是 O(n^2)。

public static void sort(int array[])
{
    for(int i = 0; i < array.length - 1; i++)
    {
        for(int j = 0; j < array.length - i - 1; j++)
        {
            int tmp = 0;
            if(array[j] > array[j+1])
            {
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
            }
        }
    }
}
public static void main(String[] args){
    int[] array = new int[]{5,8,6,3,9,2,1,7};
    sort(array);
    System.out.println(Arrays.toString(array));
}

很明显可以看出，经过第 6 轮排序后，整个数列已然是有序的了。可是排序算法仍然兢兢业业地继续执行了第 7 轮排序。

在这种情况下，如果能判断出数列已经有序，并做出标记，那么剩下的几轮排序就不必执行了，可以提前结束工作。

public static void sort(int array[])
{
    for(int i = 0; i < array.length - 1; i++)
    {
        //有序标记，每一轮的初始值都是true
        boolean isSorted = true;
        for(int j = 0; j < array.length - i - 1; j++)
        {
            int tmp = 0;
            if(array[j] > array[j+1])
            {
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                //因为有元素进行交换，所以不是有序的，标记变为false
                isSorted = false;
            }
        }
        if(isSorted){
            break;
        }
    }
}
public static void main(String[] args){
    int[] array = new int[]{5,8,6,3,9,2,1,7};
    sort(array);
    System.out.println(Arrays.toString(array));
}

与第 1 版代码相比，第 2 版代码做了小小的改动，利用布尔变量 isSorted 作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，则说明数列已然有序，然后直接跳出大循环。

这个数列的特点是前半部分的元素（3、4、2、1）无序，后半部分的元素（5、6、7、8）按升序排列，并且后半部分元素中的最小值也大于前半部分元素的最大值。

这个问题的关键点在于对数列有序区的界定。

按照现有的逻辑，有序区的长度和排序的轮数是相等的。例如第1轮排序过后的有序区长度是 1，第 2 轮排序过后的有序区长度是 2 ……

实际上，数列真正的有序区可能会大于这个长度，如上述例子中在第 2 轮排序时，后面的 5 个元素实际上都已经属于有序区了。因此后面的多次元素比较是没有意义的。

那么，该如何避免这种情况呢？我们可以在每一轮排序后，记录下来最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了。

public static void sort(int array[])
{
    //记录最后一次交换的位置
    int lastExchangeIndex = 0;
    //无序数列的边界，每次比较只需要比到这里为止
    int sortBorder = array.length - 1;
    for(int i = 0; i < array.length - 1; i++)
    {
        //有序标记，每一轮的初始值都是true
        boolean isSorted = true;
        for(int j = 0; j < sortBorder; j++)
        {
            int tmp = 0;
            if(array[j] > array[j+1])
            {
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                //因为有元素进行交换，所以不是有序的，标记变为false
                isSorted = false;
                //更新为最后一次交换元素的位置
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        if(isSorted){
            break;
        }
    }
}
public static void main(String[] args){
    int[] array = new int[]{3,4,2,1,5,6,7,8};
    sort(array);
    System.out.println(Arrays.toString(array));
}

在第 3 版代码中，sortBorder 就是无序数列的边界。在每一轮排序过程中，处于 sortBorder 之后的元素就不需要再进行比较了，肯定是有序的。

还有一种排序算法叫作鸡尾酒排序，是基于冒泡排序的一种升级排序法。

鸡尾酒排序

冒泡排序的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。算法的每一轮都是 从左到右来比较元素，进行单向的位置交换的。

那么鸡尾酒排序做了怎样的优化呢？

鸡尾酒排序的元素比较和交换过程是 双向 的。

下面举一个例子。

由 8 个数字组成一个无序数列 {2,3,4,5,6,7,8,1}，希望对其进行从小到大的排序。

如果按照冒泡排序的思想，排序过程如下。

第 1 轮（和冒泡排序一样，8 和 1 交换）

第 2 轮

此时开始不一样了，我们反过来 从右往左 比较并进行交换。

第 3 轮（虽然实际上已经有序，但是流程并没有结束）在鸡尾酒排序的第3轮，需要重新从左向右比较并进行交换。

这就是鸡尾酒排序的思路。排序过程就像钟摆一样，第1轮从左到右，第 2 轮从右到左，第 3 轮再从左到右……

public static void sort(int array[])
{
    int tmp = 0;
    for(int i=0; i<array.length/2; i++)
    {
        //有序标记，每一轮的初始值都是true
        boolean isSorted = true;
        //奇数轮，从左向右比较和交换
        for(int j=i; j<array.length-i-1; j++)
        {
            if(array[j] > array[j+1])
            {
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                //有元素交换，所以不是有序的，标记变为false
                isSorted = false;
            }
        }
        if(isSorted){
            break;
        }
        //在偶数轮之前，将isSorted重新标记为true
        isSorted = true;
        //偶数轮，从右向左比较和交换
        for(int j=array.length-i-1; j>i; j--)
        {
            if(array[j] < array[j-1])
            {
                tmp = array[j];
                array[j] = array[j-1];
                array[j-1] = tmp;
                //因为有元素进行交换，所以不是有序的，标记变为false
                isSorted = false;
            }
        }
        if(isSorted){
            break;
        }
    }
}

public static void main(String[] args){
    int[] array = new int[]{2,3,4,5,6,7,8,1};
    sort(array);
    System.out.println(Arrays.toString(array));
}

这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合，大循环内包含 2 个小循环，第 1 个小循环从左向右比较并交换元素，第 2 个小循环从右向左比较并交换元素。

---

快速排序

同冒泡排序一样，快速排序也属于 交换排序，通过元素之间的比较和交换位置来达到排序的目的。

不同的是，冒泡排序在每一轮中只把 1 个元素冒泡到数列的一端，而快速排序则 在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。

这种思路就叫作分治法。

每次把数列分成两部分，究竟有什么好处呢？

假如给出一个 8 个元素的数列，一般情况下，使用冒泡排序需要比较 7 轮，每一轮把 1 个元素移动到数列的一端，时间复杂度是 O(n^2)。

而快速排序的流程是什么样子呢？

如图所示，在分治法的思想下，原数列在每一轮都被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。

每一轮的比较和交换，需要把数组全部元素都遍历一遍，时间复杂度是 O(n)。这样的遍历一共需要多少轮呢？假如元素个数是 n，那么平均情况下需要 nlog n 轮，因此快速排序算法总体的平均时间复杂度是 O(n log n)。

基准元素的选择

基准元素，英文是 pivot，在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边。

那么如何选择基准元素呢？

最简单的方式是选择数列的第 1 个元素。

这种选择在绝大多数情况下是没有问题的。但是，假如有一个原本逆序的数列，期望排序成顺序数列，那么会出现什么情况呢？

那么，该怎么避免这种情况发生呢？

其实很简单，我们可以 随机选择一个元素作为基准元素，并且让基准元素和数列首元素交换位置。

这样一来，即使在数列完全逆序的情况下，也可以有效地将数列分成两部分。

当然，即使是随机选择基准元素，也会有极小的几率选到数列的最大值或最小值，同样会影响分治的效果。

所以，虽然快速排序的平均时间复杂度是 O(n\ \textit{log} \ n)O(n log n)，但最坏情况下的时间复杂度是 O(n^2)。

元素的交换

选定了基准元素以后，我们要做的就是把其他元素中小于基准元素的都交换到基准元素一边，大于基准元素的都交换到基准元素另一边。

具体如何实现呢？有两种方法。

双边循环法。
单边循环法。

何谓双边循环法？下面来看一看详细过程。

给出原始数列如下，要求对其从小到大进行排序。

首先，选定基准元素 pivot，并且设置两个指针 left 和 right，指向数列的最左和最右两个元素。

接下来进行 第 1 次循环，从 right 指针开始，让指针所指向的元素和基准元素做比较。如果 大于或等于 pivot，则指针向 左 移动；如果 小于pivot，则 right 指针停止移动，切换到 left 指针。

在当前数列中，1 < 4，所以 right 直接停止移动，换到 left 指针，进行下一步行动。

轮到 left 指针行动，让指针所指向的元素和基准元素做比较。如果 小于或等于 pivot，则指针向 右 移动；如果 大于 pivot，则 left 指针停止移动。

由于 left 开始指向的是基准元素，判断肯定相等，所以 left 右移 1 位。

由于 7 > 4，left 指针在元素 7 的位置停下。这时，让 left 和 right 指针所指向的元素进行交换。

接下来，进入第 2 次循环，重新切换到 right 指针，向左移动。right 指针先移动到 8，8 > 4，继续左移。由于 2 < 4，停止在 2 的位置。

按照这个思路，后续步骤如图所示。

public static void quickSort(int[] arr, int startIndex, int endIndex) {
    // 递归结束条件：startIndex大于或等于endIndex时
    if (startIndex >= endIndex) {
        return;
    }
    // 得到基准元素位置
    int pivotIndex = partition(arr, startIndex, endIndex);
    // 根据基准元素，分成两部分进行递归排序
    quickSort(arr, startIndex, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, endIndex);
}
    /**
     * 分治（双边循环法）
     * @param arr 待交换的数组
     * @param startIndex 起始下标
     * @param endIndex 结束下标
     */
private static int partition(int[] arr, int startIndex, int endIndex) {
    // 取第1个位置（也可以选择随机位置）的元素作为基准元素
    int pivot = arr[startIndex];
    int left = startIndex;
    int right = endIndex;

    while( left != right) {
        //控制right指针比较并左移
        while(left<right && arr[right] > pivot){
            right--;
        }
        //控制left指针比较并右移
        while( left<right && arr[left] <= pivot) {
            left++;
        }
        //交换left和right指针所指向的元素
        if(left<right) {
            int p = arr[left];
            arr[left] = arr[right];
            arr[right] = p;
        }
    }
    //pivot和指针重合点交换
    arr[startIndex] = arr[left];
    arr[left] = pivot;
    return left;
}
public static void main(String[] args) {
    int[] arr = new int[] {4,4,6,5,3,2,8,1};
    quickSort(arr, 0, arr.length-1);
    System.out.println(Arrays.toString(arr));
}

在上述代码中，quickSort 方法通过递归的方式，实现了分而治之的思想。

partition 方法则实现了元素的交换，让数列中的元素依据自身大小，分别交换到基准元素的左右两边。在这里，我们使用的交换方式是双边循环法。

单边循环法

双边循环法从数组的两边交替遍历元素，虽然更加直观，但是代码实现相对烦琐。而单边循环法则简单得多，只从数组的一边对元素进行遍历和交换。我们来看一看详细过程。

开始和双边循环法相似，首先选定基准元素 pivot。同时，设置一个 mmark 指针指向数列起始位置，这个 mark 指针代表小于基准元素的区域边界。

接下来，从基准元素的下一个位置开始遍历数组。

如果遍历到的元素大于基准元素，就继续往后遍历。

如果遍历到的元素小于基准元素，则需要做两件事：第一，把 mark 指针右移 1 位，因为小于 pivot 的区域边界增大了 1；第二，让最新遍历到的元素和 mark 指针所在位置的元素交换位置，因为最新遍历的元素归属于小于 pivot 的区域。

首先遍历到元素 7，7 > 4，所以继续遍历。

public static void quickSort(int[] arr, int startIndex, int endIndex) {
    // 递归结束条件：startIndex大于或等于endIndex时
    if (startIndex >= endIndex) {
        return;
    }
    // 得到基准元素位置
    int pivotIndex = partition(arr, startIndex, endIndex);
    // 根据基准元素，分成两部分进行递归排序
    quickSort(arr, startIndex, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, endIndex);
}
/**
 * 分治（单边循环法）
 * @param arr 待交换的数组
 * @param startIndex 起始下标
 * @param endIndex 结束下标
 */
private static int partition(int[] arr, int startIndex, int endIndex) {
    // 取第1个位置（也可以选择随机位置）的元素作为基准元素
    int pivot = arr[startIndex];
    int mark = startIndex;

    for(int i=startIndex+1; i<=endIndex; i++){
        if(arr[i]<pivot){
            mark ++;
            int p = arr[mark];
            arr[mark] = arr[i];
            arr[i] = p;
        }
    }
    arr[startIndex] = arr[mark];
    arr[mark] = pivot;
    return mark;
}
public static void main(String[] args) {
    int[] arr = new int[] {4,4,6,5,3,2,8,1};
    quickSort(arr, 0, arr.length-1);
    System.out.println(Arrays.toString(arr));
}

非递归实现

在第 1 章介绍空间复杂度时我们曾经提到过，代码中一层一层的方法调用，本身就使用了一个方法调用栈。每次进入一个新方法，就相当于入栈；每次有方法返回，就相当于出栈。

所以，可以把原本的递归实现转化成一个栈的实现，在栈中存储每一次方法调用的参数。

public static void quickSort(int[] arr, int startIndex, int endIndex) {
    // 用一个集合栈来代替递归的函数栈
    Stack<Map<String, Integer>> quickSortStack = new Stack<Map<String, Integer>>();
    // 整个数列的起止下标，以哈希的形式入栈
    Map rootParam = new HashMap();
    rootParam.put("startIndex", startIndex);
    rootParam.put("endIndex", endIndex);
    quickSortStack.push(rootParam);

    // 循环结束条件：栈为空时
    while (!quickSortStack.isEmpty()) {
        // 栈顶元素出栈，得到起止下标
        Map<String, Integer> param = quickSortStack.pop();
        // 得到基准元素位置
        int pivotIndex = partition(arr, param.get("startIndex"), param.get("endIndex"));
        // 根据基准元素分成两部分, 把每一部分的起止下标入栈
        if(param.get("startIndex") < pivotIndex -1){
            Map<String, Integer> leftParam = new HashMap<String, Integer>();
            leftParam.put("startIndex", param.get("startIndex"));
            leftParam.put("endIndex", pivotIndex-1);
            quickSortStack.push(leftParam);
        }
        if(pivotIndex + 1 < param.get("endIndex")){
            Map<String, Integer> rightParam = new HashMap<String, Integer>();
            rightParam.put("startIndex", pivotIndex + 1);
            rightParam.put("endIndex", param.get("endIndex"));
            quickSortStack.push(rightParam);
        }
    }
}

/**
 * 分治（单边循环法）
 * @param arr 待交换的数组
 * @param startIndex 起始下标
 * @param endIndex 结束下标
 */
private static int partition(int[] arr, int startIndex, int endIndex) {
    // 取第1个位置（也可以选择随机位置）的元素作为基准元素
    int pivot = arr[startIndex];
    int mark = startIndex;
    for(int i=startIndex+1; i<=endIndex; i++){
        if(arr[i]<pivot){
            mark ++;
            int p = arr[mark];
            arr[mark] = arr[i];
            arr[i] = p;
        }
    }
    arr[startIndex] = arr[mark];
    arr[mark] = pivot;
    return mark;
}
public static void main(String[] args) {
    int[] arr = new int[] {4,7,6,5,3,2,8,1};
    quickSort(arr, 0, arr.length-1);
    System.out.println(Arrays.toString(arr));
}

和刚才的递归实现相比，非递归方式代码的变动只发生在 quickSort 方法中。该方法引入了一个存储 Map 类型元素的栈，用于存储每一次交换时的起始下标和结束下标。

每一次循环，都会让栈顶元素出栈，通过 partition 方法进行分治，并且按照基准元素的位置分成左右两部分，左右两部分再分别入栈。当栈为空时，说明排序已经完毕，退出循环。

---

堆排序

以最大堆为例，如果删除一个最大堆的堆顶（并不是完全删除，而是跟末尾的节点交换位置），经过自我调整，第 2 大的元素就会被交换上来，成为最大堆的新堆顶。

正如上图所示，在删除值为 10 的堆顶节点后，经过调整，值为 9 的新节点就会顶替上来；在删除值为 9 的堆顶节点后，经过调整，值为 8 的新节点就会顶替上来……

由于二叉堆的这个特性，每一次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。那么只要反复删除堆顶，反复调整二叉堆，所得到的集合就会成为一个有序集合。

到此为止，原本的最大二叉堆已经变成了一个从小到大的有序集合。之前说过，二叉堆实际存储在数组中，数组中的元素排列如下。

由此，可以归纳出堆排序算法的步骤。

把无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。
循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。

/**
 * “下沉”调整
 * @param array 待调整的堆
 * @param parentIndex 要“下沉”的父节点
 * @param length 堆的有效大小
 */
public static void downAdjust(int[] array, int parentIndex, int length) {
    // temp保存父节点值，用于最后的赋值
    int temp = array[parentIndex];
    int childIndex = 2 * parentIndex + 1;
    while (childIndex < length) {
        // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
        if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
            childIndex++;
        }
        // 如果父节点大于任何一个孩子的值，则直接跳出
        if (temp >= array[childIndex])
            break;
        //无须真正交换，单向赋值即可
        array[parentIndex] = array[childIndex];
        parentIndex = childIndex;
        childIndex = 2 * childIndex + 1;
    }
    array[parentIndex] = temp;
}

/**
 * 堆排序（升序）
 * @param array 待调整的堆
 */
public static void heapSort(int[] array) {
    // 1.把无序数组构建成最大堆
    for (int i = (array.length-2)/2; i >= 0; i--) {
        downAdjust(array, i, array.length);
    }
    System.out.println(Arrays.toString(array));
    // 2.循环删除堆顶元素，移到集合尾部，调整堆产生新的堆顶
    for (int i = array.length - 1; i > 0; i--) {
        // 最后1个元素和第1个元素进行交换
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;
        // “下沉”调整最大堆
        downAdjust(array, 0, i);
    }
}


public static void main(String[] args) {
    int[] arr = new int[] {1,3,2,6,5,7,8,9,10,0};
    heapSort(arr);
    System.out.println(Arrays.toString(arr));
}

二叉堆的节点「下沉」调整（downAdjust 方法）是堆排序算法的基础，这个调节操作本身的时间复杂度在上一章讲过，是 O(log n)。

我们再来回顾一下堆排序算法的步骤。

把无序数组构建成二叉堆。
循环删除堆顶元素，并将该元素移到集合尾部，调整堆产生新的堆顶。
第 1 步，把无序数组构建成二叉堆，这一步的时间复杂度是 O(n)O(n)。
第 2 步，需要进行 n - 1 次循环。每次循环调用一次 downAdjust 方法，所以第 2 步的计算规模是 (n−1)×log n ，时间复杂度为 O(n log n)。

两个步骤是并列关系，所以整体的时间复杂度是 O(n log n)。

---

计数排序

不基于元素比较，而是利用数组下标来确定元素的正确位置。

假设数组中有 20 个随机整数，取值范围为 0 ～ 10，要求用最快的速度把这 20 个整数从小到大进行排序。

如何给这些无序的随机整数进行排序呢？

考虑到这些整数只能够在 0、1、2、3、4、5、6、7、8、9、10 这 11 个数中取值，取值范围有限。所以，可以根据这有限的范围，建立一个长度为 11 的数组。数组下标从 0 到 10，元素初始值全为 0。

假设 20 个随机整数的值如下所示。

9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9 ，7，9

下面就开始遍历这个无序的随机数列，每一个整数按照其值对号入座，同时，对应数组下标的元素进行加 1 操作。

有了这个统计结果，排序就很简单了。直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次。

0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10

public static int[] countSort(int[] array) {
    //1.得到数列的最大值
    int max = array[0];
    for(int i=1; i<array.length; i++){
        if(array[i] > max){
            max = array[i];
        }
    }
    //2.根据数列最大值确定统计数组的长度
    int[] countArray = new int[max+1];
    //3.遍历数列，填充统计数组
    for(int i=0; i<array.length; i++){
        countArray[array[i]]++;
    }
    //4.遍历统计数组，输出结果
    int index = 0;
    int[] sortedArray = new int[array.length];
    for(int i=0; i<countArray.length; i++){
        for(int j=0; j<countArray[i]; j++){
            sortedArray[index++] = i;
        }
    }
    return sortedArray;
}
public static void main(String[] args) {
    int[] array = new int[] {4,4,6,5,3,2,8,1,7,5,6,0,10};
    int[] sortedArray = countSort(array);
    System.out.println(Arrays.toString(sortedArray));
}

public static int[] countSort(int[] array) {
    //1.得到数列的最大值和最小值，并算出差值d
    int max = array[0];
    int min = array[0];
    for(int i=1; i<array.length; i++) {
        if(array[i] > max) {
            max = array[i];
        }
        if(array[i] < min) {
            min = array[i];
        }
    }
    int d = max - min;
    //2.创建统计数组并统计对应元素的个数
    int[] countArray = new int[d+1];
    for(int i=0; i<array.length; i++) {
        countArray[array[i]-min]++;
    }

    //3.统计数组做变形，后面的元素等于前面的元素之和
    for(int i=1;i<countArray.length;i++) {

        countArray[i] += countArray[i-1];
    }
    //4.倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
    int[] sortedArray = new int[array.length];
    for(int i=array.length-1;i>=0;i--) {
        sortedArray[countArray[array[i]-min]-1]=array[i];
        countArray[array[i]-min]--;
    }
    return sortedArray;
}

public static void main(String[] args) {
    int[] array = new int[] {95,94,91,98,99,90,99,93,91,92};
    int[] sortedArray = countSort(array);
    System.out.println(Arrays.toString(sortedArray));
}

1．当数列最大和最小值差距过大时，并不适合用计数排序。

例如给出 20 个随机整数，范围在 0 到 1 亿之间，这时如果使用计数排序，需要创建长度为 1 亿的数组。不但严重浪费空间，而且时间复杂度也会随之升高。

2．当数列元素不是整数时，也不适合用计数排序。

如果数列中的元素都是小数，如 25.213，或 0.00 000 001 这样的数字，则无法创建对应的统计数组。这样显然无法进行计数排序。

---

桶排序

那么，桶排序中所谓的「桶」，又是什么呢？

每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素。

假设有一个非整数数列如下：

4.5，0.84，3.25，2.18，0.5

让我们来看看桶排序的工作原理。

桶排序的第 1 步，就是创建这些桶，并确定每一个桶的区间范围。

具体需要建立多少个桶，如何确定桶的区间范围，有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除最后一个桶只包含数列最大值外，前面各个桶的区间按照比例来确定。

区间跨度 = （最大值-最小值）/ （桶的数量 - 1）

第 2 步，遍历原始数列，把元素对号入座放入各个桶中。

第 3 步，对每个桶内部的元素分别进行排序（显然，只有第 1 个桶需要排序）。

第 4 步，遍历所有的桶，输出所有元素。

0.5，0.84，2.18，3.25，4.5

到此为止，排序结束。

public static double[] bucketSort(double[] array){

    //1.得到数列的最大值和最小值，并算出差值d
    double max = array[0];
    double min = array[0];
    for(int i=1; i<array.length; i++) {
        if(array[i] > max) {
            max = array[i];
        }
        if(array[i] < min) {
            min = array[i];
        }
    }
    double d = max - min;

    //2.初始化桶
    int bucketNum = array.length;
    ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketList.add(new LinkedList<Double>());
    }

    //3.遍历原始数组，将每个元素放入桶中
    for(int i = 0; i < array.length; i++){
        int num = (int)((array[i] - min) * (bucketNum-1) / d);
        bucketList.get(num).add(array[i]);
    }

    //4.对每个桶内部进行排序
    for(int i = 0; i < bucketList.size(); i++){
        //JDK底层采用了归并排序或归并的优化版本
        Collections.sort(bucketList.get(i));
    }

    //5.输出全部元素
    double[] sortedArray = new double[array.length];
    int index = 0;
    for(LinkedList<Double> list : bucketList){
        for(double element : list){
            sortedArray[index] = element;
            index++;
        }
    }
    return sortedArray;
}

public static void main(String[] args) {
    double[] array = new double[] {4.12,6.421,0.0023,3.0,2.123,8.122,4.12, 10.09};
    double[] sortedArray = bucketSort(array);
    System.out.println(Arrays.toString(sortedArray));
}

在上述代码中，所有的桶都保存在 ArrayList 集合中，每一个桶都被定义成一个链表（LinkedList），这样便于在尾部插入元素。

同时，上述代码使用了 JDK 的集合工具类 Collections.sort 来为桶内部的元素进行排序。Collections.sort 底层采用的是归并排序或 Timsort，各位读者可以简单地把它们当作一种时间复杂度为 O(n log n) 的排序。

假设原始数列有 n 个元素，分成 n 个桶。

下面逐步来分析一下算法复杂度。

第 1 步，求数列最大、最小值，运算量为 n。

第 2 步，创建空桶，运算量为 n。

第 3 步，把原始数列的元素分配到各个桶中，运算量为 n。

第 4 步，在每个桶内部做排序，在元素分布相对均匀的情况下，所有桶的运算量之和为 n。

第 5 步，输出排序数列，运算量为 n。

因此，桶排序的总体时间复杂度为 O(n)。

至于空间复杂度就很容易得到了，同样是 O(n)。