第一部分：Java數(shù)據(jù)結(jié)構(gòu)

要理解Java數(shù)據(jù)結(jié)構(gòu)，必須能清楚何為數(shù)據(jù)結(jié)構(gòu)？

數(shù)據(jù)結(jié)構(gòu):

1. Data_Structure，它是儲(chǔ)存數(shù)據(jù)的一種結(jié)構(gòu)體，在此結(jié)構(gòu)中儲(chǔ)存一些數(shù)據(jù)，而這些數(shù)據(jù)之間有一定的關(guān)系。
2. 而各數(shù)據(jù)元素之間的相互關(guān)系，又包括三個(gè)組成成分，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)運(yùn)算結(jié)構(gòu)。
3. 而一個(gè)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)過(guò)程分成抽象層、數(shù)據(jù)結(jié)構(gòu)層和實(shí)現(xiàn)層。

數(shù)據(jù)結(jié)構(gòu)在Java的語(yǔ)言體系中按邏輯結(jié)構(gòu)可以分為兩大類(lèi)：線(xiàn)性數(shù)據(jù)結(jié)構(gòu)和非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。

一、Java數(shù)據(jù)結(jié)構(gòu)之：線(xiàn)性數(shù)據(jù)結(jié)構(gòu)

線(xiàn)性數(shù)據(jù)結(jié)構(gòu)：常見(jiàn)的有一維數(shù)組，線(xiàn)性表，棧，隊(duì)列，雙隊(duì)列，串。

1：一維數(shù)組

在Java里面常用的util有：String [],int [],ArrayList,Vector,CopyOnWriteArrayList等。及可以同過(guò)一維數(shù)組[]自己實(shí)現(xiàn)不同邏輯結(jié)構(gòu)的Util類(lèi)。而ArrayList封裝了一些[]的基本操作方法。ArrayList和Vector的區(qū)別是:Vector是線(xiàn)程安全的，方法同步。CopyOnWriteArrayList也是線(xiàn)程安全的但效率要比Vector高很多。(PS:如果不懂出門(mén)右拐看另一篇chat)。

數(shù)組這種數(shù)據(jù)結(jié)構(gòu)典型的操作方法，是根據(jù)下標(biāo)進(jìn)行操作的，所以insert的的時(shí)候可以根據(jù)下標(biāo)插入到具體的某個(gè)位置，但是這個(gè)時(shí)候它后面的元素都得往后面移動(dòng)一位。所以插入效率比較低,更新，刪除效率也比較低，而查詢(xún)效率非常高,查詢(xún)效率時(shí)間復(fù)雜度是1。

2： 線(xiàn)性表

線(xiàn)性表是有序的儲(chǔ)存結(jié)構(gòu)、鏈?zhǔn)降膬?chǔ)存結(jié)構(gòu)。鏈表的物理儲(chǔ)存空間是不連續(xù)的，鏈表的每一個(gè)節(jié)點(diǎn)都知道上一個(gè)節(jié)點(diǎn)、或者下一個(gè)節(jié)點(diǎn)是誰(shuí)，通常用Node表示。常見(jiàn)的有順序鏈表(LinkedList、Linked***)，單項(xiàng)鏈表（里面只有Node類(lèi)），雙向鏈表(兩個(gè)Node類(lèi))，循環(huán)鏈表(多個(gè)Node類(lèi))等。

操作方法：插入效率比較高，插入的時(shí)候只需要改變節(jié)點(diǎn)的前后節(jié)點(diǎn)的連接即可。而查詢(xún)效率就比較低了，如果實(shí)現(xiàn)的不好，需要整個(gè)鏈路找下去才能找到應(yīng)該找的元素。所以常見(jiàn)的方法有：add(index,element),addFirst(element),addLast(element)。getFirst(),getLast(),get(element)等。

常見(jiàn)的Uitil有：LinkedList，LinkedMap等，而這兩個(gè)JDK底層也做了N多優(yōu)化，可以有效避免查詢(xún)效率低的問(wèn)題。當(dāng)自己實(shí)現(xiàn)的時(shí)候需要注意。其實(shí)樹(shù)形結(jié)構(gòu)可以說(shuō)是非線(xiàn)性的鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)。

3: 棧Stack

棧,最主要的是要實(shí)現(xiàn)先進(jìn)后出，后進(jìn)先出的邏輯結(jié)構(gòu)。來(lái)實(shí)現(xiàn)一些場(chǎng)景對(duì)邏輯順序的要求。所以常用的方法有push(element)壓棧，pop()出棧。

java.util.Stack。就實(shí)現(xiàn)了這用邏輯。而Java的Jvm里面也用的到了此種數(shù)據(jù)結(jié)構(gòu)，就是線(xiàn)程棧，來(lái)保證當(dāng)前線(xiàn)程的執(zhí)行順序。

4：隊(duì)列

隊(duì)列，隊(duì)列是一種特殊的線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，隊(duì)列只能允許在隊(duì)頭，隊(duì)尾進(jìn)行添加和查詢(xún)等相關(guān)操作。隊(duì)列又有單項(xiàng)有序隊(duì)列，雙向隊(duì)列，阻塞隊(duì)列等。

Queue這種數(shù)據(jù)結(jié)構(gòu)注定了基本操作方法有：add(E e)加入隊(duì)列，remove(),poll()等方法。

隊(duì)列在Java語(yǔ)言環(huán)境中是使用頻率相當(dāng)高的數(shù)據(jù)結(jié)構(gòu)，所有其實(shí)現(xiàn)的類(lèi)也很多來(lái)滿(mǎn)足不同場(chǎng)景。

使用場(chǎng)景也非常多，如線(xiàn)程池，mq，連接池等。

5：串

串：也稱(chēng)字符串，是由N個(gè)字符組成的優(yōu)先序列。在Java里面就是指String,而String里面是由chat[]來(lái)進(jìn)行儲(chǔ)存。

KMP算法： 這個(gè)算法一定要牢記，Java數(shù)據(jù)結(jié)構(gòu)這本書(shū)里面針對(duì)字符串的查找匹配算法也只介紹了一種。關(guān)鍵點(diǎn)就是：在字符串比對(duì)的時(shí)候，主串的比較位置不需要回退的問(wèn)題。

二、Java數(shù)據(jù)結(jié)構(gòu)之：非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)

非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)：常見(jiàn)的有：多維數(shù)組，集合，樹(shù)，圖，散列表(hash).

1：多維數(shù)組

一維數(shù)組前面咱也提到了，多維數(shù)組無(wú)非就是String [][],int[][]等。Java里面很少提供這樣的工具類(lèi)，而java里面tree和圖底層的native方法用了多維數(shù)組來(lái)儲(chǔ)存。

2：集合

由一個(gè)或多個(gè)確定的元素所構(gòu)成的整體叫做集合。在Java里面可以去廣義的去理解為實(shí)現(xiàn)了Collection接口的類(lèi)都叫集合。

3：樹(shù)

樹(shù)形結(jié)構(gòu)，作者覺(jué)得它是一種特殊的鏈形數(shù)據(jù)結(jié)構(gòu)。最少有一個(gè)根節(jié)點(diǎn)組成，可以有多個(gè)子節(jié)點(diǎn)。樹(shù)，顯然是由遞歸算法組成。

樹(shù)的特點(diǎn)：

在一個(gè)樹(shù)結(jié)構(gòu)中，有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有直接父節(jié)點(diǎn)，它就是根節(jié)點(diǎn)。除了根節(jié)點(diǎn)，其他結(jié)點(diǎn)有且只有一個(gè)直接父節(jié)點(diǎn)每個(gè)結(jié)點(diǎn)可以有任意多個(gè)直接子節(jié)點(diǎn)。

樹(shù)的數(shù)據(jù)結(jié)構(gòu)又分如下幾種：

1) 自由樹(shù)/普通樹(shù)：對(duì)子節(jié)點(diǎn)沒(méi)有任何約束。

2) 二叉樹(shù)：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子節(jié)點(diǎn)的樹(shù)稱(chēng)為二叉樹(shù)。

2.1) 一般二叉樹(shù)：每個(gè)子節(jié)點(diǎn)的父親節(jié)點(diǎn)不一定有兩個(gè)子節(jié)點(diǎn)的二叉樹(shù)成為一般二叉樹(shù)。

2.2) 完全二叉樹(shù)：對(duì)于一顆二叉樹(shù)，假設(shè)其深度為d（d>1）。除了第d層外，其它各層的節(jié)點(diǎn)數(shù)目均已達(dá)最大值，且第d層所有節(jié)點(diǎn)從左向右連續(xù)地緊密排列，這樣的二叉樹(shù)被稱(chēng)為完全二叉樹(shù)；

2.3) 滿(mǎn)二叉樹(shù)：所有的節(jié)點(diǎn)都是二叉的二叉樹(shù)成為滿(mǎn)二叉樹(shù)。

3) 二叉搜索樹(shù)/BST：binary search tree,又稱(chēng)二叉排序樹(shù)、二叉查找樹(shù)。是有序的。要點(diǎn)：如果不為空，那么其左子樹(shù)節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值；右子樹(shù)節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值。

3.1) 二叉平衡樹(shù)：二叉搜索樹(shù)，是有序的排序樹(shù)，但左右兩邊包括子節(jié)點(diǎn)不一定平衡，而二叉平衡樹(shù)是排序樹(shù)的一種，并且加點(diǎn)條件，就是任意一個(gè)節(jié)點(diǎn)的兩個(gè)叉的深度差不多（比如差值的絕對(duì)值小于某個(gè)常數(shù)，或者一個(gè)不能比另一個(gè)深出去一倍之類(lèi)的）。這樣的樹(shù)可以保證二分搜索任意元素都是O(log n)的，一般還附帶帶有插入或者刪除某個(gè)元素也是O(log n)的的性質(zhì)。

為了實(shí)現(xiàn)，二叉平衡樹(shù)又延伸出來(lái)了一些算法，業(yè)界常見(jiàn)的有AVL、和紅黑算法，所以又有以下兩種樹(shù)：

3.1.1) AVL樹(shù)：最早的平衡二叉樹(shù)之一。應(yīng)用相對(duì)其他數(shù)據(jù)結(jié)構(gòu)比較少。windows對(duì)進(jìn)程地址空間的管理用到了AVL樹(shù)。

3.1.2) 紅黑樹(shù)：通過(guò)制定了一些紅黑標(biāo)記和左右旋轉(zhuǎn)規(guī)則來(lái)保證二叉樹(shù)平衡。

紅黑樹(shù)的5條性質(zhì)：

每個(gè)結(jié)點(diǎn)要么是紅的，要么是黑的。根結(jié)點(diǎn)是黑的。每個(gè)葉結(jié)點(diǎn)（葉結(jié)點(diǎn)即指樹(shù)尾端NIL指針或NULL結(jié)點(diǎn)）是黑的。如果一個(gè)結(jié)點(diǎn)是紅的，那么它的倆個(gè)兒子都是黑的。對(duì)于任一結(jié)點(diǎn)而言，其到葉結(jié)點(diǎn)樹(shù)尾端NIL指針的每一條路徑都包含相同數(shù)目的黑結(jié)點(diǎn)。

4) B-tree：又稱(chēng)B樹(shù)、B-樹(shù)。又叫平衡(balance)多路查找樹(shù)。樹(shù)中每個(gè)結(jié)點(diǎn)最多含有m個(gè)孩子（m>=2）。它類(lèi)似普通的平衡二叉樹(shù)，不同的一點(diǎn)是B-樹(shù)允許每個(gè)節(jié)點(diǎn)有更多的子節(jié)點(diǎn)。

4) B+tree：又稱(chēng)B+。是B-樹(shù)的變體，也是一種多路搜索樹(shù)。

樹(shù)總結(jié)：
樹(shù)在Java里面應(yīng)用的也比較多。非排序樹(shù)，主要用來(lái)做數(shù)據(jù)儲(chǔ)存和展示。而排序樹(shù)，主要用來(lái)做算法和運(yùn)算，HashMap里面的TreeNode就用到了紅黑樹(shù)算法。而B(niǎo)+樹(shù)在數(shù)據(jù)庫(kù)的索引原理里面有典型的應(yīng)用。

4：Hash

Hash概念：

Hash，一般翻譯做“散列”，也有直接音譯為“哈?！钡?，就是把任意長(zhǎng)度的輸入（又叫做預(yù)映射， pre-image），變換成固定長(zhǎng)度的輸出，該輸出就是散列值。一般通過(guò)Hash算法實(shí)現(xiàn)。

所謂的Hash算法都是散列算法，把任意長(zhǎng)度的輸入，變換成固定長(zhǎng)度的輸出，該輸出就是散列值.（如：MD5,SHA1,加解密算法等）

簡(jiǎn)單的說(shuō)就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)。

Java中的hashCode：

我們都知道所有的class都是Object的子類(lèi)，既所有的class都會(huì)有默認(rèn)Object.java里面的hashCode的方法，如果自己沒(méi)有重寫(xiě)，默認(rèn)情況就是native方法通過(guò)對(duì)象的內(nèi)存的+對(duì)象的值然后通過(guò)hash散列算法計(jì)算出來(lái)個(gè)int的數(shù)字。

最大的特性是：不同的對(duì)象，不同的值有可能計(jì)算出來(lái)的hashCode可能是一樣的。

Hash表：

Java中數(shù)據(jù)存儲(chǔ)方式最底層的兩種結(jié)構(gòu)，一種是數(shù)組，另一種就是鏈表。而Hash表就是綜合了這兩種數(shù)據(jù)結(jié)構(gòu)。

如：HashTable,HashMap。這個(gè)時(shí)候就得提一下HashMap的原理了，默認(rèn)16個(gè)數(shù)組儲(chǔ)存，通過(guò)Hash值取模放到不同的桶里面去。（注意：JDK1.8此處算法又做了改進(jìn)，數(shù)組里面的值會(huì)演變成樹(shù)形結(jié)構(gòu)。）

哈希表具有較快（常量級(jí)）的查詢(xún)速度，及相對(duì)較快的增刪速度，所以很適合在海量數(shù)據(jù)的環(huán)境中使用。一般實(shí)現(xiàn)哈希表的方法采用“拉鏈法”，我們可以理解為“鏈表的數(shù)組”。

一致性Hash：

我們查看一下HashMap的原理，其實(shí)發(fā)現(xiàn)Hash很好的解決了單體應(yīng)用情況下的數(shù)據(jù)查找和插入的速度問(wèn)題。但是畢竟單體應(yīng)用的儲(chǔ)存空間是有限的，所有在分布式環(huán)境下，應(yīng)運(yùn)而生了一致性Hash算法。

用意和hashCode的用意一樣，只不過(guò)它是取模放在不同的IP機(jī)器上而已。具體算法可以找一下相關(guān)資料。

而一致性Hash需要注意的就是默認(rèn)分配的桶比較多些，而當(dāng)其中一臺(tái)機(jī)器掛了，影響的面比較小一些。

需要注意的是，相同的內(nèi)容算出來(lái)的hash一定是一樣的。既：冪等性。

第二部分：Java基本算法

理解了Java數(shù)據(jù)結(jié)構(gòu)，還必須要掌握一些常見(jiàn)的基本算法。 理解算法之前必須要先理解的幾個(gè)算法的概念：

空間復(fù)雜度：一句來(lái)理解就是，此算法在規(guī)模為n的情況下額外消耗的儲(chǔ)存空間。

時(shí)間復(fù)雜度：一句來(lái)理解就是，此算法在規(guī)模為n的情況下，一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱(chēng)為語(yǔ)句頻度或時(shí)間頻度。

穩(wěn)定性：主要是來(lái)描述算法，每次執(zhí)行完，得到的結(jié)果都是一樣的，但是可以不同的順序輸入，可能消耗的時(shí)間復(fù)雜度和空間復(fù)雜度不一樣。

一、二分查找算法

二分查找又稱(chēng)折半查找，優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好，占用系統(tǒng)內(nèi)存較少；其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。這個(gè)是基礎(chǔ)，最簡(jiǎn)單的查找算法了。

 public static void main(String[] args) {
  int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
  System.out.println(binSearch(srcArray, 28));
 }
 /**
  * 二分查找普通循環(huán)實(shí)現(xiàn)
  *
  * @param srcArray 有序數(shù)組
  * @param key 查找元素
  * @return
  */
 public static int binSearch(int srcArray[], int key) {
  int mid = srcArray.length / 2;
//  System.out.println("=:"+mid);
  if (key == srcArray[mid]) {
   return mid;
  }
 
//二分核心邏輯
  int start = 0;
  int end = srcArray.length - 1;
  while (start <= end) {
//   System.out.println(start+"="+end);
   mid = (end - start) / 2 + start;
   if (key < srcArray[mid]) {
    end = mid - 1;
   } else if (key > srcArray[mid]) {
    start = mid + 1;
   } else {
    return mid;
   }
  }
  return -1;
 }

二分查找算法如果沒(méi)有用到遞歸方法的話(huà)，只會(huì)影響CPU。對(duì)內(nèi)存模型來(lái)說(shuō)影響不大。時(shí)間復(fù)雜度log2n，2的開(kāi)方。空間復(fù)雜度是2。一定要牢記這個(gè)算法。應(yīng)用的地方也是非常廣泛，平衡樹(shù)里面大量采用。

二、遞歸算法

遞歸簡(jiǎn)單理解就是方法自身調(diào)用自身。

 public static void main(String[] args) {
  int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
  System.out.println(binSearch(srcArray, 0,15,28));
 }
 /**
  * 二分查找遞歸實(shí)現(xiàn)
  *
  * @param srcArray 有序數(shù)組
  * @param start 數(shù)組低地址下標(biāo)
  * @param end 數(shù)組高地址下標(biāo)
  * @param key 查找元素
  * @return 查找元素不存在返回-1
  */
 public static int binSearch(int srcArray[], int start, int end, int key) {
  int mid = (end - start) / 2 + start;
  if (srcArray[mid] == key) {
   return mid;
  }
  if (start >= end) {
   return -1;
  } else if (key > srcArray[mid]) {
   return binSearch(srcArray, mid + 1, end, key);
  } else if (key < srcArray[mid]) {
   return binSearch(srcArray, start, mid - 1, key);
  }
  return -1;
 }

遞歸幾乎會(huì)經(jīng)常用到，需要注意的一點(diǎn)是：遞歸不光影響的CPU。JVM里面的線(xiàn)程?？臻g也會(huì)變大。所以當(dāng)遞歸的調(diào)用鏈長(zhǎng)的時(shí)候需要-Xss設(shè)置線(xiàn)程棧的大小。

三、八大排序算法

一、直接插入排序（Insertion Sort）
二、希爾排序（Shell Sort）
三、選擇排序（Selection Sort）
四、堆排序（Heap Sort）
五、冒泡排序（Bubble Sort）
六、快速排序（Quick Sort）
七、歸并排序（Merging Sort）
八、基數(shù)排序（Radix Sort）

八大算法，網(wǎng)上的資料就比較多了。

吐血推薦參考資料：git hub 八大排序算法詳解。此大神比作者講解的還詳細(xì)，作者就不在這里，描述重復(fù)的東西了，作者帶領(lǐng)大家把重點(diǎn)的兩個(gè)強(qiáng)調(diào)一下,此兩個(gè)是必須要掌握的。

1：冒泡排序

基本思想：

冒泡排序（Bubble Sort）是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪(fǎng)過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪(fǎng)數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

以下是冒泡排序算法復(fù)雜度:

冒泡排序是最容易實(shí)現(xiàn)的排序, 最壞的情況是每次都需要交換, 共需遍歷并交換將近n²/2次, 時(shí)間復(fù)雜度為O(n²). 最佳的情況是內(nèi)循環(huán)遍歷一次后發(fā)現(xiàn)排序是對(duì)的, 因此退出循環(huán), 時(shí)間復(fù)雜度為O(n). 平均來(lái)講, 時(shí)間復(fù)雜度為O(n²). 由于冒泡排序中只有緩存的temp變量需要內(nèi)存空間, 因此空間復(fù)雜度為常量O(1).

Tips: 由于冒泡排序只在相鄰元素大小不符合要求時(shí)才調(diào)換他們的位置, 它并不改變相同元素之間的相對(duì)順序, 因此它是穩(wěn)定的排序算法.

/**
 * 冒泡排序
 *
 * ①. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
 * ②. 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。
 * ③. 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
 * ④. 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟①~③，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
 * @param arr 待排序數(shù)組
 */
public static void bubbleSort(int[] arr){
 for (int i = arr.length; i > 0; i--) {  //外層循環(huán)移動(dòng)游標(biāo)
  for(int j = 0; j < i && (j+1) < i; j++){ //內(nèi)層循環(huán)遍歷游標(biāo)及之后(或之前)的元素
   if(arr[j] > arr[j+1]){
    int temp = arr[j];
    arr[j] = arr[j+1];
    arr[j+1] = temp;
    System.out.println("Sorting: " + Arrays.toString(arr));
   }
  }
 }
}

2：快速排序

快速排序使用分治策略來(lái)把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）。步驟為：

①. 從數(shù)列中挑出一個(gè)元素，稱(chēng)為”基準(zhǔn)”（pivot）。

②. 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱(chēng)為分區(qū)（partition）操作。

③. 遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

遞歸到最底部時(shí)，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個(gè)算法一定會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

代碼實(shí)現(xiàn)：

用偽代碼描述如下：

①. i = L; j = R; 將基準(zhǔn)數(shù)挖出形成第一個(gè)坑a[i]。

②．j--，由后向前找比它小的數(shù)，找到后挖出此數(shù)填前一個(gè)坑a[i]中。

③．i++，由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個(gè)坑a[j]中。

④．再重復(fù)執(zhí)行②，③二步，直到i==j，將基準(zhǔn)數(shù)填入a[i]中。

快速排序采用“分而治之、各個(gè)擊破”的觀念，此為原地（In-place）分區(qū)版本。

/**
 * 快速排序（遞歸）
 *
 * ①. 從數(shù)列中挑出一個(gè)元素，稱(chēng)為"基準(zhǔn)"（pivot）。
 * ②. 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱(chēng)為分區(qū)（partition）操作。
 * ③. 遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
 * @param arr 待排序數(shù)組
 * @param low 左邊界
 * @param high 右邊界
 */
public static void quickSort(int[] arr, int low, int high){
 if(arr.length <= 0) return;
 if(low >= high) return;
 int left = low;
 int right = high;
 int temp = arr[left]; //挖坑1：保存基準(zhǔn)的值
 while (left < right){
  while(left < right && arr[right] >= temp){ //坑2：從后向前找到比基準(zhǔn)小的元素，插入到基準(zhǔn)位置坑1中
   right--;
  }
  arr[left] = arr[right];
  while(left < right && arr[left] <= temp){ //坑3：從前往后找到比基準(zhǔn)大的元素，放到剛才挖的坑2中
   left++;
  }
  arr[right] = arr[left];
 }
 arr[left] = temp; //基準(zhǔn)值填補(bǔ)到坑3中，準(zhǔn)備分治遞歸快排
 System.out.println("Sorting: " + Arrays.toString(arr));
 quickSort(arr, low, left-1);
 quickSort(arr, left+1, high);
}

以下是快速排序算法復(fù)雜度:

快速排序排序效率非常高。 雖然它運(yùn)行最糟糕時(shí)將達(dá)到O(n²)的時(shí)間復(fù)雜度, 但通常平均來(lái)看, 它的時(shí)間復(fù)雜為O(nlogn), 比同樣為O(nlogn)時(shí)間復(fù)雜度的歸并排序還要快. 快速排序似乎更偏愛(ài)亂序的數(shù)列, 越是亂序的數(shù)列, 它相比其他排序而言, 相對(duì)效率更高.

最新評(píng)論