溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家分享的是有關Java數據結構與算法的示例分析的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。
算法是程序的靈魂，優秀的程序可以在海量數據計算時，依然保持高速計算
數據結構和算法的關系：
程序 = 數據結構 + 算法
數據結構是算法的基礎, 換言之，想要學好算法，需要把數據結構學到位。
數據結構和算法學習大綱
數據結構可以簡單的理解為數據與數據之間所存在的一些關系，數據的結構分為數據的存儲結構和數據的邏輯結構。
集合結構：數據元素同屬于一個集合，他們之間是并列關系，無其他的關系；可以理解為中學時期學習的集合，在一個范圍之內，有很多的元素，元素間沒有什么關系
線性結構：元素之間存在著一對一的關系；可以理解為每個學生對應著一個學號，學號與姓名就是線性結構
樹形結構：元素之間存在著一對多的關系，可以簡單理解為家庭族譜一樣，一代接一代
圖形結構：元素之間存在多對多的關系，每一個元素可能對應著多個元素，或被多個元素對應，網狀圖
順序存儲結構：就是將數據進行連續的存儲，我們可以將它比喻成學校食堂打飯排隊一樣，一個接著一個；
鏈式存儲結構：不是按照順序存儲的，后一個進來的數只需要將他的地址告訴前一個節點，前一個節點中就存放了它后面那個數的地址，所以最后一個數的存儲地址就是為null；可以將這種結構比喻成商場吃飯叫號，上面的號碼比喻成是地址，你可以之后后面的地址是什么，上面的其他內容就是該節點的內容；
區別：
順序存儲的特點是查詢快，插入或者刪除慢
鏈式存儲的特點是查詢慢，插入或者刪除快
同一問題不同解決方法
通過時間和空間復雜度判斷算法的優劣
算法沒有最好的，只有最合適的，學習算法是為了積累學習思路，掌握學習思路，并不是為了解決某問題去記住某種算法；對于時間復雜度與空間復雜度，現在大多數開發情況下，我們都在使用以空間換時間，耗費更多的內存，來保證擁有更快的速度。
各排序算法復雜度及穩定性：
對于算法進行特別具體的細致分析雖然很好，但在實踐中的實際價值有限。對于算法的時間性質和空間性質，最重要的是其數量級和趨勢，這些是分析算法效率的主要部分。而計量算法基本操作數量的規模函數中那些常量因子可以忽略不計。例如，可以認為 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開發的，基本上都是服務器開發, 一般不存在這樣的問題。
數組是一種線性表數據結構，它用一組連續的內存空間，來存儲一組具有相同類型的數據。這里我們要抽取出三個跟數組相關的關鍵詞：線性表，連續內存空間，相同數據類型；數組具有連續的內存空間，存儲相同類型的數據，正是該特性使得數組具有一個特性：隨機訪問。但是有利有弊，這個特性雖然使得訪問數組邊得非常容易，但是也使得數組插入和刪除操作會變得很低效，插入和刪除數據后為了保證連續性,要做很多數據搬遷工作。
查找數組中的方法有兩種：
線性查找：線性查找就是簡單的查找數組中的元素
二分法查找：二分法查找要求目標數組必須是有序的。
實現類：
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)）、刪除慢
實現類：
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)）
棧（stack），有些地方稱為堆棧，是一種容器，可存入數據元素、訪問元素、刪除元素，它的特點在于只能允許在容器的一端（稱為棧頂端指標，英語：top）進行加入數據（英語：push）和輸出數據（英語：pop）的運算。沒有了位置概念，保證任何時候可以訪問、刪除的元素都是此前最后存入的那個元素，確定了一種默認的訪問順序。
由于棧數據結構只允許在一端進行操作，因而按照后進先出的原理運作。
棧可以用順序表實現，也可以用鏈表實現。
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
}}隊列（Queue）是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。
隊列是一種先進先出的（First In First Out）的線性表，簡稱FIFO。允許插入的一端為隊尾，允許刪除的一端為隊頭。隊列不允許在中間部位進行操作！假設隊列是q=（a1，a2，……，an），那么a1就是隊頭元素，而an是隊尾元素。這樣我們就可以刪除時，總是從a1開始，而插入時，總是在隊列最后。這也比較符合我們通常生活中的習慣，排在第一個的優先出列，最后來的當然排在隊伍最后。
同棧一樣，隊列也可以用順序表或者鏈表實現。
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 < elements.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
}}單鏈表也叫單向鏈表，是鏈表中最簡單的一種形式，它的每個節點包含兩個域，一個信息域（元素域）和一個鏈接域。這個鏈接指向鏈表中的下一個節點，而最后一個節點的鏈接域則指向一個空值。
表元素域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
}}單鏈表的一個變形是單向循環鏈表，鏈表中最后一個節點的 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
}}在雙向鏈表中有兩個指針域，一個是指向前驅結點的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
}}線性結構中不論是數組還是鏈表，他們都存在著詬病；比如查找某個數必須從頭開始查，消耗較多的時間。使用樹結構，在插入和查找的性能上相對都會比線性結構要好
示意圖
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、森林：多個樹組成的集合
無序樹：樹中任意節點的子節點之間沒有順序關系，這種樹稱為無序樹，也稱為自由樹；
有序樹：樹中任意節點的子節點之間有順序關系，這種樹稱為有序樹；
二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹；
完全二叉樹：對于一顆二叉樹，假設其深度為d(d>1)。除了第d層外，其它各層的節點數目均已達最大值，且第d層所有節點從左向右連續地緊密排列，這樣的二叉樹被稱為完全二叉樹，其中滿二叉樹的定義是所有葉節點都在最底層的完全二叉樹;
平衡二叉樹（AVL樹）：當且僅當任何節點的兩棵子樹的高度差不大于1的二叉樹；
排序二叉樹（二叉查找樹（英語：Binary Search Tree），也稱二叉搜索樹、有序二叉樹）；
霍夫曼樹（用于信息編碼）：帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹；
B樹：一種對讀寫操作進行優化的自平衡的二叉查找樹，能夠保持數據有序，擁有多余兩個子樹。
順序存儲：將數據結構存儲在固定的數組中，然在遍歷速度上有一定的優勢，但因所占空間比較大，是非主流二叉樹。二叉樹通常以鏈式存儲。
鏈式存儲：
由于對節點的個數無法掌握，常見樹的存儲表示都轉換成二叉樹進行處理，子節點個數最多為2
1、xml，html等，那么編寫這些東西的解析器的時候，不可避免用到樹
2、路由協議就是使用了樹的算法
3、mysql數據庫索引
4、文件系統的目錄結構
5、所以很多經典的AI算法其實都是樹搜索，此外機器學習中的decision tree也是樹結構
任何一個節點的子節點數量不超過 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 時為根,除外）
滿二叉樹： 所有葉子結點都集中在二叉樹的最下面一層上，而且結點總數為：2^n-1 (n為層數 / 高度）
完全二叉樹： 所有的葉子節點都在最后一層或者倒數第二層，且最后一層葉子節點在左邊連續，倒數第二層在右邊連續（滿二叉樹也是屬于完全二叉樹）（從上往下，從左往右能挨著數滿）
創建二叉樹：首先需要一個樹的類，還需要另一個類用來存放節點，設置節點；將節點放入樹中，就形成了二叉樹；（節點中需要權值，左子樹，右子樹，并且都能對他們的值進行設置）。
樹的遍歷：
先序遍歷：根節點，左節點，右節點（如果節點有子樹，先從左往右遍歷子樹，再遍歷兄弟節點）
先序遍歷結果為：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和他的子節點被刪除了
}}
概述：順序存儲使用數組的形式實現；由于非完全二叉樹會導致數組中出現空缺，有的位置不能填上數字，所以順序存儲二叉樹通常情況下只考慮完全二叉樹
原理： 順序存儲在數組中是按照第一層第二層一次往下存儲的，遍歷方式也有先序遍歷、中序遍歷、后續遍歷
性質：
第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
}}為什么使用線索二叉樹？
當用二叉鏈表作為二叉樹的存儲結構時，可以很方便的找到某個結點的左右孩子；但一般情況下，無法直接找到該結點在某種遍歷序列中的前驅和后繼結點
原理：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
}}無序序列：
二叉排序樹圖解：
概述：二叉排序樹（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
}}平衡二叉樹（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
}}HuffmanTree因為翻譯不同所以有其他的名字：赫夫曼樹、霍夫曼樹、哈夫曼樹
赫夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和，記為WPL=（W1L1+W2L2+W3L3+…+WnLn），N個權值Wi（i=1,2,…n）構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li（i=1,2,…n）。可以證明赫夫曼樹的WPL是最小的。
路徑： 路徑是指從一個節點到另一個節點的分支序列。
路徑長度： 指從一個節點到另一個結點所經過的分支數目。 如下圖：從根節點到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
對于數組{5,29,7,8,14,23,3,11}，我們把它構造成赫夫曼樹
第一步：使用數組中所有元素創建若干個二叉樹，這些值作為節點的權值（只有一個節點）。
第二步：將這些節點按照權值的大小進行排序。
第三步：取出權值最小的兩個節點，并創建一個新的節點作為這兩個節點的父節點，這個父節點的權值為兩個子節點的權值之和。將這兩個節點分別賦給父節點的左右節點
第四步：刪除這兩個節點，將父節點添加進集合里
第五步：重復第二步到第四步，直到集合中只剩一個元素，結束循環
節點類
//接口實現排序功能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=100Process finished with exit code 0
二叉樹需要加載到內存的，如果二叉樹的節點少，沒有什么問題，但是如果二叉樹的節點很多(比如1億)， 就存在如下問題:
問題1：在構建二叉樹時，需要多次進行I/O操作(海量數據存在數據庫或文件中)，節點海量，構建二叉樹時，速度有影響.
問題2：節點海量，也會造成二叉樹的高度很大，會降低操作速度.
解決上述問題 —> 多叉樹
1、在二叉樹中，每個節點有數據項，最多有兩個子節點。如果允許每個節點可以有更多的數據項和更多的子節點，就是多叉樹（multiway tree）
2、后面我們講解的"2-3樹"，"2-3-4樹"就是多叉樹，多叉樹通過重新組織節點，減少樹的高度，能對二叉樹進行優化。
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樹的刪除也分為三種情況，與插入相反。
三種刪除情況：
1）所刪元素位于一個3節點的葉子節點上，直接刪除，不會影響樹結構（如：刪除9）
2）所刪元素位于一個2節點上，直接刪除，破壞樹結構
分為四種情況：
此節點雙親也是2節點，且擁有一個3節點的右孩子（如：刪除1）
此節點的雙親是2節點，它右孩子也是2節點（如：刪除4）
此節點的雙親是3節點（如：刪除10）
當前樹是一個滿二叉樹，降低樹高（如：刪除8）
3）所刪元素位于非葉子的分支節點。此時按樹中序遍歷得到此元素的前驅或后續元素，補位
兩種情況：
分支節點是2節點（如：刪除4）
分支節點是3節點（如：刪除12）
2-3-4樹是2-3樹的擴展，包括了 4 節點的使用，一個 4 節點包含小中大三個元素和四個孩子（或沒有孩子）
1）如果待插入的節點不是 4 節點，則直接插入即可
2）如果待插入的節點是 4 節點，則先把新節點臨時插入進去變成 5 節點，然后對 5 節點進行向上分裂、合并，5 節點分裂成兩個 2 節點（5 節點最小的元素、5 節點第二個元素）、1個 3 節點（5 節點后兩個元素），然后將分裂之后的第2個 2 節點向上合并到父節點中，然后把父節點作為插入元素之后的當前節點，重復（1）、（2）步驟，直到滿足2-3-4樹的定義性質
刪除順序使1,6,3,4,5,2,9
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樹上查找時，從根節點到關鍵字節點的路徑上涉及的節點數不超多
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，并且每一個葉子節點帶有指向下一個相鄰的葉節點指針，形成鏈表
B樹的非葉節點會存儲關鍵字及其對應的數據地址，B+樹的非葉節點只存關鍵字索引，不會存具體的數據地址，因此B+樹的一個節點相比B樹能存儲更多的索引元素，一次性讀入內存的需要查找的關鍵字也就越多，B+樹的高度更小，相對IO讀寫次數就降低了。
B樹的查詢效率并不穩定，最好的情況只查詢一次（根節點），最壞情況是查找到葉子節點，而B+樹由于非葉節點不存數據地址，而只是葉子節點中關鍵字的索引。所有查詢都要查找到葉子節點才算命中，查詢效率比較穩定。這對于sql語句的優化是非常有幫助的。
B+樹所有葉子節點形成有序鏈表，只需要去遍歷葉子節點就可以實現整棵樹的遍歷。方便數據的范圍查詢，而B樹不支持這樣的操作或者說效率太低。
現代數據庫和文件系統的索引表大部分是使用B+樹來實現的，但并不是全部
圖（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)。
如下圖
圖結構的常見的兩個存儲方式： 鄰接矩陣 、鄰接表
圖中的 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 相關聯
從圖中某一頂點出發訪遍圖中其余頂點，且使每一個頂點僅被訪問一次，這一過程就叫做圖的遍歷
在圖結構中，存在著兩種遍歷搜索的方式，分別是 廣度優先搜索 和 深度優先搜索
廣度優先遍歷（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
}}冒泡排序（Bubble Sort）是一種簡單的排序算法。它重復地遍歷要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。遍歷數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
運行流程：
比較相鄰的元素。如果第一個比第二個大（升序），就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。
針對所有的元素重復以上的步驟，除了最后一個。
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
動圖實現：
靜圖詳解：
交換過程圖示(第一次)：
那么我們需要進行n-1次冒泡過程，每次對應的比較次數如下圖所示：
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));
}
}}最優時間復雜度：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)的時間復雜度是一個比較糟糕的結果，尤其在數據量很大的情況下。所以冒泡排序通常不會用于實際應用。
傳統的冒泡算法每次排序只確定了最大值，我們可以在每次循環之中進行正反兩次冒泡，分別找到最大值和最小值，如此可使排序的輪數減少一半
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));
}
}}選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優點與數據移動有關。如果某個元素位于正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬于非常好的一種
動圖展示：
動圖1：
動圖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));
}
}}最優時間復雜度：O(n^2)
最壞時間復雜度：O(n^2)
穩定性：不穩定（考慮升序每次選擇最大的情況）
選擇排序與冒泡排序一樣，需要進行N*(N-1)/2次比較，但是只需要N次交換，當N很大時，交換次數的時間影響力更大，所以選擇排序的時間復雜度為O(N^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, 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));
}
}}插入排序（Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間
動圖展示：
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));
}
}}最優時間復雜度：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)，這三者被稱為簡單排序或者基本排序，三者都是穩定的排序算法。
如果待排序數組基本有序時，插入排序的效率會更高
在插入某個元素之前需要先確定該元素在有序數組中的位置，上例的做法是對有序數組中的元素逐個掃描，當數據量比較大的時候，這是一個很耗時間的過程，可以采用二分查找法改進，這種排序也被稱為二分插入排序
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));
}
}}歸并排序（Merge Sort）是采用分治法的一個非常典型的應用。歸并排序的思想就是先遞歸分解數組，再合并數組。
將數組分解最小之后，然后合并兩個有序數組，基本思路是比較兩個數組的最前面的數，誰小就先取誰，取了后相應的指針就往后移一位。然后再比較，直至一個數組為空，最后把另一個數組的剩余部分復制過來即可。
動圖展示：
動圖1
動圖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));
}}最優時間復雜度：O(nlogn)
最壞時間復雜度：O(nlogn)
穩定性：穩定
快速排序（Quick Sort），又稱劃分交換排序（partition-exchange sort），通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
排序步驟：
1、 從數列中挑出一個元素，稱為"基準"（pivot），通常選擇第一個元素
2、重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區結束之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
3、遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
動圖展示：
動圖1
動圖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);
}
}}最優時間復雜度：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)時間。
希爾排序（Shell Sort）是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因DL．Shell于1959年提出而得名。 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止
動圖展示：
靜圖分析：
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));
}
}}最優時間復雜度：根據步長序列的不同而不同
最壞時間復雜度：O(n^2)
穩定性：不穩定
希爾排序不像其他時間復雜度為O(N log2N)的排序算法那么快，但是比選擇排序和插入排序這種時間復雜度為O(N2)的排序算法還是要快得多，而且非常容易實現。它在最壞情況下的執行效率和在平均情況下的執行效率相比不會降低多少，而快速排序除非采取特殊措施，否則在最壞情況下的執行效率變得非常差。
迄今為止，還無法從理論上精準地分析希爾排序的效率，有各種各樣基于試驗的評估，估計它的時間級介于O(N^3/2)與 O(N^7/6)之間。我們可以認為希爾排序的平均時間復雜度為o(n^1.3)。
堆排序（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.
步驟三 后續過程，繼續進行調整，交換，如此反復進行，最終使得整個序列有序
排序思路：
將無需序列構建成一個堆，根據升序降序需求選擇大頂堆或小頂堆;
將堆頂元素與末尾元素交換，將最大元素"沉"到數組末端;
重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，反復執行調整+交換步驟，直到整個序列有序
動圖展示：
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));
}}最優時間復雜度：o(nlogn)
最壞時間復雜度：o(nlogn)
穩定性：不穩定
它的運行時間主要是消耗在初始構建堆和在重建堆時的反復篩選上。
在構建堆的過程中，因為我們是完全二叉樹從最下層最右邊的非終端結點開始構建，將它與其孩子進行比較和若有必要的互換，對于每個非終端結點來說，其實最多進行兩次比較和互換操作，因此整個構建堆的時間復雜度為O(n)。
在正式排序時，第i次取堆頂記錄重建堆需要用O(logi)的時間（完全二叉樹的某個結點到根結點的距離為log2i＋1），并且需要取n-1次堆頂記錄，因此，重建堆的時間復雜度為O(nlogn)。
所以總體來說，堆排序的時間復雜度為O(nlogn)。由于堆排序對原始記錄的排序狀態并不敏感，因此它無論是最好、最壞和平均時間復雜度均為O(nlogn)。這在性能上顯然要遠遠好過于冒泡、簡單選擇、直接插入的O(n2)的時間復雜度了。
空間復雜度上，它只有一個用來交換的暫存單元，也非常的不錯。不過由于記錄的比較與交換是跳躍式進行，因此堆排序是一種不穩定的排序方法。
計數排序（Counting Sort）不是基于比較的排序算法，其核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。 作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。
排序步驟：
找出待排序的數組中最大和最小的元素；
統計數組中每個值為i的元素出現的次數，存入數組C的第i項；
對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；
反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1
動圖展示：
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;
}
}
}}最優時間復雜度：o(n+k)
最壞時間復雜度：o(n+k)
穩定性：不穩定
計數排序是一個穩定的排序算法。當輸入的元素是 n 個 0到 k 之間的整數時，時間復雜度是O(n+k)，空間復雜度也是O(n+k)，其排序速度快于任何比較排序算法。當k不是很大并且序列比較集中時，計數排序是一個很有效的排序算法
桶排序 （Bucket sort）或所謂的箱排序，是一個排序算法，工作的原理是將數組分到有限數量的桶里。每個桶再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序），最后依次把各個桶中的記錄列出來記得到有序序列。桶排序是鴿巢排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間 o(n)。但桶排序并不是比較排序，他不受到O(n log n)下限的影響。
排序步驟：
設置一個定量的數組當作空桶；
遍歷輸入數據，并且把數據一個一個放到對應的桶里去；
對每個不是空的桶進行排序；
從不是空的桶里把排好序的數據拼接起來
動圖展示：
靜圖展示：
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());
}}最優時間復雜度：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個空間。其次待排序的元素都要在一定的范圍內等等。
基數排序（Radix Sort）是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前
排序步驟：
取得數組中的最大數，并取得位數；
arr為原始數組，從最低位開始取每個位組成radix數組；
對radix進行計數排序（利用計數排序適用于小范圍數的特點）
動圖展示：
靜圖分析：
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));
}
}}最優時間復雜度：O(n^k)
最壞時間復雜度：O(n^k)
穩定性：穩定
初看起來，基數排序的執行效率似乎好的讓人無法相信，所有要做的只是把原始數據項從數組復制到鏈表，然后再復制回去。如果有10個數據項，則有20次復制，對每一位重復一次這個過程。假設對5位的數字排序，就需要20 * 5=100次復制。
*如果有100個數據項，那么就有200 * 5=1000次復制。復制的次數與數據項的個數成正比，即O(n)。這是我們看到的效率最高的排序算法。
不幸的是，數據項越多，就需要更長的關鍵字，如果數據項增加10倍，那么關鍵字必須增加一位（多一輪排序）。復制的次數和數據項的個數與關鍵字長度成正比，可以認為關鍵字長度是N的對數。因此在大多數情況下，基數排序的執行效率倒退為O(N*logN)，和快速排序差不多
感謝各位的閱讀！關于“Java數據結構與算法的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
