尚硅谷-數(shù)據(jù)結(jié)構(gòu)排序算法

1、數(shù)據(jù)結(jié)構(gòu)-排序算法講師：劉優(yōu)I ? T?算法+數(shù)據(jù)結(jié)構(gòu)=程序數(shù)據(jù)結(jié)構(gòu)編程的本質(zhì)就是對(duì)數(shù)據(jù)（信息以數(shù)據(jù)的形式而存在）的處理，實(shí)際編程中不得不處理大量數(shù)據(jù)，因此實(shí)際動(dòng)手編程之前必須先分析處理這些數(shù)據(jù)，處理數(shù)據(jù)之間存在的關(guān)系?，F(xiàn)實(shí)的數(shù)據(jù)元素之間有著紛繁復(fù)雜的邏輯關(guān)系，需要采用合適的物理結(jié)構(gòu)來存儲(chǔ)這些數(shù)據(jù)，并以此為基礎(chǔ)對(duì)這些數(shù)據(jù)進(jìn)行相應(yīng)的操作。同時(shí)，還要分析這些數(shù)據(jù)結(jié)構(gòu)在時(shí)間、空間上的開銷的優(yōu)劣。這種專門研究應(yīng)用程序中數(shù)據(jù)之間邏輯關(guān)系、存儲(chǔ)方式及其操作的學(xué)問就是數(shù)據(jù)結(jié)構(gòu)。Data-Structure = (D,R)數(shù)據(jù)元素之間存在的關(guān)聯(lián)關(guān)系被稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。歸納起來，應(yīng)用程序中的數(shù)據(jù)大致有如下四種

2、基本的邏輯結(jié)構(gòu)：集合：數(shù)據(jù)元素之間只有“同屬于一個(gè)集合”的關(guān)系線性關(guān)系：數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系同一種的邏輯結(jié)構(gòu)，在底層通常有兩種物理存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)一維數(shù)組非順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈表）、散列結(jié)構(gòu)算法的設(shè)計(jì)取決于邏輯結(jié)構(gòu)；算法的實(shí)現(xiàn)依賴于存儲(chǔ)結(jié)構(gòu)對(duì)于普通線性表而言，它的作用是一個(gè)容器，用于盛裝具有相似結(jié)構(gòu)的數(shù)據(jù)。分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以進(jìn)行插入、刪除和排序的操作如果線性表，只允許在線性表的某端添加、刪除元素，這時(shí)就演變?yōu)椋簵：完?duì)列棧（stack），是一種特殊的線性表，只能

3、在固定在一端（線性表的尾端）進(jìn)行插入、刪除操作。允許進(jìn)行插入、刪除操作的一端為棧頂top，另一端為棧底bottom。進(jìn)棧：將一個(gè)元素插入棧的過程。棧的長(zhǎng)度+1。“壓入?！背鰲＃簞h除一個(gè)元素的過程。棧的長(zhǎng)度-1?！皬棾鰲！毕冗M(jìn)后出，或說后進(jìn)先出。常用操作：初始化。分為順序棧結(jié)構(gòu)和鏈?zhǔn)綏＝Y(jié)構(gòu)隊(duì)列（queue），也是一種特殊的線性表，使用固定的一端（隊(duì)尾rear）來插入數(shù)據(jù)，另一端（對(duì)頭front）用于刪除數(shù)據(jù)。先進(jìn)先出。就像購(gòu)物一樣，先進(jìn)入隊(duì)伍的顧客先獲得服務(wù)，整個(gè)隊(duì)伍按固定方向移動(dòng)。分為順序隊(duì)列結(jié)構(gòu)和鏈?zhǔn)疥?duì)列結(jié)構(gòu)從JDK1.5開始，java集合框架提供了Queue接口。實(shí)現(xiàn)該接口的類可以當(dāng)成隊(duì)列

4、使用。樹，也是一種數(shù)據(jù)結(jié)構(gòu)，非線性的，這種結(jié)構(gòu)內(nèi)的元素存在一對(duì)多的關(guān)系。樹，尤其是二叉樹應(yīng)用很廣泛。哈夫曼樹和哈夫曼編碼就是二叉樹的重要用途。排序二叉樹、平衡二叉樹、紅黑樹二叉樹：在普通樹的基礎(chǔ)上，讓一棵樹中每個(gè)節(jié)點(diǎn)最多只能包含兩個(gè)子節(jié)點(diǎn)，且嚴(yán)格區(qū)分左子節(jié)點(diǎn)和右子節(jié)點(diǎn)（位置不能換）遍歷二叉樹，考慮深度優(yōu)先遍歷(先序遍歷、中序遍歷和后序遍歷)和廣度優(yōu)先遍歷哈夫曼樹，一種帶權(quán)路徑最短的二叉樹，在信息檢索中很常用。哈夫曼編碼，假設(shè)需要對(duì)一個(gè)字符串如“abcdabcaba”進(jìn)行編碼，將它轉(zhuǎn)換為唯一的二進(jìn)制碼，同時(shí)要求轉(zhuǎn)換出來的二進(jìn)制碼的長(zhǎng)度最小。我們采用哈夫曼樹來解決報(bào)文編碼問題。排序二叉樹：一種特殊

5、的二叉樹，可以非常方便地對(duì)樹中的所有節(jié)點(diǎn)進(jìn)行排序和檢索。滿足一些條件的二叉樹，才被稱為排序二叉樹。比如：若它的左子樹不為空，左子樹上的所有節(jié)點(diǎn)值均小于根節(jié)點(diǎn)值；若右子樹不為空，右子樹上的所有節(jié)點(diǎn)值均大于根節(jié)點(diǎn)值。紅黑樹：一種更高效的檢索二叉樹，常用來實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。在實(shí)際編程中都有極為廣泛的用途，例如JDK提供的集合類TreeMap就是一棵紅黑樹的實(shí)現(xiàn)。紅黑樹在只讀操作上，跟普通排序二叉樹上的只讀操作相同，只是檢索性能好。對(duì)于刪除和插入操作可能導(dǎo)致樹不再符合紅黑樹的特征。（需要進(jìn)行顏色的調(diào)換）紅黑樹的特性：首先滿足排序二叉樹的特性；每個(gè)節(jié)點(diǎn)要么紅色，要么黑色；根節(jié)點(diǎn)是黑色的；所有葉子節(jié)點(diǎn)都是nu

6、ll且為黑色；紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)是黑色的；從任一節(jié)點(diǎn)到其子樹的每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)）數(shù)據(jù)結(jié)構(gòu)之排序排序：假設(shè)含有n個(gè)記錄的序列為R1，R2，.,Rn,其相應(yīng)的關(guān)鍵字序列為K1，K2，.,Kn。將這些記錄重新排序?yàn)镽i1,Ri2,.,Rin,使得相應(yīng)的關(guān)鍵字值滿足條Ki1=Ki2=.=Kin,這樣的一種操作稱為排序。通常來說，排序的目的是快速查找。衡量排序算法的優(yōu)劣：1.時(shí)間復(fù)雜度：分析關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)2.空間復(fù)雜度：分析排序算法中需要多少輔助內(nèi)存3.穩(wěn)定性：若兩個(gè)記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。排序算

7、法分類：內(nèi)部排序和外部排序。內(nèi)部排序：整個(gè)排序過程不需要借助于外部存儲(chǔ)器（如磁盤等），所有排序操作都在內(nèi)存中完成。外部排序：參與排序的數(shù)據(jù)非常多，數(shù)據(jù)量非常大，計(jì)算機(jī)無法把整個(gè)排序過程放在內(nèi)存中完成，必須借助于外部存儲(chǔ)器（如磁盤）。外部排序最常見的是多路歸并排序。可以認(rèn)為外部排序是由多次內(nèi)部排序組成。常用的內(nèi)部排序選擇排序直接選擇排序、堆排序交換排序冒泡排序、快速排序插入排序直接插入排序、折半插入排序、Shell排序歸并排序桶式排序基數(shù)排序常用的內(nèi)部排序選擇排序直接選擇排序、堆排序交換排序冒泡排序、快速排序插入排序直接插入排序、折半插入排序、Shell排序歸并排序桶式排序基數(shù)排序選擇排序基本原

8、理：將待排序的元素分為已排序（初始為空）和未排序兩組，依次將未排序的元素中值最小的元素放入已排序的組中。直接選擇排序簡(jiǎn)單直觀，但性能略差；堆排序是一種較為高效的選擇排序方法，但實(shí)現(xiàn)起來略微復(fù)雜直接選擇排序直接選擇排序的基本過程為：SelectSort.javaSelectSort2.java算法的時(shí)間效率：無論初始狀態(tài)如何，在第i趟排序中選擇最小關(guān)鍵碼的元素，需做n-i次比較，因此總的比較次數(shù)為：算法的空間效率：空間效率很高，只需要一個(gè)附加程序單元用于交換，其空間效率為算法的穩(wěn)定性：不穩(wěn)定直接選擇排序效率分析常用的內(nèi)部排序選擇排序直接選擇排序、堆排序交換排序冒泡排序、快速排序插入排序直接插入排

9、序、折半插入排序、Shell排序歸并排序桶式排序基數(shù)排序堆排序HeapSort.java算法的時(shí)間效率：假設(shè)有n個(gè)數(shù)據(jù)，需要進(jìn)行n-1次建堆，每次建堆本身耗時(shí) ，則其時(shí)間效率為算法的空間效率：空間效率很高，只需要一個(gè)附加程序單元用于交換，其空間效率為算法的穩(wěn)定性：不穩(wěn)定堆排序效率分析常用的內(nèi)部排序選擇排序直接選擇排序、堆排序交換排序冒泡排序、快速排序插入排序直接插入排序、折半插入排序、Shell排序歸并排序桶式排序基數(shù)排序冒泡排序排序思想：相鄰兩元素進(jìn)行比較，如有需要?jiǎng)t進(jìn)行交換，每完成一次循環(huán)就將最大元素排在最后（如從小到大排序），下一次循環(huán)是將其它的數(shù)進(jìn)行類似操作。BubbleSort.ja

10、va算法的時(shí)間效率：從冒泡排序的算法可以看出，若待排序的元素為正序，則只需進(jìn)行一趟排序，比較次數(shù)為n-1次，移動(dòng)元素次數(shù)為0；若待排序的元素為逆序，則需要進(jìn)行n-1趟排序，比較次數(shù)為 ，移動(dòng)次數(shù)為 ，因此時(shí)間復(fù)雜度為算法的空間效率：空間效率很高，只需要一個(gè)附加程序單元用于交換，其空間效率為算法的穩(wěn)定性：穩(wěn)定冒泡排序效率分析常用的內(nèi)部排序選擇排序直接選擇排序、堆排序交換排序冒泡排序、快速排序插入排序直接插入排序、折半插入排序、Shell排序歸并排序桶式排序基數(shù)排序QuickSort.java算法的時(shí)間效率：時(shí)間效率很好，因?yàn)槊刻四艽_定的元素都呈指數(shù)增長(zhǎng)，故時(shí)間復(fù)雜度為算法的空間效率：由于使用遞歸

11、，而遞歸使用棧，因此空間效率最優(yōu)時(shí)為算法的穩(wěn)定性：由于包含跳躍式交換，因此不穩(wěn)定快速排序效率分析常用的內(nèi)部排序選擇排序直接選擇排序、堆排序交換排序冒泡排序、快速排序插入排序直接插入排序、折半插入排序、Shell排序歸并排序桶式排序基數(shù)排序InsertSort.java算法的時(shí)間效率：在最壞的情況下，所有元素的比較次數(shù)總和為（0+1+2+n-1）= ；在其他情況下，也要考慮移動(dòng)元素的次數(shù)，故時(shí)間復(fù)雜度為算法的空間效率：空間效率很高，只需要一個(gè)附加程序單元用于交換，其空間效率為算法的穩(wěn)定性：穩(wěn)定直接插入排序效率分析常用的內(nèi)部排序選擇排序直接選擇排序、堆排序交換排序冒泡排序、快速排序插入排序直接插入

12、排序、折半插入排序、Shell排序歸并排序桶式排序基數(shù)排序折半插入排序折半插入排序是對(duì)直接插入排序的簡(jiǎn)單改進(jìn)。此處介紹的折半插入，其實(shí)就是通過不斷地折半來快速確定第i個(gè)元素的插入位置，這實(shí)際上是一種查找算法：折半查找。Java的Arrays類里的binarySearch()方法，就是折半查找的實(shí)現(xiàn)，用于從指定數(shù)組中查找指定元素，前提是該數(shù)組已經(jīng)處于有序狀態(tài)。與直接插入排序的效果相同，只是更快了一些，因?yàn)檎郯氩迦肱判蚩梢愿斓卮_定第i個(gè)元素的插入位置BinaryInsertSort.java常用的內(nèi)部排序選擇排序直接選擇排序、堆排序交換排序冒泡排序、快速排序插入排序直接插入排序、折半插入排序、S

13、hell排序歸并排序桶式排序基數(shù)排序ShellSort.java算法的時(shí)間效率：開銷估計(jì)在 之間算法的空間效率：空間效率很高，只需要一個(gè)附加程序單元用于交換，其空間效率為算法的穩(wěn)定性：不穩(wěn)定 Shell排序效率分析常用的內(nèi)部排序選擇排序直接選擇排序、堆排序交換排序冒泡排序、快速排序插入排序直接插入排序、折半插入排序、Shell排序歸并排序桶式排序基數(shù)排序MergeSort.java算法的時(shí)間效率：歸并算法需要遞歸地進(jìn)行分解、合并，每進(jìn)行一趟歸并排序，需要merge()方法一次，每次執(zhí)行merge()需要比較n次，故復(fù)雜度為算法的空間效率：較差，需要一個(gè)與原始序列同樣大小的輔助序列算法的穩(wěn)定性：

14、穩(wěn)定歸并排序效率分析常用的內(nèi)部排序選擇排序直接選擇排序、堆排序交換排序冒泡排序、快速排序插入排序直接插入排序、折半插入排序、Shell排序歸并排序桶式排序基數(shù)排序桶式排序桶式排序不再是一種基于比較的排序方法，它是一種非常巧妙的排序方式，但這種排序方式需要待排序列滿足如下兩個(gè)特征：待排序列的所有值處于一個(gè)可枚舉范圍內(nèi)待排序列所在的這個(gè)可枚舉范圍不應(yīng)該太大，否則排序開銷太大以下為例：5，4，2，4，1 使用桶式排序BucketSort.java算法的時(shí)間效率：時(shí)間效率極高，只需經(jīng)過兩輪遍歷即可算法的空間效率：空間開銷較大，需要兩個(gè)數(shù)組來完成算法的穩(wěn)定性：穩(wěn)定桶式排序效率分析常用的內(nèi)部排序選擇排序直

15、接選擇排序、堆排序交換排序冒泡排序、快速排序插入排序直接插入排序、折半插入排序、Shell排序歸并排序桶式排序基數(shù)排序基數(shù)排序基數(shù)排序已經(jīng)不再是一種常規(guī)的排序方法，它更多地像是一種排序方法的應(yīng)用，基數(shù)排序必須依賴于另外的排序方法?；鶖?shù)排序的總體思路就是將待排數(shù)據(jù)拆分成多個(gè)關(guān)鍵字進(jìn)行排序，也就是說，基數(shù)排序的實(shí)質(zhì)是多關(guān)鍵字排序。多關(guān)鍵字排序的思路是將待排數(shù)據(jù)里的排序關(guān)鍵字拆分成多個(gè)排序關(guān)鍵字：第1個(gè)子關(guān)鍵字、第2個(gè)子關(guān)鍵字、第3個(gè)子關(guān)鍵字。然后，根據(jù)子關(guān)鍵字對(duì)待排數(shù)據(jù)進(jìn)行排序。在進(jìn)行多關(guān)鍵字排序時(shí)有兩種解決方案：最高位優(yōu)先法MSD最低位優(yōu)先法LSDMultiKeyRadixSort.javaMS

16、D法和LSD法的比較比較MSD法和LSD法，一般來講，LSD法要比MSD法來得簡(jiǎn)單，因?yàn)長(zhǎng)SD法是從頭到尾進(jìn)行若干次分配和收集，執(zhí)行的次數(shù)取決于構(gòu)成關(guān)鍵字值的成分為多少；而MSD法則要處理各序列與子序列的獨(dú)立排序問題，就可能復(fù)雜一些。各種內(nèi)部排序方法性能比較1.從平均時(shí)間而言：快速排序最佳。但在最壞情況下時(shí)間性能不如堆排序和歸并排序。2.從算法簡(jiǎn)單性看：由于直接選擇排序、直接插入排序和冒泡排序的算法比較簡(jiǎn)單，將其認(rèn)為是簡(jiǎn)單算法，都包含在上圖的“簡(jiǎn)單排序”中。對(duì)于Shell排序、堆排序、快速排序和歸并排序算法，其算法比較復(fù)雜，認(rèn)為是復(fù)雜排序。3.從穩(wěn)定性看：直接插入排序、冒泡排序和歸并排序時(shí)穩(wěn)定

17、的；而直接選擇排序、快速排序、 Shell排序和堆排序是不穩(wěn)定排序4.從待排序的記錄數(shù)n的大小看，n較小時(shí)，宜采用簡(jiǎn)單排序；而n較大時(shí)宜采用改進(jìn)排序。排序方法的選擇(1)若n較小(如n50)，可采用直接插入或直接選擇排序。 當(dāng)記錄規(guī)模較小時(shí)，直接插入排序較好；否則因?yàn)橹苯舆x擇移動(dòng)的記錄數(shù)少于直接插入，應(yīng)選直接選擇排序?yàn)橐恕?2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插入、冒泡或隨機(jī)的快速排序?yàn)橐耍?3)若n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。數(shù)組排序java.util.Arrays類的sort()方法提供了數(shù)組元素排序功能：import java.util.*;public class Sort public static void main(Strin