轉(zhuǎn)載自https://baijiahao.baidu.com/s?id=1675247850928846451&wfr=spider&for=pc
常見數(shù)據(jù)結(jié)構(gòu)
一、數(shù)組
數(shù)據(jù)是有限個(gè)相同類型的變量所組成的有序集合。數(shù)組中的每一個(gè)變量被稱為元素。
二、 鏈表
鏈表是一種在物理上非連續(xù)、非順序的數(shù)據(jù)結(jié)構(gòu)，由若干個(gè)節(jié)點(diǎn)組成。
單向鏈表的每一個(gè)節(jié)點(diǎn)又包含兩部分，一部分是存放數(shù)據(jù)的變量data，另一部分是指向下一個(gè)節(jié)點(diǎn)的指針next。
- 鏈表 VS 數(shù)組
數(shù)組：適合多讀、插入刪除少的場景。
鏈表：適用于插入刪除多、讀少的場景
三、棧
棧是一種線性邏輯數(shù)據(jù)結(jié)構(gòu)，棧的元素只能后進(jìn)先出。最早進(jìn)入的元素存放的位置叫做棧底，最后進(jìn)入的元素存放的位置叫棧頂。
一個(gè)比喻，棧是一個(gè)一端封閉一端的開放的中空管子，隊(duì)列是兩端開放的中空管子。
四、隊(duì)列
這一種線性邏輯數(shù)據(jù)結(jié)構(gòu)，隊(duì)列的元素只能后進(jìn)后出。隊(duì)列的出口端叫做隊(duì)頭，隊(duì)列的入口端叫做隊(duì)尾。
五、哈希表
哈希表是一種邏輯數(shù)據(jù)結(jié)構(gòu)，提供了鍵（key）和值（value）的映射關(guān)系。
哈希表本質(zhì)上是一個(gè)數(shù)組，只是數(shù)組只能根據(jù)下標(biāo)，像a[0] a[1] a[2] a[3] 這樣來訪問，而哈希表的key則是以字符串類型為主的。通過哈希函數(shù)，我們可以把字符串或其他類型的key，轉(zhuǎn)化成數(shù)組的下標(biāo)index。如給出一個(gè)長度為8的數(shù)組，則：
當(dāng)key=001121時(shí)，
index = HashCode ("001121") % Array.length = 7
當(dāng)key=this時(shí)，
index = HashCode ("this") % Array.length = 6
六、樹
樹（tree）是n（n≥0）個(gè)節(jié)點(diǎn)的有限集。
當(dāng)n=0時(shí)，稱為空樹。在任意一個(gè)非空樹中，有如下特點(diǎn)：
有且僅有一個(gè)特定的稱為根的節(jié)點(diǎn)。
當(dāng)n>1時(shí)，其余節(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集，每一個(gè)集合本身又是一個(gè)樹，并稱為根的子樹。
- 樹的遍歷？
（1）深度優(yōu)先
前序：根節(jié)點(diǎn)、左子樹、右子樹。
中序：左子樹、根節(jié)點(diǎn)、右子樹。
后序：左子樹、右子樹、根節(jié)點(diǎn)。
實(shí)現(xiàn)方式：遞歸或棧。
（2）廣度優(yōu)先
層序：一層一層遍歷。
實(shí)現(xiàn)方式：隊(duì)列。
七、二叉樹
二叉樹（binary tree）是樹的一種特殊形式。二叉，顧名思義，這種樹的每個(gè)節(jié)點(diǎn)最多有2個(gè)孩子節(jié)點(diǎn)。注意，這里是最多有2個(gè)，也可能只有1個(gè)，或者沒有孩子節(jié)點(diǎn)。
滿二叉樹是指一個(gè)二叉樹的所有非葉子節(jié)點(diǎn)都存在左右孩子，并且所有葉子節(jié)點(diǎn)都在同一層級上，那么這個(gè)樹就是滿二叉樹。
完全二叉樹則是對一個(gè)有n個(gè)節(jié)點(diǎn)的二叉樹，按層級順序編號，則所有節(jié)點(diǎn)的編號為從1到n。如果這個(gè)樹所有節(jié)點(diǎn)和同樣深度的滿二叉樹的編號為從1到n的節(jié)點(diǎn)位置相同，則這個(gè)二叉樹為完全二叉樹。
八、二叉查找樹
二叉查找樹在二叉樹的基礎(chǔ)上增加了以下幾個(gè)條件：
如果左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值。
如果右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值。
左、右子樹也都是二叉查找樹。
九、二叉堆
二叉堆是一種特殊的完全二叉樹，它分為兩個(gè)類型：最大堆和最小堆。
最大堆的任何一個(gè)父節(jié)點(diǎn)的值，都大于或等于它左、右孩子節(jié)點(diǎn)的值。
最小堆的任何一個(gè)父節(jié)點(diǎn)的值，都小于或等于它左、右孩子節(jié)點(diǎn)的值。
常見排序算法
這是十大經(jīng)典排序算法，下面將簡要介紹其中的冒泡排序、歸并排序、快速排序、堆排序和桶排序算法，最后對十大常見算法做一個(gè)簡單的性能對比分析。
1 冒泡排序
冒泡排序是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)。
- 針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
- 重復(fù)步驟1~3，直到排序完成。
2 歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個(gè)非常典型的應(yīng)用。遞歸的把當(dāng)前序列分割成兩半（分割），在保持元素順序的同時(shí)將上一步得到的子序列集成到一起（歸并），最終形成一個(gè)有序數(shù)列。
- 把長度為n的輸入序列分成兩個(gè)長度為n/2的子序列。
- 對這兩個(gè)子序列分別采用歸并排序。
- 將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。
3 快速排序
快速排序使用分治法策略來把一個(gè)序列分為較小和較大的2個(gè)子序列，然后遞歸地排序兩個(gè)子序列，以達(dá)到整個(gè)數(shù)列最終有序。
- 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)值”（pivot）。
- 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。
- 遞歸地對【小于基準(zhǔn)值元素的子數(shù)列】和【大于基準(zhǔn)值元素的子數(shù)列】進(jìn)行排序。
4 堆排序
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
- 將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成最大堆，此堆為初始的無序區(qū)。
- 將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]。
- 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對當(dāng)前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個(gè)元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過程完成。
5 計(jì)數(shù)排序
計(jì)數(shù)排序不是基于比較的排序算法，其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
- 找出待排序的數(shù)組中最大元素。
- 構(gòu)建一個(gè)數(shù)組C，長度為最大元素值+1。
- 遍歷無序的隨機(jī)數(shù)列，每一個(gè)整數(shù)按照其值對號入座，對應(yīng)數(shù)組下標(biāo)的值加1。
- 遍歷數(shù)組C，輸出數(shù)組元素的下標(biāo)值，元素的值是幾就輸出幾次。
6 桶排序
桶排序是計(jì)數(shù)排序的升級版。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。實(shí)現(xiàn)原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里，每個(gè)桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。
- 創(chuàng)建桶，區(qū)間跨度=(最大值-最小值)/(桶的數(shù)量-1)。
- 遍歷數(shù)列，對號入座。
- 每個(gè)桶內(nèi)進(jìn)行排序，可選擇快排等。
- 遍歷所有的桶，輸出所有元素。
7 性能對比
隨機(jī)生成區(qū)間0 ~ K之間的序列，共計(jì)N個(gè)數(shù)字，利用各種算法進(jìn)行排序，記錄排序所需時(shí)間。
