第1章 資料結構與演算法基礎概述

1.1 資料結構和演算法的重要性

• 演算法是程式的靈魂，優秀的程式可以在海量資料計算時，依然保持高速計算

• 資料結構和演算法的關系：

  • 程式 = 資料結構 + 演算法
  • 資料結構是演算法的基礎, 換言之，想要學好演算法，需要把資料結構學到位，

• 資料結構和演算法學習大綱
  

1.2 資料結構概述

• 資料結構可以簡單的理解為資料與資料之間所存在的一些關系，資料的結構分為資料的存盤結構和資料的邏輯結構，

邏輯結構

• 集合結構：資料元素同屬于一個集合，他們之間是并列關系，無其他的關系；可以理解為中學時期學習的集合，在一個范圍之內，有很多的元素，元素間沒有什么關系
• 線性結構：元素之間存在著一對一的關系；可以理解為每個學生對應著一個學號，學號與姓名就是線性結構
• 樹形結構：元素之間存在著一對多的關系，可以簡單理解為家庭族譜一樣，一代接一代
• 圖形結構：元素之間存在多對多的關系，每一個元素可能對應著多個元素，或被多個元素對應，網狀圖

存盤結構

• 順序存盤結構：就是將資料進行連續的存盤，我們可以將它比喻成學校食堂打飯排隊一樣，一個接著一個；
• 鏈式存盤結構：不是按照順序存盤的，后一個進來的數只需要將他的地址告訴前一個節點，前一個節點中就存放了它后面那個數的地址，所以最后一個數的存盤地址就是為null；可以將這種結構比喻成商場吃飯叫號，上面的號碼比喻成是地址，你可以之后后面的地址是什么，上面的其他內容就是該節點的內容；
• 區別：
  • 順序存盤的特點是查詢快，插入或者洗掉慢
  • 鏈式存盤的特點是查詢慢，插入或者洗掉快

1.3 演算法概述

• 同一問題不同解決方法
• 通過時間和空間復雜度判斷演算法的優劣
• 演算法沒有最好的，只有最合適的，學習演算法是為了積累學習思路，掌握學習思路，并不是為了解決某問題去記住某種演算法；對于時間復雜度與空間復雜度，現在大多數開發情況下，我們都在使用以空間換時間，耗費更多的記憶體，來保證擁有更快的速度，
• 各排序演算法復雜度及穩定性：
  

如何理解“大O記法”

對于演算法進行特別具體的細致分析雖然很好，但在實踐中的實際價值有限，對于演算法的時間性質和空間性質，最重要的是其數量級和趨勢，這些是分析演算法效率的主要部分，而計量演算法基本運算元量的規模函式中那些常量因子可以忽略不計，例如，可以認為 3n^2 和 100n^2 屬于同一個量級，如果兩個演算法處理同樣規模實體的代價分別為這兩個函式，就認為它們的效率“差不多”，都為n^2級，

時間復雜度

一個演算法花費的時間與演算法中陳述句的執行次數成正比例，哪個演算法中陳述句執行次數多,它花費時間就多，演算法中的陳述句執行次數稱為陳述句頻度或時間頻度,記為T(n)，n 稱為問題的規模，當 n 不斷變化時，時間頻度T(n)也會不斷變化，但有時我們想知道它變化時呈現什么規律，為此，我們引入時間復雜度概念，

一般情況下，演算法中基本操作重復執行的次數是問題規模 n 的某個函式,用T(n)表示，若有某個輔助函式f(n)，使得當 n 趨近于無究大時，T(n)/f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函式，記作T(n)=O(f(n))，稱O(f(n))為演算法的漸進時間復雜度，簡稱時間復雜度，

有時候，演算法中基本操作重復執行的次數還隨問題的輸入資料集不同而不同,如在冒泡排序中，輸入資料有序而無序，結果是不一樣的，此時，我們計算平均值，

時間復雜度基本計算規則：

• 基本操作，即只有常數項，認為其時間復雜度為O(1)
• 順序結構，時間復雜度按加法進行計算
• 回圈結構，時間復雜度按乘法進行計算
• 分支結構，時間復雜度取最大值
• 判斷一個演算法的效率時，往往只需要關注運算元量的最高次項，其它次要項和常數項可以忽略
• 在沒有特殊說明時，我們所分析的演算法的時間復雜度都是指最壞時間復雜度

常用時間復雜度：

• 注意：經常將log2n（以2為底的對數）簡寫成logn

常見時間復雜度之間的關系：

• 所以時間消耗由小到大為：O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!) < O(n^n)

案例1：

count = 0;				      (1)
	for(i = 0;i <= n;i++)	  (2)
		for(j = 0;j <= n;j++) (3)
			count++;          (4)

• 陳述句（1）執行1次
• 陳述句（2）執行n次
• 陳述句（3）執行n^2次
• 陳述句（4）執行n^2次
• 時間復雜度為：T(n) = 1+n+n^2+n^2 = O(n^2)

案例2：

a = 1; 						(1)
b = 2;						(2)
for(int i = 1;i <= n;i++) { (3)
	int s = a + b;			(4)
	b = a;					(5)
	a = s;					(6)
}	

• 陳述句（1）、（2）執行1次
• 陳述句（3）執行n次
• 陳述句（4）、（5）、（6）執行n次
• 時間復雜度為：T(n) = 1+1+4n = o(n)

案例3：

i = 1;		 (1)
while(i<n) {
	i = i*2; (2)
}	

• 陳述句（1）的頻度是1
• 設陳述句（2）的頻度是f(n)，則2f(n)<=n;f(n)<=log2n,取最大值f(n) = log2n
• 時間復雜度為：T(n) = O(log2n)

空間復雜度

• 演算法的空間復雜度計算公式：S(n) = 0( f(n) )，其中 n 為輸入規模，f(n)為陳述句關于 n 所占存盤空間的函式

• 一個演算法在計算機存盤器上所占用的存盤空間，包括三個方面

  • 存盤演算法本身所占用的存盤空間
  • 演算法的輸入輸出資料所占用的存盤空間
  • 演算法在運行程序中臨時占用的存盤空間

案例：指定的陣列進行反轉，并回傳反轉的內容

解法一：

public static int[] reverse1(int[] arr) {
    int n = arr.length; //申請4個位元組
    int temp; //申請4個位元組
    for (int start = 0, end = n - 1; start <= end; start++, end--) {
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
    return arr;
}

• 空間復雜度為：S(n) = 4+4 = O(8) = O(1)

解法二：

public static int[] reverse2(int[] arr) {
    int n = arr.length; //申請4個位元組
    int[] temp = new int[n]; //申請n*4個位元組+陣列自身頭資訊開銷24個位元組
    for (int i = n - 1; i >= 0; i--) {
        temp[n - 1 - i] = arr[i];
    }
    return temp;
}

• 空間復雜度為：S(n) = 4+4n+24 = O(n+28) = O(n)

根據大O推導法則，演算法一的空間復雜度為0(1),演算法二的空間復雜度為0(n)，所以從空間占用的角度講，演算法一要優于演算法二，

由于java中有記憶體垃圾回識訓制，并且jvm對程式的記憶體占用也有優化(例如即時編譯) , 我們無法精確的評估一個java程式的記憶體占用情況，但是了解了java的基本記憶體占用，使我們可以對java程式的記憶體占用情況進行估算，

由于現在的計算機設備記憶體一般都比較大，基本上個人計算機都是4G起步，大的可以達到32G ，所以記憶體占用一般情況下并不是我們演算法的瓶頸，普通情況下直接說復雜度，默認為演算法的時間復雜度，

但是，如果你做的程式是嵌入式開發，尤其是一些傳感器設備上的內置程式,由于這些設備的記憶體很小, 一般為幾kb，這個時候對演算法的空間復雜度就有要求了，但是一般做java開發的，基本上都是服務器開發, 一般不存在這樣的問題，

第2章 陣列

2.1 陣列概念

陣列是一種線性表資料結構，它用一組連續的記憶體空間，來存盤一組具有相同型別的資料，這里我們要抽取出三個跟陣列相關的關鍵詞：線性表，連續記憶體空間，相同資料型別；陣列具有連續的記憶體空間，存盤相同型別的資料，正是該特性使得陣列具有一個特性：隨機訪問，但是有利有弊，這個特性雖然使得訪問陣列邊得非常容易，但是也使得陣列插入和洗掉操作會變得很低效，插入和洗掉資料后為了保證連續性,要做很多資料搬遷作業，

查找陣列中的方法有兩種：

• 線性查找：線性查找就是簡單的查找陣列中的元素
• 二分法查找：二分法查找要求目標陣列必須是有序的，

2.2 無序陣列

• 實作類：

public class MyArray {
	//宣告一個陣列
	private long[] arr;
	
	//有效資料的長度
	private int elements;
	
	//無參建構式，默認長度為50
	public MyArray(){
		arr = new long[50];
	}
	
	public MyArray(int maxsize){
		arr = new long[maxsize];
	}
	
	
	//添加資料
	public void insert(long value){
		arr[elements] = value;
		elements++;
	}
	
	//顯示資料
	public void display(){
		System.out.print("[");
		for(int i = 0;i < elements;i++){
			System.out.print(arr[i] + " ");
		}
		System.out.println("]");
	}
	
	//根據下標查找資料
	public long get(int index){
		if(index >= elements || index < 0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			return arr[index];
		}
	}
	
	/**
	 * 根據值查詢
	 * @param value 需要被查詢的值
	 * @return 被查詢值的下標
	 */
	public int search(int value){
		//宣告一個變數i用來記錄該資料的下標值
		int i ;
		for(i = 0;i < elements;i++){
			if(value == arr[i]){
				break;
			}
		}
		//如果查詢到最后一個元素依然沒有找到
		if(i == elements){
			return -1;
		}else{
			return i;
		}
	}
	
	//根據下標洗掉資料
	public void delete(int index){
		if(index >= elements || index < 0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			//洗掉該元素后，后面所有元素前移一位
			for(int i = index; i < elements;i++){
				arr[i] = arr[i+1];
			}
			elements--;
		}
		
	}
	/**
	 * 替換資料
	 * @param index 被替換的下標
	 * @param newvalue 新的資料
	 */
	public void change(int index,int newvalue){
		if(index >= elements || index < 0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			arr[index] = newvalue;
		}
	} 
}

• 優點：插入快（時間復雜度為：O(1)）、如果知道下標，可以很快存盤
• 缺點：查詢慢（時間復雜度為：O(n)）、洗掉慢

2.3 有序陣列

• 實作類：

public class MyOrderArray { 
	private long[] arr;
	
	private int elements;
	
	public MyOrderArray(){
		arr = new long[50];
	}
	
	public MyOrderArray(int maxsize){
		arr = new long[maxsize];
	}
	
	//添加資料
	public void insert(int value){
		int i;
		for(i = 0;i < elements;i++){
			if(arr[i] > value){
				break;
			}
		}
		for(int j = elements;j > i;j--){
			arr[j] = arr[j -1];
		}
		arr[i] = value;
		elements++;
	}
	
	
	//洗掉資料
	public void delete(int index){
		if(index >=elements || index <0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			for(int i = index;i < elements; i++){
				arr[i] = arr[i+1];
			}
			elements--;
		}
	}
	
	//修改資料
	public void change(int index,int value){
		if(index >= elements || index < 0){
			throw new IndexOutOfBoundsException();
		}else{
			arr[index] = value;
		}
	}
	
	//根據下標查詢資料
	public long get(int index){
		if(index >= elements || index < 0){
			throw new IndexOutOfBoundsException();
		}else{
			return arr[index];
		}
	}
	
	//展示資料
	public void display(){
		System.out.print("[");
		for(int i = 0; i < elements;i++){
			System.out.print(arr[i] + " ");
		}
		System.out.println("]");
	}
	
	
	//二分法查找資料
	public int binarySearch(long value){
			//宣告三個指標分別指向陣列的頭，尾，中間
			int low = 0;
			int pow = elements;
			int middle = 0;
			
			while(true){
				middle = (low + pow) / 2;
				//如果中指標所指的值等于帶查詢數
				if(arr[middle] == value){
					return middle;
				}else if(low > pow){
					return -1;
				}else{
					if(arr[middle] > value){
						//待查詢的數在左邊,右指標重新改變指向
						pow = middle-1;
					}else{
						//帶查詢的數在右邊，左指標重新改變指向
						low = middle +1;
					}
				}
			}
	}
}

• 優點：查詢快（時間復雜度為：O(logn)）
• 缺點：增刪慢（時間復雜度為：O(n)）

第三章 堆疊

3.1 堆疊概念

堆疊（stack），有些地方稱為堆疊，是一種容器，可存入資料元素、訪問元素、洗掉元素，它的特點在于只能允許在容器的一端（稱為堆疊頂端指標，英語：top）進行加入資料（英語：push）和輸出資料（英語：pop）的運算，沒有了位置概念，保證任何時候可以訪問、洗掉的元素都是此前最后存入的那個元素，確定了一種默認的訪問順序，

由于堆疊資料結構只允許在一端進行操作，因而按照后進先出的原理運作，

堆疊可以用順序表實作，也可以用鏈表實作，

3.2 堆疊的操作

• Stack() 創建一個新的空堆疊
• push(element) 添加一個新的元素element到堆疊頂
• pop() 取出堆疊頂元素
• peek() 回傳堆疊頂元素
• is_empty() 判斷堆疊是否為空
• size() 回傳堆疊的元素個數

實作類：

package mystack;

public class MyStack {

    //堆疊的底層使用陣列來存盤資料
    //private int[] elements;
    int[] elements; //測驗時使用

    public MyStack() {
        elements = new int[0];
    }

    //添加元素
    public void push(int element) {
        //創建一個新的陣列
        int[] newArr = new int[elements.length + 1];
        //把原陣列中的元素復制到新陣列中
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        //把添加的元素放入新陣列中
        newArr[elements.length] = element;
        //使用新陣列替換舊陣列
        elements = newArr;
    }

    //取出堆疊頂元素
    public int pop() {
        //當堆疊中沒有元素
        if (is_empty()) {
            throw new RuntimeException("堆疊空");
        }
        //取出陣列的最后一個元素
        int element = elements[elements.length - 1];
        //創建一個新陣列
        int[] newArr = new int[elements.length - 1];
        //原陣列中除了最后一個元素其他元素放入新陣列
        for (int i = 0; i < elements.length - 1; i++) {
            newArr[i] = elements[i];
        }
        elements = newArr;
        return element;
    }

    //查看堆疊頂元素
    public int peek() {
        return elements[elements.length - 1];
    }

    //判斷堆疊是否為空
    public boolean is_empty() {
        return elements.length == 0;
    }

    //查看堆疊的元素個數
    public int size() {
        return elements.length;
    }
}

測驗類：

package mystack;

public class Demo {
    public static void main(String[] args) {
        MyStack ms = new MyStack();
        //添加元素
        ms.push(9);
        ms.push(8);
        ms.push(7);

        //取出堆疊頂元素
//        System.out.println(ms.pop()); //7
//        System.out.println(ms.pop()); //8
//        System.out.println(ms.pop()); //9

        //查看堆疊頂元素
        System.out.println(ms.peek()); //7
        System.out.println(ms.peek()); //7

        //查看堆疊中元素個數
        System.out.println(ms.size()); //3
    }
}

第4章 佇列

4.1 佇列概念

佇列（Queue）是只允許在一端進行插入操作，而在另一端進行洗掉操作的線性表，

佇列是一種先進先出的（First In First Out）的線性表，簡稱FIFO，允許插入的一端為隊尾，允許洗掉的一端為隊頭，佇列不允許在中間部位進行操作！假設佇列是q=（a1，a2，……，an），那么a1就是隊頭元素，而an是隊尾元素，這樣我們就可以洗掉時，總是從a1開始，而插入時，總是在佇列最后，這也比較符合我們通常生活中的習慣，排在第一個的優先出列，最后來的當然排在隊伍最后，

同堆疊一樣，佇列也可以用順序表或者鏈表實作，

4.2 佇列的操作

• Queue() 創建一個空的佇列
• enqueue(element) 往佇列中添加一個element元素
• dequeue() 從佇列頭部洗掉一個元素
• is_empty() 判斷一個佇列是否為空
• size() 回傳佇列的大小

實作類：

public class MyQueue {

    int[] elements;

    public MyQueue() {
        elements = new int[0];
    }

    //入隊
    public void enqueue(int element) {
        //創建一個新的陣列
        int[] newArr = new int[elements.length + 1];
        //把原陣列中的元素復制到新陣列中
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        //把添加的元素放入新陣列中
        newArr[elements.length] = element;
        //使用新陣列替換舊陣列
        elements = newArr;
    }

    //出隊
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("隊空，無資料");
        }
        //把陣列中第1個元素取出來
        int element = elements[0];
        //創建一個新陣列
        int[] newArr = new int[elements.length - 1];
        //把原陣列除了第一個資料，其他存入新陣列
        for (int i = 0; i < newArr.length; i++) {
            newArr[i] = elements[i + 1];
        }
        //新陣列替換舊陣列
        elements = newArr;

        return element;
    }

    //判斷是否隊空
    public boolean isEmpty() {
        return elements.length==0;
    }

    //獲取佇列長度
    public int size() {
        return elements.length;
    }
}

測驗類：

public class Demo {
    public static void main(String[] args) {
        MyQueue mq = new MyQueue();

        //入隊
        mq.enqueue(1);
        mq.enqueue(2);
        mq.enqueue(3);

        //出隊
        System.out.println(mq.dequeue()); //1
        System.out.println(mq.dequeue()); //2
        System.out.println(mq.dequeue()); //3
    }
}

第5章 鏈表

5.1 單鏈表

單鏈表概念

單鏈表也叫單向鏈表，是鏈表中最簡單的一種形式，它的每個節點包含兩個域，一個資訊域（元素域）和一個鏈接域，這個鏈接指向鏈表中的下一個節點，而最后一個節點的鏈接域則指向一個空值，

• 表元素域data用來存放具體的資料，
• 鏈接域next用來存放下一個節點的位置

單鏈表操作

• is_empty() 鏈表是否為空
• length() 鏈表長度
• travel() 遍歷整個鏈表
• add(item) 鏈表頭部添加元素
• append(item) 鏈表尾部添加元素
• insert(pos, item) 指定位置添加元素
• remove(item) 洗掉節點
• search(item) 查找節點是否存在

實作類：

//一個節點
public class Node {

    //節點內容
    int data;
    //下一個節點
    Node next;

    public Node(int data) {
        this.data = data;
    }

    //為節點追加節點
    public Node append(Node node) {
        //當前節點
        Node currentNode = this;
        //回圈向后找
        while (true) {
            //取出下一個節點
            Node nextNode = currentNode.next();
            //如果下一個節點為null，當前節點已經是最后一個節點
            if (nextNode == null) {
                break;
            }
            //賦給當前節點，無線向后找
            currentNode = nextNode;
        }
        //把需要追加的節點，追加為找到的當前節點（最后一個節點）的下一個節點
        currentNode.next = node;
        return this;
    }

    //顯示所有節點資訊
    public void show() {
        Node currentNode = this;
        while (true) {
            System.out.print(currentNode.data + " ");
            //取出下一個節點
            currentNode = currentNode.next;
            //如果是最后一個節點
            if (currentNode == null) {
                break;
            }
        }
        System.out.println();
    }

    //插入一個節點作為當前節點的下一個節點
    public void after(Node node) {
        //取出下一個節點，作為下下一個節點
        Node nextNext = next;
        //把新節點作為當前節點的下一個節點
        this.next = node;
        //把下下一個節點設定為新節點的下一個節點
        node.next = nextNext;

    }

    //洗掉下一個節點
    public void removeNode() {
        //取出下下一個節點
        Node newNext = next.next;
        //把下下一個節點設定為當前節點的下一個節點
        this.next = newNext;
    }

    //獲取下一個節點
    public Node next() {
        return this.next;
    }

    //獲取節點中的資料
    public int getData() {
        return this.data;
    }

    //判斷節點是否為最后一個節點
    public boolean isLast() {
        return next == null;
    }

}

測驗類：

public class Demo {
    public static void main(String[] args) {
        //創建節點
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        //追加節點
        n1.append(n2).append(n3);
        //取出下一個節點資料
        System.out.println(n1.next().next().getData()); //3
        //判斷節點是否為最后一個節點
        System.out.println(n1.isLast()); //false
        System.out.println(n1.next().next().isLast()); //true
        //顯示所有節點資訊
        n1.show(); //1 2 3
        //洗掉一個節點
//        n1.next.removeNode();
//        n1.show(); //1 2
        //插入一個新節點
        n1.next.after(new Node(0));
        n1.show(); //1 2 0 3
    }
}

5.2 回圈鏈表

回圈鏈表概念

單鏈表的一個變形是單向回圈鏈表，鏈表中最后一個節點的 next 域不再為 None，而是指向鏈表的頭節點，

回圈鏈表操作

實作類：

//表示一個節點
public class LoopNode {

    //節點內容
    int data;
    //下一個節點
    LoopNode next = this; //與單鏈表的區別，追加了一個this，當只有一個節點時指向自己

    public LoopNode(int data) {
        this.data = data;
    }

    //插入一個節點
    public void after(LoopNode node) {
        LoopNode afterNode = this.next;
        this.next = node;
        node.next = afterNode;
    }

    //洗掉一個節點
    public void removeNext() {
        LoopNode newNode = this.next.next;
        this.next = newNode;
    }

    //獲取下一個節點
    public LoopNode next() {
        return this.next;
    }

    //獲取節點中的資料
    public int getData() {
        return this.data;
    }

}

測驗類：

public class Demo {
    public static void main(String[] args) {
        //創建節點
        LoopNode n1 = new LoopNode(1);
        LoopNode n2 = new LoopNode(2);
        LoopNode n3 = new LoopNode(3);
        LoopNode n4 = new LoopNode(4);

        //增加節點
        n1.after(n2);
        n2.after(n3);
        n3.after(n4);
        System.out.println(n1.next().getData()); //2
        System.out.println(n2.next().getData()); //3
        System.out.println(n3.next().getData()); //4
        System.out.println(n4.next().getData()); //1
    }
}

5.3 雙向回圈鏈表

雙向回圈鏈表概念

在雙向鏈表中有兩個指標域，一個是指向前驅結點的prev，一個是指向后繼結點的next指標

雙向回圈鏈表操作

實作類：

public class DoubleNode {
    //上一個節點
    DoubleNode pre = this;
    //下一個節點
    DoubleNode next = this;
    //節點資料
    int data;

    public DoubleNode(int data) {
        this.data = data;
    }

    //增加節點
    public void after(DoubleNode node) {
        //原來的下一個節點
        DoubleNode nextNext = next;
        //新節點作為當前節點的下一個節點
        this.next = node;
        //當前節點作為新節點的前一個節點
        node.pre = this;
        //原來的下一個節點作為新節點的下一個節點
        node.next = nextNext;
        //原來的下一個節點的上一個節點為新節點
        nextNext.pre = node;
    }

    //獲取下一個節點
    public DoubleNode getNext() {
        return this.next;
    }

    //獲取上一個節點
    public DoubleNode getPre() {
        return this.pre;
    }

    //獲取資料
    public int getData() {
        return this.data;
    }
}

測驗類：

public class Demo {
    public static void main(String[] args) {
        //創建節點
        DoubleNode n1 = new DoubleNode(1);
        DoubleNode n2 = new DoubleNode(2);
        DoubleNode n3 = new DoubleNode(3);

        //追加節點
        n1.after(n2);
        n2.after(n3);

        //查看上一個，自己，下一個節點內容
        System.out.println(n2.getPre().getData()); //1
        System.out.println(n2.getData()); //2
        System.out.println(n2.getNext().getData()); //3

        System.out.println(n1.getPre().getData()); //3
        System.out.println(n3.getNext().getData()); //1
    }
}

第6章 樹結構基礎

6.1 為什么要使用樹結構

線性結構中不論是陣列還是鏈表，他們都存在著詬病；比如查找某個數必須從頭開始查，消耗較多的時間，使用樹結構，在插入和查找的性能上相對都會比線性結構要好

6.2 樹結構基本概念

示意圖

1、根節點：最頂上的唯一的一個；如：A

2、雙親節點：子節點的父節點就叫做雙親節點；如A是B、C、D的雙親節點，B是E、F的雙親節點

3、子節點：雙親節點所產生的節點就是子節點

4、路徑：從根節點到目標節點所走的路程叫做路徑；如A要訪問F，路徑為A-B-F

5、節點的度：有多少個子節點就有多少的度（最下面的度一定為0，所以是葉子節點）

6、節點的權：在節點中所存的數字

7、葉子節點：沒有子節點的節點，就是沒有下一代的節點；如：E、F、C、G

8、子樹：在整棵樹中將一部分看成也是一棵樹，即使只有一個節點也是一棵樹，不過這個樹是在整個大樹職中的，包含的關系

9、層：就是族譜中有多少代的人；如：A是1，B、C、D是2，E、F、G是3

10、樹的高度：樹的最大的層數：就是層數中的最大值

11、森林：多個樹組成的集合

6.3 樹的種類

無序樹：樹中任意節點的子節點之間沒有順序關系，這種樹稱為無序樹，也稱為自由樹；

有序樹：樹中任意節點的子節點之間有順序關系，這種樹稱為有序樹；

• 二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹；
  • 完全二叉樹：對于一顆二叉樹，假設其深度為d(d>1)，除了第d層外，其它各層的節點數目均已達最大值，且第d層所有節點從左向右連續地緊密排列，這樣的二叉樹被稱為完全二叉樹，其中滿二叉樹的定義是所有葉節點都在最底層的完全二叉樹;
  • 平衡二叉樹（AVL樹）：當且僅當任何節點的兩棵子樹的高度差不大于1的二叉樹；
  • 排序二叉樹（二叉查找樹（英語：Binary Search Tree），也稱二叉搜索樹、有序二叉樹）；
• 霍夫曼樹（用于資訊編碼）：帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹；
• B樹：一種對讀寫操作進行優化的自平衡的二叉查找樹，能夠保持資料有序，擁有多余兩個子樹，

6.4 樹的存盤與表示

順序存盤：將資料結構存盤在固定的陣列中，然在遍歷速度上有一定的優勢，但因所占空間比較大，是非主流二叉樹，二叉樹通常以鏈式存盤，

鏈式存盤：

由于對節點的個數無法掌握，常見樹的存盤表示都轉換成二叉樹進行處理，子節點個數最多為2

6.5 常見的一些樹的應用場景

1、xml，html等，那么撰寫這些東西的決議器的時候，不可避免用到樹

2、路由協議就是使用了樹的演算法

3、mysql資料庫索引

4、檔案系統的目錄結構

5、所以很多經典的AI演算法其實都是樹搜索，此外機器學習中的decision tree也是樹結構

第7章 二叉樹大全

7.1 二叉樹的定義

任何一個節點的子節點數量不超過 2，那就是二叉樹；二叉樹的子節點分為左節點和右節點，不能顛倒位置

7.2 二叉樹的性質(特性)

性質1：在二叉樹的第i層上至多有2^(i-1)個結點（i>0）

性質2：深度為k的二叉樹至多有2^k - 1個結點（k>0）

性質3：對于任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1;

性質4：具有n個結點的完全二叉樹的深度必為 log2(n+1)

性質5：對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結點，其左孩子編號必為2i，其右孩子編號必為2i＋1；其雙親的編號必為i/2（i＝1 時為根,除外）

7.3 滿二叉樹與完全二叉樹

滿二叉樹： 所有葉子結點都集中在二叉樹的最下面一層上，而且結點總數為：2^n-1 (n為層數 / 高度）

完全二叉樹： 所有的葉子節點都在最后一層或者倒數第二層，且最后一層葉子節點在左邊連續，倒數第二層在右邊連續（滿二叉樹也是屬于完全二叉樹）（從上往下，從左往右能挨著數滿）

7.4 鏈式存盤的二叉樹

創建二叉樹：首先需要一個樹的類，還需要另一個類用來存放節點，設定節點；將節點放入樹中，就形成了二叉樹；（節點中需要權值，左子樹，右子樹，并且都能對他們的值進行設定），

樹的遍歷：

• 先序遍歷：根節點，左節點，右節點（如果節點有子樹，先從左往右遍歷子樹，再遍歷兄弟節點）
  先序遍歷結果為：A B D H I E J C F K G

• 中序遍歷：左節點，根節點，右節點（中序遍歷可以看成，二叉樹每個節點，垂直方向投影下來（可以理解為每個節點從最左邊開始垂直掉到地上），然后從左往右數）
  中遍歷結果為：H D I B E J A F K C G

• 后序遍歷：左節點，右節點，根節點
  后序遍歷結果：H I D J E B K F G C A

• 層次遍歷：從上往下，從左往右
  層次遍歷結果：A B C D E F G H I J K
  

查找節點：先對樹進行一次遍歷，然后找出要找的那個數；因為有三種排序方法，所以查找節點也分為先序查找，中序查找，后序查找；

洗掉節點：由于鏈式存盤，不能找到要刪的數直接洗掉，需要找到他的父節點，然后將指向該數設定為null；所以需要一個變數來指向父節點，找到數后，再斷開連接，

代碼實作：

• 樹類

public class BinaryTree {

    TreeNode root;

    //設定根節點
    public void setRoot(TreeNode root) {
        this.root = root;
    }

    //獲取根節點
    public TreeNode getRoot() {
        return root;
    }

    //先序遍歷
    public void frontShow() {
        if (root != null) {
            root.frontShow();
        }
    }

    //中序遍歷
    public void middleShow() {
        if (root != null) {
            root.middleShow();
        }
    }

    //后序遍歷
    public void afterShow() {
        if (root != null) {
            root.afterShow();
        }
    }

    //先序查找
    public TreeNode frontSearch(int i) {
        return root.frontSearch(i);
    }

    //洗掉一個子樹
    public void delete(int i) {
        if (root.value == i) {
            root = null;
        } else {
            root.delete(i);
        }
    }
}

• 節點類

public class TreeNode {
    //節點的權
    int value;
    //左兒子
    TreeNode leftNode;
    //右兒子
    TreeNode rightNode;

    public TreeNode(int value) {
        this.value = value;
    }

    //設定左兒子
    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    //設定右兒子
    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }

    //先序遍歷
    public void frontShow() {
        //先遍歷當前節點的值
        System.out.print(value + " ");
        //左節點
        if (leftNode != null) {
            leftNode.frontShow(); //遞回思想
        }
        //右節點
        if (rightNode != null) {
            rightNode.frontShow();
        }
    }

    //中序遍歷
    public void middleShow() {
        //左節點
        if (leftNode != null) {
            leftNode.middleShow(); //遞回思想
        }
        //先遍歷當前節點的值
        System.out.print(value + " ");
        //右節點
        if (rightNode != null) {
            rightNode.middleShow();
        }
    }

    //后續遍歷
    public void afterShow() {
        //左節點
        if (leftNode != null) {
            leftNode.afterShow(); //遞回思想
        }
        //右節點
        if (rightNode != null) {
            rightNode.afterShow();
        }
        //先遍歷當前節點的值
        System.out.print(value + " ");
    }

    //先序查找
    public TreeNode frontSearch(int i) {
        TreeNode target = null;
        //對比當前節點的值
        if (this.value == i) {
            return this;
            //當前節點不是要查找的節點
        } else {
            //查找左兒子
            if (leftNode != null) {
                //查找的話t賦值給target，查不到target還是null
                target = leftNode.frontSearch(i);
            }
            //如果target不為空，說明在左兒子中已經找到
            if (target != null) {
                return target;
            }
            //如果左兒子沒有查到，再查找右兒子
            if (rightNode != null) {
                target = rightNode.frontSearch(i);
            }
        }
        return target;
    }

    //洗掉一個子樹
    public void delete(int i) {
        TreeNode parent = this;
        //判斷左兒子
        if (parent.leftNode != null && parent.leftNode.value == i) {
            parent.leftNode = null;
            return;
        }
        //判斷右兒子
        if (parent.rightNode != null && parent.rightNode.value == i) {
            parent.rightNode = null;
            return;
        }
        //如果都不是，遞回檢查并洗掉左兒子
        parent = leftNode;
        if (parent != null) {
            parent.delete(i);
        }
        //遞回檢查并洗掉右兒子
        parent = rightNode;
        if (parent != null) {
            parent.delete(i);
        }

    }
}

• 測驗類

public class Demo {
    public static void main(String[] args) {
        //創建一棵樹
        BinaryTree binaryTree = new BinaryTree();
        //創建一個根節點
        TreeNode root = new TreeNode(1);
        //把根節點賦給樹
        binaryTree.setRoot(root);
        //創建左,右節點
        TreeNode rootLeft = new TreeNode(2);
        TreeNode rootRight = new TreeNode(3);
        //把新建的節點設定為根節點的子節點
        root.setLeftNode(rootLeft);
        root.setRightNode(rootRight);
        //為第二層的左節點創建兩個子節點
        rootLeft.setLeftNode(new TreeNode(4));
        rootLeft.setRightNode(new TreeNode(5));
        //為第二層的右節點創建兩個子節點
        rootRight.setLeftNode(new TreeNode(6));
        rootRight.setRightNode(new TreeNode(7));

        //先序遍歷
        binaryTree.frontShow(); //1 2 4 5 3 6 7
        System.out.println();
        //中序遍歷
        binaryTree.middleShow(); //4 2 5 1 6 3 7
        System.out.println();
        //后序遍歷
        binaryTree.afterShow(); //4 5 2 6 7 3 1
        System.out.println();

        //先序查找
        TreeNode result = binaryTree.frontSearch(5);
        System.out.println(result); //binarytree.TreeNode@1b6d3586

        //洗掉一個子樹
        binaryTree.delete(2);
        binaryTree.frontShow(); //1 3 6 7 ，2和他的子節點被洗掉了
    }
}

7.5 順序存盤的二叉樹

概述：順序存盤使用陣列的形式實作；由于非完全二叉樹會導致陣列中出現空缺，有的位置不能填上數字，所以順序存盤二叉樹通常情況下只考慮完全二叉樹

原理： 順序存盤在陣列中是按照第一層第二層一次往下存盤的，遍歷方式也有先序遍歷、中序遍歷、后續遍歷

性質：

• 第n個元素的左子節點是：2*n+1；
• 第n個元素的右子節點是：2*n+2；
• 第n個元素的父節點是：（n-1)/2

代碼實作：

• 樹類

public class ArrayBinaryTree {

    int[] data;

    public ArrayBinaryTree(int[] data) {
        this.data = data;
    }

    //多載先序遍歷方法，不用每次傳引數了,保證每次從頭開始
    public void frontShow() {
        frontShow(0);
    }

    //先序遍歷
    public void frontShow(int index) {
        if (data == null || data.length == 0) {
            return;
        }
        //先遍歷當前節點的內容
        System.out.print(data[index] + " ");
        //處理左子樹：2*index+1
        if (2 * index + 1 < data.length) {
            frontShow(2 * index + 1);
        }
        //處理右子樹：2*index+2
        if (2 * index + 2 < data.length) {
            frontShow(2 * index + 2);
        }
    }
}

• 測驗類

public class Demo {
    public static void main(String[] args) {
        int[] data = {1,2,3,4,5,6,7};
        ArrayBinaryTree tree = new ArrayBinaryTree(data);
        //先序遍歷
        tree.frontShow(); //1 2 4 5 3 6 7
    }
}

7.6 線索二叉樹(Threaded BinaryTree)

為什么使用線索二叉樹？

當用二叉鏈表作為二叉樹的存盤結構時，可以很方便的找到某個結點的左右孩子；但一般情況下，無法直接找到該結點在某種遍歷序列中的前驅和后繼結點

原理：n個結點的二叉鏈表中含有n+1(2n-(n-1)=n+1個空指標域，利用二叉鏈表中的空指標域，存放指向結點在某種遍歷次序下的前驅和后繼結點的指標，

例如：某個結點的左孩子為空，則將空的左孩子指標域改為指向其前驅；如果某個結點的右孩子為空，則將空的右孩子指標域改為指向其后繼（這種附加的指標稱為"線索"）

代碼實作：

• 樹類

public class ThreadedBinaryTree {

    ThreadedNode root;
    //用于臨時存盤前驅節點
    ThreadedNode pre = null;
    
    //設定根節點
    public void setRoot(ThreadedNode root) {
        this.root = root;
    }

    //中序線索化二叉樹
    public void threadNodes() {
        threadNodes(root);
    }

    public void threadNodes(ThreadedNode node) {
        //當前節點如果為null，直接回傳
        if (node == null) {
            return;
        }
        //處理左子樹
        threadNodes(node.leftNode);

        //處理前驅節點
        if (node.leftNode == null) {
            //讓當前節點的左指標指向前驅節點
            node.leftNode = pre;
            //改變當前節點左指標型別
            node.leftType = 1;
        }
        //處理前驅的右指標，如果前驅節點的右指標是null（沒有右子樹）
        if (pre != null && pre.rightNode == null) {
            //讓前驅節點的右指標指向當前節點
            pre.rightNode = node;
            //改變前驅節點的右指標型別
            pre.rightType = 1;
        }

        //每處理一個節點，當前節點是下一個節點的前驅節點
        pre = node;

        //處理右子樹
        threadNodes(node.rightNode);
    }

    //遍歷線索二叉樹
    public void threadIterate() {
        //用于臨時存盤當前遍歷節點
        ThreadedNode node = root;
        while (node != null) {
            //回圈找到最開始的節點
            while (node.leftType == 0) {
                node = node.leftNode;
            }
            //列印當前節點的值
            System.out.print(node.value + " ");
            //如果當前節點的右指標指向的是后繼節點，可能后繼節點還有后繼節點
            while (node.rightType == 1) {
                node = node.rightNode;
                System.out.print(node.value + " ");
            }
            //替換遍歷的節點
            node = node.rightNode;

        }
    }

    //獲取根節點
    public ThreadedNode getRoot() {
        return root;
    }

    //先序遍歷
    public void frontShow() {
        if (root != null) {
            root.frontShow();
        }
    }

    //中序遍歷
    public void middleShow() {
        if (root != null) {
            root.middleShow();
        }
    }

    //后序遍歷
    public void afterShow() {
        if (root != null) {
            root.afterShow();
        }
    }

    //先序查找
    public ThreadedNode frontSearch(int i) {
        return root.frontSearch(i);
    }

    //洗掉一個子樹
    public void delete(int i) {
        if (root.value == i) {
            root = null;
        } else {
            root.delete(i);
        }
    }
}

• 節點類

public class ThreadedNode {
    //節點的權
    int value;
    //左兒子
    ThreadedNode leftNode;
    //右兒子
    ThreadedNode rightNode;
    //標識指標型別,1表示指向上一個節點，0
    int leftType;
    int rightType;

    public ThreadedNode(int value) {
        this.value = value;
    }

    //設定左兒子
    public void setLeftNode(ThreadedNode leftNode) {
        this.leftNode = leftNode;
    }

    //設定右兒子
    public void setRightNode(ThreadedNode rightNode) {
        this.rightNode = rightNode;
    }

    //先序遍歷
    public void frontShow() {
        //先遍歷當前節點的值
        System.out.print(value + " ");
        //左節點
        if (leftNode != null) {
            leftNode.frontShow(); //遞回思想
        }
        //右節點
        if (rightNode != null) {
            rightNode.frontShow();
        }
    }

    //中序遍歷
    public void middleShow() {
        //左節點
        if (leftNode != null) {
            leftNode.middleShow(); //遞回思想
        }
        //先遍歷當前節點的值
        System.out.print(value + " ");
        //右節點
        if (rightNode != null) {
            rightNode.middleShow();
        }
    }

    //后續遍歷
    public void afterShow() {
        //左節點
        if (leftNode != null) {
            leftNode.afterShow(); //遞回思想
        }
        //右節點
        if (rightNode != null) {
            rightNode.afterShow();
        }
        //先遍歷當前節點的值
        System.out.print(value + " ");
    }

    //先序查找
    public ThreadedNode frontSearch(int i) {
        ThreadedNode target = null;
        //對比當前節點的值
        if (this.value == i) {
            return this;
            //當前節點不是要查找的節點
        } else {
            //查找左兒子
            if (leftNode != null) {
                //查找的話t賦值給target，查不到target還是null
                target = leftNode.frontSearch(i);
            }
            //如果target不為空，說明在左兒子中已經找到
            if (target != null) {
                return target;
            }
            //如果左兒子沒有查到，再查找右兒子
            if (rightNode != null) {
                target = rightNode.frontSearch(i);
            }
        }
        return target;
    }

    //洗掉一個子樹
    public void delete(int i) {
        ThreadedNode parent = this;
        //判斷左兒子
        if (parent.leftNode != null && parent.leftNode.value == i) {
            parent.leftNode = null;
            return;
        }
        //判斷右兒子
        if (parent.rightNode != null && parent.rightNode.value == i) {
            parent.rightNode = null;
            return;
        }
        //如果都不是，遞回檢查并洗掉左兒子
        parent = leftNode;
        if (parent != null) {
            parent.delete(i);
        }
        //遞回檢查并洗掉右兒子
        parent = rightNode;
        if (parent != null) {
            parent.delete(i);
        }

    }
}

• 測驗類

public class Demo {
    public static void main(String[] args) {
        //創建一棵樹
        ThreadedBinaryTree binaryTree = new ThreadedBinaryTree();
        //創建一個根節點
        ThreadedNode root = new ThreadedNode(1);
        //把根節點賦給樹
        binaryTree.setRoot(root);
        //創建左,右節點
        ThreadedNode rootLeft = new ThreadedNode(2);
        ThreadedNode rootRight = new ThreadedNode(3);
        //把新建的節點設定為根節點的子節點
        root.setLeftNode(rootLeft);
        root.setRightNode(rootRight);
        //為第二層的左節點創建兩個子節點
        rootLeft.setLeftNode(new ThreadedNode(4));
        ThreadedNode fiveNode = new ThreadedNode(5);
        rootLeft.setRightNode(fiveNode);
        //為第二層的右節點創建兩個子節點
        rootRight.setLeftNode(new ThreadedNode(6));
        rootRight.setRightNode(new ThreadedNode(7));

        //中序遍歷
        binaryTree.middleShow(); //4 2 5 1 6 3 7
        System.out.println();
        //中序線索化二叉樹
        binaryTree.threadNodes();
//        //獲取5的后繼節點
//        ThreadedNode afterFive = fiveNode.rightNode;
//        System.out.println(afterFive.value); //1
        binaryTree.threadIterate(); //4 2 5 1 6 3 7
    }
}

7.7 二叉排序樹（Binary Sort Tree）

無序序列：
二叉排序樹圖解：

概述：二叉排序樹（Binary Sort Tree）也叫二叉查找樹或者是一顆空樹，對于二叉樹中的任何一個非葉子節點，要求左子節點比當前節點值小，右子節點比當前節點值大

特點：

• 查找性能與插入洗掉性能都適中還不錯
• 中序遍歷的結果剛好是從大到小

創建二叉排序樹原理：其實就是不斷地插入節點，然后進行比較，

洗掉節點

• 洗掉葉子節點，只需要找到父節點，將父節點與他的連接斷開即可
• 洗掉有一個子節點的就需要將他的子節點換到他現在的位置
• 洗掉有兩個子節點的節點，需要使用他的前驅節點或者后繼節點進行替換，就是左子樹最右下方的數（最大的那個）或右子樹最左邊的樹（最小的數）；即離節點值最接近的值；（還要注解要去判斷這個值有沒有右節點，有就要將右節點移上來）

代碼實作：

• 樹類

public class BinarySortTree {
    Node root;

    //添加節點
    public void add(Node node) {
        //如果是一顆空樹
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    //中序遍歷
    public void middleShow() {
        if (root != null) {
            root.middleShow(root);
        }
    }

    //查找節點
    public Node search(int value) {
        if (root == null) {
            return null;
        }
        return root.search(value);
    }

    //查找父節點
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        }
        return root.searchParent(value);
    }

    //洗掉節點
    public void delete(int value) {
        if (root == null) {
            return;
        } else {
            //找到這個節點
            Node target = search(value);
            //如果沒有這個節點
            if (target == null) {
                return;
            }
            //找到他的父節點
            Node parent = searchParent(value);
            //要洗掉的節點是葉子節點
            if (target.left == null && target.left == null) {
                //要洗掉的節點是父節點的左子節點
                if (parent.left.value == value) {
                    parent.left = null;
                }
                //要洗掉的節點是父節點的右子節點
                else {
                    parent.right = null;
                }
            }
            //要洗掉的節點有兩個子節點的情況
            else if (target.left != null && target.right != null) {
                //洗掉右子樹中值最小的節點，并且獲取到值
                int min = deletMin(target.right);
                //替換目標節點中的值
                target.value = min;
            }
            //要洗掉的節點有一個左子節點或右子節點
            else {
                //有左子節點
                if (target.left != null) {
                    //要洗掉的節點是父節點的左子節點
                    if (parent.left.value == value) {
                        parent.left = target.left;
                    }
                    //要洗掉的節點是父節點的右子節點
                    else {
                        parent.right = target.left;
                    }

                }
                //有右子節點
                else {
                    //要洗掉的節點是父節點的左子節點
                    if (parent.left.value == value) {
                        parent.left = target.right;
                    }
                    //要洗掉的節點是父節點的右子節點
                    else {
                        parent.right = target.right;
                    }
                }
            }
        }
    }

    //洗掉一棵樹中最小的節點
    private int deletMin(Node node) {
        Node target = node;
        //遞回向左找最小值
        while (target.left != null) {
            target = target.left;
        }
        //洗掉最小的節點
        delete(target.value);
        return target.value;
    }
}

• 節點類

public class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    //向子樹中添加節點
    public void add(Node node) {
        if (node == null) {
            return;
        }
        /*判斷傳入的節點的值比當前紫薯的根節點的值大還是小*/
        //添加的節點比當前節點更小(傳給左節點）
        if (node.value < this.value) {
            //如果左節點為空
            if (this.left == null) {
                this.left = node;

            }
            //如果不為空
            else {
                this.left.add(node);
            }

        }
        //添加的節點比當前節點更大(傳給右節點）
        else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }

    //中序遍歷二叉排序樹，結果剛好是從小到大
    public void middleShow(Node node) {
        if (node == null) {
            return;
        }
        middleShow(node.left);
        System.out.print(node.value + " ");
        middleShow(node.right);
    }

    //查找節點
    public Node search(int value) {
        if (this.value == value) {
            return this;
        } else if (value < this.value) {
            if (left == null) {
                return null;
            }
            return left.search(value);
        } else {
            if (right == null) {
                return null;
            }
            return right.search(value);
        }
    }

    //查找父節點
    public Node searchParent(int value) {
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            if (this.value > value && this.left != null) {
                return this.left.searchParent(value);
            } else if (this.value < value && this.right != null) {
                return this.right.searchParent(value);
            }
            return null;
        }
    }
}

• 測驗類

public class Demo {
    public static void main(String[] args) {
        int[] arr = {8, 3, 10, 1, 6, 14, 4, 7, 13};
        //創建一顆二叉排序樹
        BinarySortTree bst = new BinarySortTree();
        //回圈添加
/*        for(int i=0;i< arr.length;i++) {
            bst.add(new Node(arr[i]));
        }*/
        for (int i : arr) {
            bst.add(new Node(i));
        }

        //中序遍歷
        bst.middleShow(); //1 3 4 6 7 8 10 13 14
        System.out.println();

        //查找節點
        Node node = bst.search(10);
        System.out.println(node.value);//10

        Node node2 = bst.search(20);
        System.out.println(node2); //null

        //查找父節點
        Node node3 = bst.searchParent(1);
        Node node4 = bst.searchParent(14);
        System.out.println(node3.value); //3
        System.out.println(node4.value); //10

        //洗掉葉子節點
//        bst.delete(13);
//        bst.middleShow(); //1 3 4 6 7 8 10 14
//        System.out.println();
//        //洗掉只有一個子節點的節點
//        bst.delete(10);
//        bst.middleShow(); //1 3 4 6 7 8 ；10和14都沒了

        //洗掉有兩個子節點的節點
        bst.delete(3);
        bst.middleShow(); //1 4 6 7 8 10 13 14
    }
}

7.8 平衡二叉樹（ Balanced Binary Tree）

為什么使用平衡二叉樹？

平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹，這個方案很好的解決了二叉查找樹退化成鏈表的問題，把插入，查找，洗掉的時間復雜度最好情況和最壞情況都維持在O(logN)，但是頻繁旋轉會使插入和洗掉犧牲掉O(logN)左右的時間，不過相對二叉查找樹來說，時間上穩定了很多，

二叉排序樹插入 {1,2,3,4,5,6} 這種資料結果如下圖所示：

平衡二叉樹插入 {1,2,3,4,5,6} 這種資料結果如下圖所示：

如何判斷平衡二叉樹？

• 1、是二叉排序樹
• 2、任何一個節點的左子樹或者右子樹都是平衡二叉樹（左右高度差小于等于 1）

（1）下圖不是平衡二叉樹，因為它不是二叉排序樹違反第 1 條件

（2）下圖不是平衡二叉樹，因為有節點子樹高度差大于 1 違法第 2 條件（5的左子樹為0，右子樹為2）

（3）下圖是平衡二叉樹，因為符合 1、2 條件

相關概念

平衡因子 BF

• 定義：左子樹和右子樹高度差
• 計算：左子樹高度 - 右子樹高度的值
• 別名：簡稱 BF（Balance Factor）
• 一般來說 BF 的絕對值大于 1，,平衡樹二叉樹就失衡，需要旋轉糾正

最小不平衡子樹

• 距離插入節點最近的，并且 BF 的絕對值大于 1 的節點為根節點的子樹，

• 旋轉糾正只需要糾正最小不平衡子樹即可

• 例子如下圖所示：
  

旋轉方式

2 種旋轉方式:

左旋 :

• 舊根節點為新根節點的左子樹
• 新根節點的左子樹（如果存在）為舊根節點的右子樹

右旋：

• 舊根節點為新根節點的右子樹
• 新根節點的右子樹（如果存在）為舊根節點的左子樹

4 種旋轉糾正型別：

• 左左型：插入左孩子的左子樹，右旋
• 右右型：插入右孩子的右子樹，左旋
• 左右型：插入左孩子的右子樹，先左旋，再右旋
• 右左型：插入右孩子的左子樹，先右旋，再左旋
  

左左型：

第三個節點（1）插入的時候，BF(3) = 2，BF(2) = 1，右旋，根節點順時針旋轉

右右型：

第三個節點（3）插入的時候，BF(1)=-2 BF(2)=-1，RR 型失衡，左旋，根節點逆時針旋轉

左右型：

第三個節點（3）插入的 時候，BF(3)=2 BF(1)=-1 LR 型失衡，先 左旋 再 右旋


右左型：

第三個節點（1）插入的 時候，BF(1)=-2 BF(3)=1 RL 型失衡，先 右旋 再 左旋

實體

（1）、依次插入 3、2、1 插入第三個點 1 的時候 BF(3)=2 BF(2)=1，LL 型失衡，對最小不平衡樹 {3,2,1}進行 右旋

• 舊根節點（節點 3）為新根節點（節點 2）的右子樹
• 新根節點（節點 2）的右子樹（這里沒有右子樹）為舊根節點的左子樹
  

（2）依次插入 4 ，5 插入 5 點的時候 BF(3) = -2 BF(4)=-1，RR 型失衡，對最小不平衡樹 {3,4,5} 進行左旋

• 舊根節點（節點 3）為新根節點（節點 4）的左子樹
• 新根節點（節點 4）的左子樹（這里沒有左子樹）為舊根節點的右子樹
  

（3）插入 4 ，5 插入 5 點的時候 BF(2)=-2 BF(4)=-1 ，RR 型失衡 對最小不平衡樹{1,2,4}進行左旋

• 舊根節點（節點 2）為新根節點（節點 4）的左子樹
  
• 新根節點（節點 4）的 左子樹（節點 3）為舊根節點的右子樹
  

（4）插入 7 節點的時候 BF(5)=-2, BF(6)=-1 ，RR 型失衡，對最小不平衡樹 進行左旋

• 舊根節點（節點 5）為新根節點（節點 6）的左子樹
• 新根節點的左子樹（這里沒有）為舊根節點的右子樹
  

（5）依次插入 10 ，9 ，插入 9 點的時候 BF(10) = 1，BF(7) = -2，RL 型失衡，對先右旋再左旋，右子樹先右旋

• 舊根節點（節點 10）為新根節點（節點 9）的右子樹
• 新根節點（節點 9）的右子樹（這里沒有右子樹）為舊根節點的左子樹
  
  最小不平衡子樹再左旋：
• 舊根節點（節點 7）為新根節點（節點 9）的左子樹
• 新根節點（節點 9）的左子樹（這里沒有左子樹）為舊根節點的右子樹
  

代碼實作

• 節點類

public class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    //獲取當前節點高度
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

    //獲取左子樹高度
    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        return left.height();
    }

    //獲取右子樹高度
    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }


    //向子樹中添加節點
    public void add(Node node) {
        if (node == null) {
            return;
        }
        /*判斷傳入的節點的值比當前紫薯的根節點的值大還是小*/
        //添加的節點比當前節點更小(傳給左節點）
        if (node.value < this.value) {
            //如果左節點為空
            if (this.left == null) {
                this.left = node;

            }
            //如果不為空
            else {
                this.left.add(node);
            }

        }
        //添加的節點比當前節點更大(傳給右節點）
        else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
        //查詢是否平衡
        //右旋轉
        if (leftHeight() - rightHeight() >= 2) {
            //雙旋轉，當左子樹左邊高度小于左子樹右邊高度時
            if (left != null && left.leftHeight() < left.rightHeight()) {
                //左子樹先進行左旋轉
                left.leftRotate();
                //整體進行右旋轉
                rightRotate();
            }
            //單旋轉
            else {
                rightRotate();
            }
        }
        //左旋轉
        if (leftHeight() - rightHeight() <= -2) {
            //雙旋轉
            if (right != null && right.rightHeight() < right.leftHeight()) {
                right.rightRotate();
                leftRotate();
            }
            //單旋轉
            else {
                leftRotate();
            }
        }
    }

    //右旋轉
    private void rightRotate() {
        //創建一個新的節點，值等于當前節點的值
        Node newRight = new Node(value);
        //把新節點的右子樹設定為當前節點的右子樹
        newRight.right = right;
        //把新節點的左子樹設定為當前節點的左子樹的右子樹
        newRight.left = left.right;
        //把當前節點的值換位左子節點的值
        value = left.value;
        //把當前節點的左子樹設定為左子樹的左子樹
        left = left.left;
        //把當前節點設定為新節點
        right = newRight;
    }

    //左旋轉
    private void leftRotate() {
        //創建一個新的節點，值等于當前節點的值
        Node newLeft = new Node(value);
        //把新節點的左子樹設定為當前節點的左子樹
        newLeft.left = left;
        //把新節點的右子樹設定為當前節點的右子樹的左子樹
        newLeft.right = right.left;
        //把當前節點的值換位右子節點的值
        value = right.value;
        //把當前節點的右子樹設定為右子樹的右子樹
        right = right.right;
        //把當前節點設定為新節點
        left = newLeft;
    }

    //中序遍歷二叉排序樹，結果剛好是從小到大
    public void middleShow(Node node) {
        if (node == null) {
            return;
        }
        middleShow(node.left);
        System.out.print(node.value + " ");
        middleShow(node.right);
    }

    //查找節點
    public Node search(int value) {
        if (this.value == value) {
            return this;
        } else if (value < this.value) {
            if (left == null) {
                return null;
            }
            return left.search(value);
        } else {
            if (right == null) {
                return null;
            }
            return right.search(value);
        }
    }

    //查找父節點
    public Node searchParent(int value) {
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            if (this.value > value && this.left != null) {
                return this.left.searchParent(value);
            } else if (this.value < value && this.right != null) {
                return this.right.searchParent(value);
            }
            return null;
        }
    }
}

• 測驗類

public class Demo {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6};
        //創建一顆二叉排序樹
        BinarySortTree bst = new BinarySortTree();
        //回圈添加
        for (int i : arr) {
            bst.add(new Node(i));
        }
        //查看高度
        System.out.println(bst.root.height()); //3
        //查看節點值
        System.out.println(bst.root.value); //根節點為4
        System.out.println(bst.root.left.value); //左子節點為2
        System.out.println(bst.root.right.value); //右子節點為5
    }
}

第8章 赫夫曼樹

8.1 赫夫曼樹概述

HuffmanTree因為翻譯不同所以有其他的名字：赫夫曼樹、霍夫曼樹、哈夫曼樹

赫夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹，所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數），樹的路徑長度是從樹根到每一結點的路徑長度之和，記為WPL=（W1L1+W2L2+W3L3+…+WnLn），N個權值Wi（i=1,2,…n）構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li（i=1,2,…n），可以證明赫夫曼樹的WPL是最小的，

8.2 赫夫曼樹定義

路徑： 路徑是指從一個節點到另一個節點的分支序列，

路徑長度： 指從一個節點到另一個結點所經過的分支數目， 如下圖：從根節點到a的分支數目為2

樹的路徑長度： 樹中所有結點的路徑長度之和為樹的路徑長度PL， 如下圖：PL為10

節點的權： 給樹的每個結點賦予一個具有某種實際意義的實數，我們稱該實數為這個結點的權，如下圖：7、5、2、4

帶權路徑長度： 從樹根到某一結點的路徑長度與該節點的權的乘積，叫做該結點的帶權路徑長度，如下圖：A的帶權路徑長度為2*7=14

樹的帶權路徑長度（WPL）： 樹的帶權路徑長度為樹中所有葉子節點的帶權路徑長度之和

最優二叉樹：權值最大的節點離跟節點越近的二叉樹，所得WPL值最小，就是最優二叉樹，如下圖：（b）

• （a）WPL=9*2+4*2+5*2+2*2=40
• （b）WPL=9*1+5*2+4*3+2*3=37
• （c） WPL=4*1+2*2+5*3+9*3=50

8.3 構造赫夫曼樹步驟

對于陣列{5,29,7,8,14,23,3,11}，我們把它構造成赫夫曼樹

第一步：使用陣列中所有元素創建若干個二叉樹，這些值作為節點的權值（只有一個節點），

第二步：將這些節點按照權值的大小進行排序，

第三步：取出權值最小的兩個節點，并創建一個新的節點作為這兩個節點的父節點，這個父節點的權值為兩個子節點的權值之和，將這兩個節點分別賦給父節點的左右節點

第四步：洗掉這兩個節點，將父節點添加進集合里

第五步：重復第二步到第四步，直到集合中只剩一個元素，結束回圈

8.4 代碼實作

• 節點類

//介面實作排序功能
public class Node implements Comparable<Node> {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        return -(this.value - o.value); //集合倒敘，從大到小
    }

    @Override
    public String toString() {
        return "Node value=" + value ;
    }
}

• 測驗類

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Demo {
    public static void main(String[] args) {
        int[] arr = {5, 29, 7, 8, 14, 23, 3, 11};
        Node node = createHuffmanTree(arr);
        System.out.println(node); //Node value=100
    }

    //創建赫夫曼樹
    public static Node createHuffmanTree(int[] arr) {
        //使用陣列中所有元素創建若干個二叉樹（只有一個節點）
        List<Node> nodes = new ArrayList<>();
        for (int value : arr) {
            nodes.add(new Node(value));
        }

        //回圈處理
        while (nodes.size() > 1) {
            //排序
            Collections.sort(nodes);
            //取出最小的兩個二叉樹（集合為倒敘，從大到小）
            Node left = nodes.get(nodes.size() - 1); //權值最小
            Node right = nodes.get(nodes.size() - 2); //權值次小
            //創建一個新的二叉樹
            Node parent = new Node(left.value + right.value);
            //洗掉原來的兩個節點
            nodes.remove(left);
            nodes.remove(right);
            //新的二叉樹放入原來的二叉樹集合中
            nodes.add(parent);
            //列印結果
            System.out.println(nodes);
        }
        return nodes.get(0);
    }
}

• 回圈次數結果

[Node value=29, Node value=23, Node value=14, Node value=11, Node value=8, Node value=7, Node value=8]
[Node value=29, Node value=23, Node value=14, Node value=11, Node value=8, Node value=15]
[Node value=29, Node value=23, Node value=15, Node value=14, Node value=19]
[Node value=29, Node value=23, Node value=19, Node value=29]
[Node value=29, Node value=29, Node value=42]
[Node value=42, Node value=58]
[Node value=100]
Node value=100

Process finished with exit code 0

第9章 多路查找樹（2-3樹、2-3-4樹、B樹、B+樹）

9.1 為什么使用多路查找樹

二叉樹存在的問題

二叉樹需要加載到記憶體的，如果二叉樹的節點少，沒有什么問題，但是如果二叉樹的節點很多(比如1億)， 就存在如下問題:

• 問題1：在構建二叉樹時，需要多次進行I/O操作(海量資料存在資料庫或檔案中)，節點海量，構建二叉樹時，速度有影響.

• 問題2：節點海量，也會造成二叉樹的高度很大，會降低操作速度.
  

解決上述問題 —> 多叉樹

多路查找樹

• 1、在二叉樹中，每個節點有資料項，最多有兩個子節點，如果允許每個節點可以有更多的資料項和更多的子節點，就是多叉樹（multiway tree）
• 2、后面我們講解的"2-3樹"，"2-3-4樹"就是多叉樹，多叉樹通過重新組織節點，減少樹的高度，能對二叉樹進行優化，
• 3、舉例說明(下面2-3樹就是一顆多叉樹)
  

9.2 2-3樹

2-3樹定義

• 所有葉子節點都要在同一層
• 二節點要么有兩個子節點，要么沒有節點
• 三節點要么沒有節點，要么有三個子節點
• 不能出現節點不滿的情況
  

2-3樹插入的操作

插入原理：

對于2-3樹的插入來說，與平衡二叉樹相同，插入操作一定是發生在葉子節點上，并且節點的插入和洗掉都有可能導致不平衡的情況發生，在插入和洗掉節點時也是需要動態維持平衡的，但維持平衡的策略和AVL樹是不一樣的，

AVL樹向下添加節點之后通過旋轉來恢復平衡，而2-3樹是通過節點向上分裂來維持平衡的，也就是說2-3樹插入元素的程序中層級是向上增加的，因此不會導致葉子節點不在同一層級的現象發生，也就不需要旋轉了，

三種插入情況：

1）對于空樹，插入一個2節點即可；

2）插入節點到一個2節點的葉子上，由于本身就只有一個元素，所以只需要將其升級為3節點即可（如：插入3），

3）插入節點到一個3節點的葉子上，因為3節點本身最大容量，因此需要拆分，且將樹中兩元素或者插入元素的三者中選擇其一向上移動一層，

分為三種情況：

• 升級父節點（插入5）
  
• 升級根節點（插入11）
  
• 增加樹高度（插入2，從下往上拆）
  

2-3樹洗掉的操作

洗掉原理：2-3樹的洗掉也分為三種情況，與插入相反，

三種洗掉情況：

1）所刪元素位于一個3節點的葉子節點上，直接洗掉，不會影響樹結構（如：洗掉9）

2）所刪元素位于一個2節點上，直接洗掉，破壞樹結構

分為四種情況：

• 此節點雙親也是2節點，且擁有一個3節點的右孩子（如：洗掉1）
  

• 此節點的雙親是2節點，它右孩子也是2節點（如：洗掉4）
  

• 此節點的雙親是3節點（如：洗掉10）
  

• 當前樹是一個滿二叉樹，降低樹高（如：洗掉8）
  

3）所刪元素位于非葉子的分支節點，此時按樹中序遍歷得到此元素的前驅或后續元素，補位

兩種情況：

• 分支節點是2節點（如：洗掉4）
  
• 分支節點是3節點（如：洗掉12）
  

9.3 2-3-4樹

2-3-4樹是2-3樹的擴展，包括了 4 節點的使用，一個 4 節點包含小中大三個元素和四個孩子（或沒有孩子）

2-3-4樹的插入操作

1）如果待插入的節點不是 4 節點，則直接插入即可

2）如果待插入的節點是 4 節點，則先把新節點臨時插入進去變成 5 節點，然后對 5 節點進行向上分裂、合并，5 節點分裂成兩個 2 節點（5 節點最小的元素、5 節點第二個元素）、1個 3 節點（5 節點后兩個元素），然后將分裂之后的第2個 2 節點向上合并到父節點中，然后把父節點作為插入元素之后的當前節點，重復（1）、（2）步驟，直到滿足2-3-4樹的定義性質

2-3-4樹的洗掉操作

洗掉順序使1,6,3,4,5,2,9

9.4 B樹

B樹（BTree）是一種平衡的多路查找樹，2-3樹和2-3-4樹都是B樹的特例，

我們把結點最大的孩子樹目稱為B樹的階，因此，2-3樹是3階B樹，2-3-4樹是4階B樹

如下圖，比如說要查找7，首先從外存讀取得到根節點3,5,8三個元素，發現7不在，但是5、8之間，因此就通過A2再讀取外存的2,6,7節點找到結束，

B樹的資料結構為內外存的資料互動準備的，當要處理的資料很大時，無法一次全部裝入記憶體，這時對B樹調整，使得B樹的階數與硬碟存盤的頁面大小相匹配，比如說一棵B樹的階為1001（即1個節點包含1000個關鍵字），高度為2（從0開始），它可以存盤超過10億個關鍵字（1001x1001x1000+1001x1000+1000）,只要讓根節點持久的保留在記憶體中，那么在這顆樹上，尋找某一個關鍵字至多需要兩次硬碟的讀取即可，

對于n個關鍵字的m階B樹，最壞情況查找次數計算
第一層至少1個節點，第二層至少2個節點，由于除根節點外每個分支節點至少有?m/2?棵子樹，則第三層至少有2x?m/2?個節點，，，這樣第k+1層至少有2x(?m/2?)^(k-1),實際上，k+1層的節點就是葉子節點，若m階B樹有n個關鍵字，那么當你找到葉子節點，其實也就等于查找不成功的節點為n+1，因此
n+1>=2x(?m/2?)^(k-1),即

在含有n個關鍵字的B樹上查找時，從根節點到關鍵位元組點的路徑上涉及的節點數不超多

9.5 B+樹

B+樹可以說是B樹的升級版，相對于B樹來說B+樹更充分的利用了節點的空間，讓查詢速度更加穩定，其速度完全接近于二分法查找，大部分檔案系統和資料均采用B+樹來實作索引結構，
?
下圖B樹，我們要遍歷它，假設每個節點都屬于硬碟的不同頁面，我們為了中序遍歷所有的元素，頁面2-頁面1-頁面3-頁面1-頁面4-頁面1-頁面5，頁面1遍歷了3次，而且我們每經過節點遍歷時，都會對節點中的元素進行一次遍歷

B+樹是應檔案系統所需而出的一種B樹的變形樹，在B樹中，每一個元素樹中只出現一次，而B+樹中，出現在分支節點中的元素會被當做他們在該分支節點位置的中序后繼者（葉子節點）中再次列出，另外，每一個葉子節點都會保存一個指向后一葉子節點的指標，
下圖就是B+樹，灰色關鍵字，在根節點出現，在葉子節點中再次列出

一棵m階的B+樹和m階的B樹的差異在于：

• 有n棵子樹的非葉節點中包含有n個關鍵字（B樹中是n-1個關鍵字），但是每個關鍵字不保存資料，只用來保存葉子節點相同關鍵字的索引，所有資料都保存在葉子節點，（此處，對于非葉節點的m顆子樹和n個關鍵字的關系，mysql的索引結構似乎是m=n+1，而不是上面的m=n）
• 所有的非葉節點元素都同時存在于子節點，在子節點元素中是最大（或最小）元素，
• 所有的葉子節點包含全部關鍵字的資訊，及指向含這些關鍵字所指向的具體磁盤記錄的指標data，并且每一個葉子節點帶有指向下一個相鄰的葉節點指標，形成鏈表

9.6 總結

• B樹的非葉節點會存盤關鍵字及其對應的資料地址，B+樹的非葉節點只存關鍵字索引，不會存具體的資料地址，因此B+樹的一個節點相比B樹能存盤更多的索引元素，一次性讀入記憶體的需要查找的關鍵字也就越多，B+樹的高度更小，相對IO讀寫次數就降低了，

• B樹的查詢效率并不穩定，最好的情況只查詢一次（根節點），最壞情況是查找到葉子節點，而B+樹由于非葉節點不存資料地址，而只是葉子節點中關鍵字的索引，所有查詢都要查找到葉子節點才算命中，查詢效率比較穩定，這對于sql陳述句的優化是非常有幫助的，

• B+樹所有葉子節點形成有序鏈表，只需要去遍歷葉子節點就可以實作整棵樹的遍歷，方便資料的范圍查詢，而B樹不支持這樣的操作或者說效率太低，

• 現代資料庫和檔案系統的索引表大部分是使用B+樹來實作的，但并不是全部

第10章 圖結構

10.1 圖的基本概念

圖（Graph）是一種復雜的非線性結構，在圖結構中，每個元素都可以有零個或多個前驅，也可以有零個或多個后繼，也就是說，元素之間的關系是任意的，

常用術語：

術語	含義
頂點	圖中的某個結點
邊	頂點之間連線
相鄰頂點	由同一條邊連接在一起的頂點
度	一個頂點的相鄰頂點個數
簡單路徑	由一個頂點到另一個頂點的路線，且沒有重復經過頂點
回路	出發點和結束點都是同一個頂點
無向圖	圖中所有的邊都沒有方向
有向圖	圖中所有的邊都有方向
無權圖	圖中的邊沒有權重值
有權圖	圖中的邊帶有一定的權重值

圖的結構很簡單，就是由頂點 V 集和邊 E 集構成，因此圖可以表示成 G = (V,E)

無向圖：

若頂點 Vi 到 Vj 之間的邊沒有方向，則稱這條邊為無向邊 (Edge) ，用無序偶對 (Vi，Vj) 來表示，如果圖中任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖 (Undirected graphs)，

如：下圖就是一個無向圖，由于是無方向的，連接頂點 A 與 D 的邊，可以表示無序佇列（A，D），也可以寫成 （D，A）,但不能重復，頂點集合 V = {A,B,C,D}；邊集合 E = {(A,B),(A,D),(A,C)(B,C),(C,D),}

有向圖：

用有序偶<Vi，Vj>來表示，Vi 稱為弧尾 (Tail) ， Vj稱為弧頭 (Head)， 如果圖中任意兩個頂點之間的邊都是有向邊，則稱該圖為有向圖 (Directed grahs)，

如：下圖就是一個有向圖，連接頂點 A 到 D 的有向邊就是弧，A是弧尾，D 是弧頭， <A, D>表示弧， 注意不能寫成<D,A>，其中頂點集合 V = { A,B,C,D}； 弧集合 E = {<A,D>,<B,A>,<B,C>,<C,A>}

注意：無向邊用小括號 “()” 表示，而有向邊則是用尖括號"<>"表示

有權圖：

有些圖的邊或弧具有與它相關的數字，這種與圖的邊或弧相關的數叫做權 (Weight) ，這些權可以表示從一個頂點到另一個頂點的距離或耗費，這種帶權的圖通常稱為網 (Network)，

如下圖

10.2 圖的存盤結構及實作

圖結構的常見的兩個存盤方式： 鄰接矩陣 、鄰接表

鄰接矩陣

圖中的 0 表示該頂點無法通向另一個頂點，相反 1 就表示該頂點能通向另一個頂點

先來看第一行，該行對應的是頂點A，那我們就拿頂點A與其它點一一對應，發現頂點A除了不能通向頂點D和自身，可以通向其它任何一個的頂點

因為該圖為無向圖，因此頂點A如果能通向另一個頂點，那么這個頂點也一定能通向頂點A，所以這個頂點對應頂點A的也應該是 1

雖然我們確實用鄰接矩陣表示了圖結構，但是它有一個致命的缺點，那就是矩陣中存在著大量的 0，這在程式中會占據大量的記憶體，此時我們思考一下，0 就是表示沒有，沒有為什么還要寫，所以我們來看一下第二種表示圖結構的方法，它就很好的解決了鄰接矩陣的缺陷

代碼實作：

• 頂點類

public class Vertex {

    private String value;

    public Vertex(String value) {
        this.value = value;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return value;
    }
}

• 圖類

public class Graph {

    private Vertex[] vertex; //頂點陣列
    private int currentSize; //默認頂點位置
    public int[][] adjMat; //鄰接表

    public Graph(int size) {
        vertex = new Vertex[size];
        adjMat = new int[size][size];
    }

    //向圖中加入頂點
    public void addVertex(Vertex v) {
        vertex[currentSize++] = v;
    }

    //添加邊
    public void addEdge(String v1, String v2) {
        //找出兩個點的下標
        int index1 = 0;
        for (int i = 0; i < vertex.length; i++) {
            if (vertex[i].getValue().equals(v1)) {
                index1 = i;
                break;
            }
        }
        int index2 = 0;
        for (int i = 0; i < vertex.length; i++) {
            if (vertex[i].getValue().equals(v2)) {
                index2 = i;
                break;
            }
        }
        //表示兩個點互通
        adjMat[index1][index2] = 1;
        adjMat[index2][index1] = 1;
    }
}

• 測驗類

public class Demo {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("A");
        Vertex v2 = new Vertex("B");
        Vertex v3 = new Vertex("C");
        Vertex v4 = new Vertex("D");
        Vertex v5 = new Vertex("E");
        Graph g = new Graph(5);
        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        g.addVertex(v4);
        g.addVertex(v5);

        //增加邊
        g.addEdge("A", "B");
        g.addEdge("A", "C");
        g.addEdge("A", "E");
        g.addEdge("C", "E");
        g.addEdge("C", "D");

        for (int[] a : g.adjMat) {
            System.out.println(Arrays.toString(a));
        }
    }
}

• 結果值

[0, 1, 1, 0, 1]
[1, 0, 0, 0, 0]
[1, 0, 0, 1, 1]
[0, 0, 1, 0, 0]
[1, 0, 1, 0, 0]

鄰接表

鄰接表 是由每個頂點以及它的相鄰頂點組成的

如上圖：圖中最左側紅色的表示各個頂點，它們對應的那一行存盤著與它相關聯的頂點

• 頂點A 與 頂點B 、頂點C 、頂點E 相關聯
• 頂點B 與 頂點A 相關聯
• 頂點C 與 頂點A 、頂點D 、頂點E 相關聯
• 頂點D 與 頂點C 相關聯
• 頂點E 與 頂點A 、頂點C 相關聯

10.3 圖的遍歷方式及實作

從圖中某一頂點出發訪遍圖中其余頂點，且使每一個頂點僅被訪問一次，這一程序就叫做圖的遍歷

在圖結構中，存在著兩種遍歷搜索的方式，分別是 廣度優先搜索 和 深度優先搜索

廣度優先搜索

廣度優先遍歷（BFS）：類似于圖的層次遍歷，它的基本思想是：首先訪問起始頂點v，然后選取v的所有鄰接點進行訪問，再依次對v的鄰接點相鄰接的所有點進行訪問，以此類推，直到所有頂點都被訪問過為止

BFS和樹的層次遍歷一樣，采取佇列實作，這里添加一個標記陣列，用來標記遍歷過的頂點

執行步驟：

• 1、先把 A 壓入佇列，然后做出隊操作，A 出隊
• 2、把 A 直接相關的頂點 ，B、F 做入隊操作
• 3、B 做出隊操作，B 相關的點 C、I、G 做入隊操作
• 4、F 做出隊操作，F 相關的點 E 做入隊操作
• 5、C 做出隊操作，C 相關的點 D 做入隊操作
• 6、I 做出隊操作（I 相關的點B、C、D 都已經做過入隊操作了，不能重復入隊）
• 7、G 做出隊操作，G 相關的點 H 做入隊操作
• 8、E 做出隊操作…
• 9、D 做出隊操作…
• 10、H 做出隊操作，沒有元素了

代碼實作：

深度優先搜索

深度優先遍歷（DFS）：從一個頂點開始，沿著一條路徑一直搜索，直到到達該路徑的最后一個結點，然后回退到之前經過但未搜索過的路徑繼續搜索，直到所有路徑和結點都被搜索完畢

DFS與二叉樹的先序遍歷類似，可以采用遞回或者堆疊的方式實作

執行步驟：

• 1、從 1 出發，路徑為：1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 5 -> 4
• 2、當搜索到 4 時，相鄰沒有發現未被訪問的點，此時我們要往后倒退，找尋別的沒搜索過的路徑
• 3、退回到 5 ，相鄰沒有發現未被訪問的點，繼續后退
• 4、退回到 8 ，相鄰發現未被訪問的點 7，路徑為：8 -> 7
• 5、當搜索到 7 ，相鄰沒有發現未被訪問的點，，此時我們要往后倒退…
• 6、退回路徑7 -> 8 -> 9 -> 6 -> 3 -> 2 -> 1，流程結束

代碼實作：

• 堆疊類

public class MyStack {

    //堆疊的底層使用陣列來存盤資料
    //private int[] elements;
    int[] elements; //測驗時使用

    public MyStack() {
        elements = new int[0];
    }

    //添加元素
    public void push(int element) {
        //創建一個新的陣列
        int[] newArr = new int[elements.length + 1];
        //把原陣列中的元素復制到新陣列中
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        //把添加的元素放入新陣列中
        newArr[elements.length] = element;
        //使用新陣列替換舊陣列
        elements = newArr;
    }

    //取出堆疊頂元素
    public int pop() {
        //當堆疊中沒有元素
        if (is_empty()) {
            throw new RuntimeException("堆疊空");
        }
        //取出陣列的最后一個元素
        int element = elements[elements.length - 1];
        //創建一個新陣列
        int[] newArr = new int[elements.length - 1];
        //原陣列中除了最后一個元素其他元素放入新陣列
        for (int i = 0; i < elements.length - 1; i++) {
            newArr[i] = elements[i];
        }
        elements = newArr;
        return element;
    }

    //查看堆疊頂元素
    public int peek() {
        return elements[elements.length - 1];
    }

    //判斷堆疊是否為空
    public boolean is_empty() {
        return elements.length == 0;
    }

    //查看堆疊的元素個數
    public int size() {
        return elements.length;
    }
}

• 頂點類

public class Vertex {

    private String value;
    public boolean visited; //訪問狀態

    public Vertex(String value) {
        super();
        this.value = value;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return value;
    }
}

• 圖類

import mystack.MyStack;

public class Graph {

    private Vertex[] vertex; //頂點陣列
    private int currentSize; //默認頂點位置
    public int[][] adjMat; //鄰接表
    private MyStack stack = new MyStack(); //堆疊
    private int currentIndex; //當前遍歷的下標

    public Graph(int size) {
        vertex = new Vertex[size];
        adjMat = new int[size][size];
    }

    //向圖中加入頂點
    public void addVertex(Vertex v) {
        vertex[currentSize++] = v;
    }

    //添加邊
    public void addEdge(String v1, String v2) {
        //找出兩個點的下標
        int index1 = 0;
        for (int i = 0; i < vertex.length; i++) {
            if (vertex[i].getValue().equals(v1)) {
                index1 = i;
                break;
            }
        }
        int index2 = 0;
        for (int i = 0; i < vertex.length; i++) {
            if (vertex[i].getValue().equals(v2)) {
                index2 = i;
                break;
            }
        }
        //表示兩個點互通
        adjMat[index1][index2] = 1;
        adjMat[index2][index1] = 1;
    }

    //深度優先搜索
    public void dfs() {
        //把第0個頂點標記為已訪問狀態
        vertex[0].visited = true;
        //把第0個的下標放入堆疊中
        stack.push(0);
        //列印頂點值
        System.out.println(vertex[0].getValue());
        //遍歷
        out:
        while (!stack.is_empty()) {
            for (int i = currentIndex + 1; i < vertex.length; i++) {
                //如果和下一個遍歷的元素是通的
                if (adjMat[currentIndex][i] == 1 && vertex[i].visited == false) {
                    //把下一個元素壓入堆疊中
                    stack.push(i);
                    vertex[i].visited = true;
                    System.out.println(vertex[i].getValue());
                    continue out;
                }
            }
            //彈出堆疊頂元素（往后退）
            stack.pop();
            //修改當前位置為堆疊頂元素的位置
            if (!stack.is_empty()) {
                currentIndex = stack.peek();
            }
        }
    }
}

• 測驗類

import java.util.Arrays;

public class Demo {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("A");
        Vertex v2 = new Vertex("B");
        Vertex v3 = new Vertex("C");
        Vertex v4 = new Vertex("D");
        Vertex v5 = new Vertex("E");
        Graph g = new Graph(5);
        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        g.addVertex(v4);
        g.addVertex(v5);

        //增加邊
        g.addEdge("A", "B");
        g.addEdge("A", "C");
        g.addEdge("A", "E");
        g.addEdge("C", "E");
        g.addEdge("C", "D");

        for (int[] a : g.adjMat) {
            System.out.println(Arrays.toString(a));
        }

        //深度優先遍歷
        g.dfs();
//        A
//        B
//        C
//        E
//        D
    }
}

第11章 冒泡排序（含改進版）

11.1 冒泡排序概念

冒泡排序（Bubble Sort）是一種簡單的排序演算法，它重復地遍歷要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來，遍歷數列的作業是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成，這個演算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端，

運行流程：

• 比較相鄰的元素，如果第一個比第二個大（升序），就交換他們兩個，
• 對每一對相鄰元素作同樣的作業，從開始第一對到結尾的最后一對，這步做完后，最后的元素會是最大的數，
• 針對所有的元素重復以上的步驟，除了最后一個，
• 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，

動圖實作：

11.2 代碼實作

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        bubbleSort(arr);
//        [4, 5, 3, 2, 1, 6]
//        [4, 3, 2, 1, 5, 6]
//        [3, 2, 1, 4, 5, 6]
//        [2, 1, 3, 4, 5, 6]
//        [1, 2, 3, 4, 5, 6]
    }

    //冒泡排序，共需要比較length-1輪
    public static void bubbleSort(int[] arr) {
        //控制一共比較多少輪
        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;
                }
            }
            //列印每次排序后的結果
            System.out.println(Arrays.toString(arr)); 
        }
    }
}

11.3 時間復雜度

• 最優時間復雜度：O(n) （表示遍歷一次發現沒有任何可以交換的元素，排序結束，）
• 最壞時間復雜度：O(n^2)
• 穩定性：穩定

排序分析：待排陣列中一共有6個數，第一輪排序時進行了5次比較，第二輪排序時進行了4比較，依次類推，最后一輪進行了1次比較，

陣列元素總數為N時，則一共需要的比較次數為：(N-1)+ (N-2)+ (N-3)+ ...1=N*(N-1)/2

演算法約做了N^2/2次比較，因為只有在前面的元素比后面的元素大時才交換資料，所以交換的次數少于比較的次數，如果資料是隨機的，大概有一半資料需要交換，則交換的次數為N^2/4（不過在最壞情況下，即初始資料逆序時，每次比較都需要交換），

交換和比較的操作次數都與 N^2 成正比，由于在大O表示法中，常數忽略不計，冒泡排序的時間復雜度為O(N^2)，

O(N2)的時間復雜度是一個比較糟糕的結果，尤其在資料量很大的情況下，所以冒泡排序通常不會用于實際應用，

11.4 代碼改進

傳統的冒泡演算法每次排序只確定了最大值，我們可以在每次回圈之中進行正反兩次冒泡，分別找到最大值和最小值，如此可使排序的輪數減少一半

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        bubbleSort(arr);
//        [1, 4, 5, 3, 2, 6]
//        [1, 2, 4, 3, 5, 6]
//        [1, 2, 3, 4, 5, 6]
    }

    //冒泡排序改進
    public static void bubbleSort(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            //正向冒泡，確定最大值
            for (int i = left; i < right; ++i) {
                //如果前一位大于后一位，交換位置
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
            --right;

            //反向冒泡，確定最小值
            for (int j = right; j > left; --j) {
                //如果前一位大于后一位，交換位置
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
            ++left;
            
            System.out.println(Arrays.toString(arr));
        }
    }
}

第12章 選擇排序（含改進版）

12.1 選擇排序概念

選擇排序（Selection sort）是一種簡單直觀的排序演算法，它的作業原理如下，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾，以此類推，直到所有元素均排序完畢，

選擇排序的主要優點與資料移動有關，如果某個元素位于正確的最終位置上，則它不會被移動，選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換，在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬于非常好的一種

動圖展示：

12.2 代碼實作

import java.util.Arrays;

public class seletsort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        selectSort(arr);
//        [1, 5, 6, 3, 2, 4]
//        [1, 2, 6, 3, 5, 4]
//        [1, 2, 3, 6, 5, 4]
//        [1, 2, 3, 4, 5, 6]
//        [1, 2, 3, 4, 5, 6]
//        [1, 2, 3, 4, 5, 6]
    }

    //選擇排序
    public static void selectSort(int[] arr) {
        //遍歷所有的數
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            //把當前遍歷的數和后面所有的數依次進行比較，并記錄最小的數的下標
            for (int j = i + 1; j < arr.length; j++) {
                //如果后面比較的數比記錄的最小的數小
                if (arr[minIndex] > arr[j]) {
                    //記錄最小的那個數的下標
                    minIndex = j;
                }
            }
            //如果發現了更小的元素，與第一個元素交換位置（第一個不是最小的元素）
            if (i != minIndex) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
            //列印每次排序后的結果
            System.out.println(Arrays.toString(arr));
        }
    }
}

12.3 時間復雜度

• 最優時間復雜度：O(n^2)
• 最壞時間復雜度：O(n^2)
• 穩定性：不穩定（考慮升序每次選擇最大的情況）

選擇排序與冒泡排序一樣，需要進行N*(N-1)/2次比較，但是只需要N次交換，當N很大時，交換次數的時間影響力更大，所以選擇排序的時間復雜度為O(N^2)，

雖然選擇排序與冒泡排序在時間復雜度屬于同一量級，但是毫無疑問選擇排序的效率更高，因為它的交換操作次數更少，而且在交換操作比比較操作的時間級大得多時，選擇排序的速度是相當快的，

12.4 代碼改進

傳統的選擇排序每次只確定最小值，根據改進冒泡演算法的經驗，我們可以對排序演算法進行如下改進：每趟排序確定兩個最值——最大值與最小值，這樣就可以將排序趟數縮減一半

改進后代碼如下：

import java.util.Arrays;

public class seletsort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        selectSort(arr);
//        [1, 5, 4, 3, 2, 6]
//        [1, 2, 4, 3, 5, 6]
//        [1, 2, 3, 4, 5, 6]

    }

    //選擇排序改進
    public static void selectSort(int[] arr) {
        int minIndex; // 存盤最小元素的小標
        int maxIndex; // 存盤最大元素的小標

        for (int i = 0; i < arr.length / 2; i++) {
            minIndex = i;
            maxIndex = i;
            //每完成一輪排序，就確定了兩個最值，下一輪排序時比較范圍減少兩個元素
            for (int j = i + 1; j <= arr.length - 1 - i; j++) {
                //如果待排陣列中的某個元素比當前元素小，minIndex指向該元素的下標
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                    continue;
                }
                //如果待排陣列中的某個元素比當前元素大，maxIndex指向該元素的下標
                else if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }

            //如果發現了更小的元素，與第一個元素交換位置（第一個不是最小的元素）
            if (i != minIndex) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;

                // 原來的第一個元素已經與下標為minIndex的元素交換了位置
                // 所以現在arr[minIndex]存放的才是之前第一個元素中的資料
                // 如果之前maxIndex指向的是第一個元素，那么需要將maxIndex重新指向arr[minIndex]
                if (maxIndex == i) {
                    maxIndex = minIndex;
                }
            }

            // 如果發現了更大的元素，與最后一個元素交換位置
            if (arr.length - 1 - i != maxIndex) {
                int temp = arr[arr.length - 1 - i];
                arr[arr.length - 1 - i] = arr[maxIndex];
                arr[maxIndex] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
    }
}

第13章 選擇排序（含改進版）

13.1 插入排序概念

插入排序（Insertion Sort）是一種簡單直觀的排序演算法，它的作業原理是通過構建有序序列，對于未排序資料，在已排序序列中從后向前掃描，找到相應位置并插入，插入排序在實作上，在從后向前掃描程序中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間

動圖展示：

13.2 代碼實作

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        insertSort(arr);
//        [4, 5, 6, 3, 2, 1]
//        [4, 5, 6, 3, 2, 1]
//        [3, 4, 5, 6, 2, 1]
//        [2, 3, 4, 5, 6, 1]
//        [1, 2, 3, 4, 5, 6]
    }

    //插入排序
    public static void insertSort(int[] arr) {
        //遍歷所有的數字，從第二個開始和前一個比較
        for (int i = 1; i < arr.length; i++) {
            //如果當前數字比前一個數字小
            if (arr[i] < arr[i - 1]) {
                //把當前遍歷的數字存起來
                int temp = arr[i];
                //遍歷當前數字前面的數字
                int j;
                for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
                    //把前一個數賦給后一個數
                    arr[j + 1] = arr[j];
                }
                //把臨時變數（外層for回圈的當前元素）賦給不滿足條件的后一個元素
                arr[j + 1] = temp;
            }
            //列印每次排序后的結果
            System.out.println(Arrays.toString(arr));
        }
    }
}

13.3 時間復雜度

• 最優時間復雜度：O(n) （升序排列，序列已經處于升序狀態）
• 最壞時間復雜度：O(n^2)
• 穩定性：穩定

在第一趟排序中，插入排序最多比較一次，第二趟最多比較兩次，依次類推，最后一趟最多比較N-1次，因此有：1+2+3+...+N-1 = N*N(N-1)/2

因為在每趟排序發現插入點之前，平均來說，只有全體資料項的一半進行比較，我們除以2得到：N*N(N-1)/4

復制的次數大致等于比較的次數，然而，一次復制與一次比較的時間消耗不同，所以相對于隨機資料，這個演算法比冒泡排序快一倍，比選擇排序略快，

與冒泡排序、選擇排序一樣，插入排序的時間復雜度仍然為O(N^2)，這三者被稱為簡單排序或者基本排序，三者都是穩定的排序演算法，

如果待排序陣列基本有序時，插入排序的效率會更高

13.4 代碼改進

在插入某個元素之前需要先確定該元素在有序陣列中的位置，上例的做法是對有序陣列中的元素逐個掃描，當資料量比較大的時候，這是一個很耗時間的程序，可以采用二分查找法改進，這種排序也被稱為二分插入排序

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        insertSort(arr);
//        [4, 5, 6, 3, 2, 1]
//        [4, 5, 6, 3, 2, 1]
//        [3, 4, 5, 6, 2, 1]
//        [2, 3, 4, 5, 6, 1]
//        [1, 2, 3, 4, 5, 6]
    }

    //二分插入排序
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            //如果新記錄小于有序序列的最大元素，則用二分法找出新紀錄在有序序列中的位置
            if (arr[i] < arr[i - 1]) {
                int temp = arr[i]; //定義temp存盤所要插入的數
                int left = 0; //最左邊的數，從str[0]開始
                int right = i - 1; //最右邊位，所要插入那個數的前一位

                while (left <= right) {
                    int middle = (left + right) / 2;   //mid中間位
                    //如果值比中間值大,讓left右移到中間下標+1
                    if (arr[middle] < temp) {
                        left = middle + 1;
                    }
                    //如果值比中間值小，讓right左移到中間下標-1
                    else {
                        right = middle - 1;
                    }
                }
                //以左下標為標準，在左位置前插入該資料，左及左后邊全部后移
                for (int j = i; j > left; j--) {
                    arr[j] = arr[j - 1];
                }
                arr[left] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
    }
}

第14章 歸并排序

14.1 歸并排序概念

歸并排序（Merge Sort）是采用分治法的一個非常典型的應用，歸并排序的思想就是先遞回分解陣列，再合并陣列，

將陣列分解最小之后，然后合并兩個有序陣列，基本思路是比較兩個陣列的最前面的數，誰小就先取誰，取了后相應的指標就往后移一位，然后再比較，直至一個陣列為空，最后把另一個陣列的剩余部分復制過來即可，

動圖展示：

• 動圖1

• 動圖2

14.2 代碼實作

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {6, 5, 3, 1, 8, 7, 2, 4};
        mergeSort(arr, 0, arr.length - 1);
//        [5, 6, 3, 1, 8, 7, 2, 4]
//        [5, 6, 1, 3, 8, 7, 2, 4]
//        [1, 3, 5, 6, 8, 7, 2, 4]
//        [1, 3, 5, 6, 7, 8, 2, 4]
//        [1, 3, 5, 6, 7, 8, 2, 4]
//        [1, 3, 5, 6, 2, 4, 7, 8]
//        [1, 2, 3, 4, 5, 6, 7, 8]
    }

    //歸并排序
    public static void mergeSort(int[] arr, int low, int high) {
        int middle = (high + low) / 2;
        //遞回結束
        if (low < high) {
            //處理左邊
            mergeSort(arr, low, middle);
            //處理右邊
            mergeSort(arr, middle + 1, high);
            //歸并
            merge(arr, low, middle, high);
        }
    }

    //歸并操作
    //low:開始位置，middle：分割位置，high：結束位置
    public static void merge(int[] arr, int low, int middle, int high) {
        //用于存盤歸并后的臨時陣列
        int[] temp = new int[high - low + 1];
        //記錄第一個陣列中需要遍歷的下標
        int i = low;
        //記錄第二個陣列中需要遍歷的下標
        int j = middle + 1;
        //用于記錄在臨時陣列中存放的下標
        int index = 0;
        //遍歷兩個陣列取出小的數字，放入臨時陣列中
        while (i <= middle && j <= high) {
            //第一個陣列的資料更小
            if (arr[i] <= arr[j]) {
                //把小的陣列放入臨時陣列中
                temp[index] = arr[i];
                //讓下標向后移一位
                i++;
            } else {
                temp[index] = arr[j];
                j++;
            }
            //每存入一個數字后，臨時陣列下標后移
            index++;
        }

        //上面的回圈退出后，把剩余的元素依次填入到temp中,以下兩個while只有一個會執行
        //前面一個陣列有多余資料
        while (i <= middle) {
            temp[index] = arr[i];
            i++;
            index++;
        }
        //后面一個陣列有多余資料
        while (j <= high) {
            temp[index] = arr[j];
            j++;
            index++;
        }
        //把臨時陣列中的資料重新存入原陣列
        for (int k = 0; k < temp.length; k++) {
            arr[k + low] = temp[k];
        }

        //列印每次排序后的結果
        System.out.println(Arrays.toString(arr));
    }
}

14.3 時間復雜度

最優時間復雜度：O(nlogn)

最壞時間復雜度：O(nlogn)

穩定性：穩定

第15章 快速排序

15.1 快速排序概念

快速排序（Quick Sort），又稱劃分交換排序（partition-exchange sort），通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然后再按此方法對這兩部分資料分別進行快速排序，整個排序程序可以遞回進行，以此達到整個資料變成有序序列，

排序步驟：

• 1、 從數列中挑出一個元素，稱為"基準"（pivot），通常選擇第一個元素
• 2、重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊），在這個磁區結束之后，該基準就處于數列的中間位置，這個稱為磁區（partition）操作，
• 3、遞回地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序，

遞回的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了，雖然一直遞回下去，但是這個演算法總會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去，

動圖展示：

• 動圖1

• 動圖2：

靜圖分析：

15.2 代碼實作

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {30, 40, 60, 10, 20, 50};
        quickSort(arr, 0, arr.length - 1);
//        [20, 10, 30, 60, 40, 50]
//        [10, 20, 30, 60, 40, 50]
//        [10, 20, 30, 60, 40, 50]
//        [10, 20, 30, 50, 40, 60]
//        [10, 20, 30, 40, 50, 60]
//        [10, 20, 30, 40, 50, 60]
    }

    //快速排序
    public static void quickSort(int[] arr, int start, int end) {
        //遞回結束的標記
        if (start < end) {
            //把陣列中第0個數字作為標準數
            int stard = arr[start];
            //記錄需要排序的下標
            int low = start;
            int high = end;
            //回圈找比標準數大的數和標準數小的數
            while (low < high) {
                //如果右邊數字比標準數大，下標向前移
                while (low < high && arr[high] >= stard) {
                    high--;
                }
                //右邊數字比標準數小，使用右邊的數替換左邊的數
                arr[low] = arr[high];
                //如果左邊數字比標準數小
                while (low < high && arr[low] <= stard) {
                    low++;
                }
                //左邊數字比標準數大，使用左邊的數替換右邊的數
                arr[high] = arr[low];
            }
            //把標準數賦給低所在的位置的元素
            arr[low] = stard;
            //列印每次排序后的結果
            System.out.println(Arrays.toString(arr));

            //遞回處理所有標準數左邊的數字（含標準數）
            quickSort(arr, start, low);
            //遞回處理所有標準數右邊的數字
            quickSort(arr, low + 1, end);
        }
    }
}

15.3 時間復雜度

• 最優時間復雜度：O(nlogn)
• 最壞時間復雜度：O(n^2)
• 穩定性：不穩定

從一開始快速排序平均需要花費O(n log n)時間的描述并不明顯，但是不難觀察到的是磁區運算，陣列的元素都會在每次回圈中走訪過一次，使用O(n)的時間，在使用結合（concatenation）的版本中，這項運算也是O(n)，

在最好的情況，每次我們運行一次磁區，我們會把一個數列分為兩個幾近相等的片段，這個意思就是每次遞回呼叫處理一半大小的數列，因此，在到達大小為一的數列前，我們只要作log n次嵌套的呼叫，這個意思就是呼叫樹的深度是O(log n)，但是在同一層次結構的兩個程式呼叫中，不會處理到原來數列的相同部分；因此，程式呼叫的每一層次結構總共全部僅需要O(n)的時間（每個呼叫有某些共同的額外耗費，但是因為在每一層次結構僅僅只有O(n)個呼叫，這些被歸納在O(n)系數中），結果是這個演算法僅需使用O(n log n)時間，

第16章 希爾排序

16.1 希爾排序概念

希爾排序（Shell Sort）是插入排序的一種，也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本，希爾排序是非穩定排序演算法，該方法因DL．Shell于1959年提出而得名， 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，演算法便終止

動圖展示：

靜圖分析：

16.2 代碼實作

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort(arr);
//        [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
//        [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
//        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    //希爾排序
    public static void shellSort(int[] arr) {
        //遍歷所有的步長
        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
            //遍歷所有的元素
            for (int i = gap; i < arr.length; i++) {
                //遍歷本組中所有元素
                for (int j = i - gap; j >= 0; j -= gap) {
                    //如果當前元素大于加上步長后的那個元素
                    if (arr[j] > arr[j + gap]) {
                        int temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            //列印每次排序后的結果
            System.out.println(Arrays.toString(arr));
        }
    }
}

16.3 時間復雜度

• 最優時間復雜度：根據步長序列的不同而不同
• 最壞時間復雜度：O(n^2)
• 穩定性：不穩定

希爾排序不像其他時間復雜度為O(N log2N)的排序演算法那么快，但是比選擇排序和插入排序這種時間復雜度為O(N2)的排序演算法還是要快得多，而且非常容易實作，它在最壞情況下的執行效率和在平均情況下的執行效率相比不會降低多少，而快速排序除非采取特殊措施，否則在最壞情況下的執行效率變得非常差，

迄今為止，還無法從理論上精準地分析希爾排序的效率，有各種各樣基于試驗的評估，估計它的時間級介于O(N^3/2)與 O(N^7/6)之間，我們可以認為希爾排序的平均時間復雜度為o(n^1.3)，

第17章 堆排序

17.1 堆排序概述

堆排序（Heap Sort）是指利用堆這種資料結構所設計的一種排序演算法，堆積是一個近似完全二叉樹的結構，每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆，如下圖：

同時，我們對堆中的結點按層進行編號，將這種邏輯結構映射到陣列中就是下面這個樣子
該陣列從邏輯上講就是一個堆結構，我們用簡單的公式來描述一下堆的定義就是：

• 大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

• 小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

步驟一 構造初始堆，將給定無序序列構造成一個大頂堆（一般升序采用大頂堆，降序采用小頂堆)

1）假設給定無序序列結構如下

2）此時我們從最后一個非葉子結點開始（葉結點自然不用調整，第一個非葉子結點 arr.length/2-1=5/2-1=1，也就是下面的6結點），從左至右，從下至上進行調整

3）找到第二個非葉節點4，由于[4,9,8]中9元素最大，4和9交換
4）這時，交換導致了子根[4,5,6]結構混亂，繼續調整，[4,5,6]中6最大，交換4和6，
此時，我們就將一個無需序列構造成了一個大頂堆

步驟二 將堆頂元素與末尾元素進行交換，使末尾元素最大，然后繼續調整堆，再將堆頂元素與末尾元素交換，得到第二大元素，如此反復進行交換、重建、交換

1）將堆頂元素9和末尾元素4進行交換，9就不用繼續排序了

2）重新調整結構，使其繼續構建大頂堆（9除外）

3）再將堆頂元素8與末尾元素5進行交換，得到第二大元素8.

步驟三 后續程序，繼續進行調整，交換，如此反復進行，最終使得整個序列有序

排序思路：

• 將無需序列構建成一個堆，根據升序降序需求選擇大頂堆或小頂堆;

• 將堆頂元素與末尾元素交換，將最大元素"沉"到陣列末端;

• 重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，反復執行調整+交換步驟，直到整個序列有序

動圖展示：

17.2 代碼實作

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        heapSort(arr);
//        [4, 6, 8, 5, 9]
//        [4, 9, 8, 5, 6]
//        [4, 9, 8, 5, 6]
//        [9, 6, 8, 5, 4]
//        [9, 6, 8, 5, 4]
//        [9, 6, 8, 5, 4]
//        [8, 6, 4, 5, 9]
//        [8, 6, 4, 5, 9]
//        [6, 5, 4, 8, 9]
//        [6, 5, 4, 8, 9]
//        [5, 4, 6, 8, 9]
//        [5, 4, 6, 8, 9]
//        [4, 5, 6, 8, 9]
    }

    //堆排序
    public static void heapSort(int[] arr) {
        //開始位置是最后一個非葉子節點（最后一個節點的父節點）
        int start = (arr.length - 1) / 2;
        //回圈調整為大頂堆
        for (int i = start; i >= 0; i--) {
            maxHeap(arr, arr.length, i);
        }
        //先把陣列中第0個和堆中最后一個交換位置
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //再把前面的處理為大頂堆
            maxHeap(arr, i, 0);
        }
    }

    //陣列轉大頂堆,size:調整多少（從最后一個向前減），index:調整哪一個（最后一個非葉子節點）
    public static void maxHeap(int[] arr, int size, int index) {
        //左子節點
        int leftNode = 2 * index + 1;
        //右子節點
        int rightNode = 2 * index + 2;
        //先設當前為最大節點
        int max = index;
        //和兩個子節點分別對比，找出最大的節點
        if (leftNode < size && arr[leftNode] > arr[max]) {
            max = leftNode;
        }
        if (rightNode < size && arr[rightNode] > arr[max]) {
            max = rightNode;
        }

        //交換位置
        if (max != index) {
            int temp = arr[index];
            arr[index] = arr[max];
            arr[max] = temp;
            //交換位置后，可能會破壞之前排好的堆，所以之間排好的堆需要重新調整
            maxHeap(arr, size, max);
        }
        //列印每次排序后的結果
        System.out.println(Arrays.toString(arr));
    }
}

17.3 時間復雜度

• 最優時間復雜度：o(nlogn)
• 最壞時間復雜度：o(nlogn)
• 穩定性：不穩定

它的運行時間主要是消耗在初始構建堆和在重建堆時的反復篩選上，

在構建堆的程序中，因為我們是完全二叉樹從最下層最右邊的非終端結點開始構建，將它與其孩子進行比較和若有必要的互換，對于每個非終端結點來說，其實最多進行兩次比較和互換操作，因此整個構建堆的時間復雜度為O(n)，

在正式排序時，第i次取堆頂記錄重建堆需要用O(logi)的時間（完全二叉樹的某個結點到根結點的距離為log2i＋1），并且需要取n-1次堆頂記錄，因此，重建堆的時間復雜度為O(nlogn)，

所以總體來說，堆排序的時間復雜度為O(nlogn)，由于堆排序對原始記錄的排序狀態并不敏感，因此它無論是最好、最壞和平均時間復雜度均為O(nlogn)，這在性能上顯然要遠遠好過于冒泡、簡單選擇、直接插入的O(n2)的時間復雜度了，

空間復雜度上，它只有一個用來交換的暫存單元，也非常的不錯，不過由于記錄的比較與交換是跳躍式進行，因此堆排序是一種不穩定的排序方法，

第18章 計數排序

18.1 計數排序概念

計數排序（Counting Sort）不是基于比較的排序演算法，其核心在于將輸入的資料值轉化為鍵存盤在額外開辟的陣列空間中， 作為一種線性時間復雜度的排序，計數排序要求輸入的資料必須是有確定范圍的整數，

排序步驟：

• 找出待排序的陣列中最大和最小的元素；
• 統計陣列中每個值為i的元素出現的次數，存入陣列C的第i項；
• 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；
• 反向填充目標陣列：將每個元素i放在新陣列的第C(i)項，每放一個元素就將C(i)減去1

動圖展示：

18.2 代碼實作

import java.util.Arrays;

public class CountingSort {
    public static void main(String[] args) {
        //測驗
        int[] arr = {1, 4, 6, 7, 5, 4, 3, 2, 1, 4, 5, 10, 9, 10, 3};
        sortCount(arr);
        System.out.println(Arrays.toString(arr));
//        [1, 1, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 9, 10, 10]
    }

    //計數排序
    public static void sortCount(int[] arr) {
        //一：求取最大值和最小值，計算中間陣列的長度：
        int max = arr[0];
        int min = arr[0];
        int len = arr.length;
        for (int i : arr) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
        //二、有了最大值和最小值能夠確定中間陣列的長度（中間陣列是用來記錄原始資料中每個值出現的頻率）
        int[] temp = new int[max - min + 1];
        //三.回圈遍歷舊陣列計數排序: 就是統計原始陣列值出現的頻率到中間陣列temp中
        for (int i = 0; i < len; i++) {
            temp[arr[i] - min] += 1;
        }
        //四、遍歷輸出
        //先回圈每一個元素  在計數排序器的下標中
        for (int i = 0, index = 0; i < temp.length; i++) {
            int item = temp[i];
            回圈出現的次數
            while (item-- != 0) {
                //以為原來減少了min現在加上min，值就變成了原來的值
                arr[index++] = i + min;
            }
        }
    }
}

18.3 時間復雜度

• 最優時間復雜度：o(n+k)
• 最壞時間復雜度：o(n+k)
• 穩定性：不穩定

計數排序是一個穩定的排序演算法，當輸入的元素是 n 個 0到 k 之間的整數時，時間復雜度是O(n+k)，空間復雜度也是O(n+k)，其排序速度快于任何比較排序演算法，當k不是很大并且序列比較集中時，計數排序是一個很有效的排序演算法

第19章 桶排序

19.1 桶排序概念

桶排序 （Bucket sort）或所謂的箱排序，是一個排序演算法，作業的原理是將陣列分到有限數量的桶里，每個桶再個別排序（有可能再使用別的排序演算法或是以遞回方式繼續使用桶排序進行排序），最后依次把各個桶中的記錄列出來記得到有序序列，桶排序是鴿巢排序的一種歸納結果，當要被排序的陣列內的數值是均勻分配的時候，桶排序使用線性時間 o(n)，但桶排序并不是比較排序，他不受到O(n log n)下限的影響，

排序步驟：

• 設定一個定量的陣列當作空桶；
• 遍歷輸入資料，并且把資料一個一個放到對應的桶里去；
• 對每個不是空的桶進行排序；
• 從不是空的桶里把排好序的資料拼接起來

動圖展示：

靜圖展示：

19.2 代碼實作

package sort;

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {

    public static void main(String[] args) {
        int[] arr = {29, 25, 3, 49, 9, 37, 21, 43};
        bucketSort(arr);
        //分桶后結果為:[[3, 9], [], [21, 25], [29], [37], [43, 49]]
    }

    public static void bucketSort(int[] arr) {
        // 大的當小的，小的當大的
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        // 找出最小最大值
        for (int i=0, len=arr.length; i<len; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        // 創建初始的桶
        int bucketNum = (max - min)/arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);

        // 這一步是不可缺少的，上面的初始化只初始化了一維串列，二維串列需額外初始化
        for (int i=0; i<bucketNum; i++) {
            bucketArr.add(new ArrayList<>());
        }
        for (int i=0, len=arr.length; i<len; i++) {
            int num = (arr[i] - min)/arr.length;    //相同的商在同一個桶中
            bucketArr.get(num).add(arr[i]);     //根據商的不同，放入不同的桶
        }

        for (int i=0; i<bucketArr.size(); i++) {    //同一桶內，自己排序
            Collections.sort(bucketArr.get(i));
        }
        System.out.println("分桶后結果為:"+bucketArr.toString());
    }
}

19.3 時間復雜度

• 最優時間復雜度：o(n)
• 最壞時間復雜度：o(n^2)
• 穩定性：穩定

對于桶排序來說，分配程序的時間是O(n)；收集程序的時間為O(k) （采用鏈表來存盤輸入的待排序記錄），因此，桶排序的時間為O(n+k)，若桶個數m的數量級為O(n)，則桶排序的時間是線性的，最優即O(n)，

前面說的幾大排序演算法 ，大部分時間復雜度都是O(n2)，也有部分排序演算法時間復雜度是O(nlogn)，而桶式排序卻能實作O(n)的時間復雜度，但桶排序的缺點是：首先是空間復雜度比較高，需要的額外開銷大，排序有兩個陣列的空間開銷，一個存放待排序陣列，一個就是所謂的桶，比如待排序值是從0到m-1，那就需要m個桶，這個桶陣列就要至少m個空間，其次待排序的元素都要在一定的范圍內等等，

第20章 基數排序

20.1 基數排序概念

基數排序（Radix Sort）是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位，有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序，最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前

排序步驟：

• 取得陣列中的最大數，并取得位數；
• arr為原始陣列，從最低位開始取每個位組成radix陣列；
• 對radix進行計數排序（利用計數排序適用于小范圍數的特點）

動圖展示：

靜圖分析：

20.2 代碼實作

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {4, 32, 457, 16, 28, 64};
        radixSort(arr);
//        [32, 4, 64, 16, 457, 28]
//        [4, 16, 28, 32, 457, 64]
//        [4, 16, 28, 32, 64, 457]
    }

    //基數排序
    public static void radixSort(int[] arr) {
        // 定義臨時二維陣串列示十個桶
        int[][] temp = new int[10][arr.length];
        // 定義一個一維陣列，用于記錄在temp中相應的陣列中存放數字的數量
        int[] counts = new int[10];
        //存陣列中最大的數字
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //計算最大數字是幾位數（才能知道排序次數）
        int maxLength = (max + "").length();
        //根據最大長度的數決定比較的次數
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            //把每一個數字分別計算余數
            for (int j = 0; j < arr.length; j++) {
                //計算余數
                int ys = arr[j] / n % 10;
                //把當前遍歷的資料放入指定的陣列中
                temp[ys][counts[ys]] = arr[j];
                //記錄數量
                counts[ys]++;
            }
            //記錄取的元素需要放的位置
            int index = 0;
            //把數字取出來
            for (int k = 0; k < counts.length; k++) {
                //記錄數量的陣列中，當前余數記錄的數量不為0才取
                if (counts[k] != 0) {
                    //回圈取出元素
                    for (int l = 0; l < counts[k]; l++) {
                        //取出元素
                        arr[index] = temp[k][l];
                        //記錄下一個位置
                        index++;
                    }
                    //把數量置為0
                    counts[k] = 0;
                }
            }
            //列印每次排序后的結果
            System.out.println(Arrays.toString(arr));
        }
    }
}

20.3 時間復雜度

• 最優時間復雜度：O(n^k)
• 最壞時間復雜度：O(n^k)
• 穩定性：穩定

初看起來，基數排序的執行效率似乎好的讓人無法相信，所有要做的只是把原始資料項從陣列復制到鏈表，然后再復制回去，如果有10個資料項，則有20次復制，對每一位重復一次這個程序，假設對5位的數字排序，就需要20 * 5=100次復制，

*如果有100個資料項，那么就有200 * 5=1000次復制，復制的次數與資料項的個數成正比，即O(n)，這是我們看到的效率最高的排序演算法，

不幸的是，資料項越多，就需要更長的關鍵字，如果資料項增加10倍，那么關鍵字必須增加一位（多一輪排序），復制的次數和資料項的個數與關鍵字長度成正比，可以認為關鍵字長度是N的對數，因此在大多數情況下，基數排序的執行效率倒退為O(N*logN)，和快速排序差不多