Java資料結構與演算法之排序（堆排序、計數排序、桶排序）

1。堆排序

1。1二叉堆概念以及原理

二叉堆本質上是一種完全二叉樹，它分為兩個型別：大頂堆和小頂堆

大頂堆（最大堆）

最大堆的任何一個父節點的值，都大於或等於它左、右孩子節點的值。

小頂堆（最小堆）

最小堆的任何一個父節點的值，都小於或等於它左、右孩子節點的值。

二叉堆的根節點叫作

堆頂

，最大堆和最小堆的特點決定了：最大堆的堆頂是整個堆中的最大元素；最小堆的堆頂是整個堆中的最小元素。

儲存原理

完全二叉樹比較適合用

陣列

來儲存。用陣列來儲存完全二叉樹是非常節省儲存空間的。因為我們不需要儲存左右子節點的指標，

單純地透過陣列的下標，就可以找到一個節點的左右子節點和父節點

。

陣列中下標為

i 的節點的左子節點，就是下標為 i2 的節點，右子節點就是下標為 i2+1 的節點

，

父節點就是下標為 i/2 取整的節點

（儲存資料從陣列下標1開始的，也可以從0開始）

1。2 堆排序

陣列從邏輯上講就是一個堆結構，我們用簡單的公式來描述一下堆的定義就是：

大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 2*(i+1)

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

堆排序的基本思想

將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。將其與末尾元素進行交換，此時末尾就為最大值。然後將剩餘n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反覆執行，便能得到一個有序序列了。

排序過程如下：

1。將給定無序序列構造成一個大頂堆（升序用大頂堆，降序用小頂堆）

2。然後從最後一個非葉子節點開始（

最後一個非葉子節點 的index=arr.length/2-1

），從左至右，從下至上依次次調整。

3。找到第二個非葉節點4，由於［4，9，8］中9元素最大，4和9交換

4。這時，交換導致了子根［4，5，6］結構混亂，繼續調整，［4，5，6］中6最大，交換4和6

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

重新調整結構，使其繼續滿足堆定義

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

如此反覆最終使得整個序列有序。

1。3 堆排序程式碼實現

public class HeapSort {

public static void sort（int［］ arr）{

//1。構建大頂堆

for （int i=arr。length/2-1；i>=0；i——）{

//從最後一個非葉子節點開始

adjustHeap（arr，i，arr。length）；

}

//2。大頂堆首尾元素交換，重複構建

for （int i = arr。length - 1； i > 0； i——）{

// 最後1個元素和第1個元素進行交換

int temp = arr［i］；

arr［i］ = arr［0］；

arr［0］ = temp；

// “下沉”調整最大堆

adjustHeap（arr， 0， i）；

}

}

private static void adjustHeap（int［］ arr， int parentIndex， int length） {

//temp儲存父節點的值

int temp=arr［parentIndex］；

//左子節點的index

int childIndex=2*parentIndex+1；

while （childIndex

//此邏輯是獲取2個子節點的最大的一個，如果不走if 說明左子節點大，反之右節點大

if （childIndex+1arr［childIndex］）{

//如果存在右子節點，而且右子節點比左子節點大

childIndex++；

}

//如果temp大就不用比 直接跳出

if （temp>arr［childIndex］） break；

//交換

arr［parentIndex］=arr［childIndex］；

//將當前最大子節點的index 作為父節點繼續迴圈

parentIndex=childIndex；

//下一個孩子節點

childIndex=2*childIndex+1；

}

arr［parentIndex］ = temp；

}

public static void main（String ［］args）{

int ［］arr = {7，6，4，3，5，2，10，9，8}；

System。out。println（“排序前：”+ Arrays。toString（arr））；

sort（arr）；

System。out。println（“排序後：”+ Arrays。toString（arr））；

}

}

測試輸出：

小結：

時間複雜度：O（nlogn）

跟快排時間複雜度是一樣的，但是這個思路感覺相對複雜，程式碼邏輯需要從前面排序原理對比著來看，才能看出每一步的作用。

1。4 堆的應用

優先佇列，求Top K等等。

2。計數排序

2。1概念和原理

計數排序，這種排序演算法是利用陣列下標來確定元素的正確位置的，這種排序的侷限性比較大，適合於連續的取值範圍不大的陣列（通常都是整數）。

排序原理過程

假設陣列中有10個整數，取值範圍為0～10，可以根據有限的範圍，建一個長度為11的陣列，陣列下標從0到10，元素初始值為0。

假設待排序的陣列為：9，1，2，7，8，1，3，6，5，3

遍歷這個陣列，每個元素的值對應的新建陣列的下標+1，例如第一個數是9，那麼陣列下標9的數值+1，

依次遍歷下去，最終得到的陣列資料為：

然後再遍歷陣列，輸出元素下標，下標對應的數值是多少，就輸出幾次，輸出結果為：1、1、2、3、3、5、6、7、8、9 。

注意

：

不連續和取值範圍過大會造成陣列過大

，如果起始不是0，比如考試分數，可以採取偏移量的方式來節約陣列空間。

2。2 程式碼實現

以考試分數 90分以上的分數的陣列作為案例來實現計數排序。

public class CountSort {

public static int［］ sort（int［］ arr，int offset）{

int［］ temp=new int［11］；

//計數

for （int n ： arr） {

int i=n-offset；

temp［i］++；

}

//填充新陣列

int［］ result=new int［arr。length］；

// i是計數陣列下標，k是新陣列下標

for （int i = 0， k = 0； i < temp。length； i++） {

for （int j = 0； j < temp［i］； j++） {

result［k++］ = i + offset；

}

}

return result；

}

public static void main（String［］ args） {

int［］ scores = {95， 94， 91， 98， 99， 90， 99， 93， 91， 92}；

System。out。println（“排序前的陣列：”+ Arrays。toString（scores））；

int［］ sort = sort（scores， 90）；

System。out。println（“排序後的陣列：”+ Arrays。toString（sort））；

}

}

測試輸出：

小結：

時間複雜度 O（m+n），在特定情況下使用計數排序，效率還是相當不錯的。

3。 桶排序

3。1 概念和原理

桶排序也是一種線性時間的排序演算法，桶排序需要建立若干個桶來協助排序，每一個桶（bucket）代表一個區間範圍，裡面可以承載一個或多個元素。

排序過程

第1步，建立這些桶，並確定每一個桶的區間範圍具體需要建立多少個桶

確定桶的區間範圍，有很多種不同的方式。可以選擇：

建立的桶數量等於原始數列的元素數量

，除最後一個桶只包 含數列最大值外， 前面各個桶的區間按照比例來確定。

區間跨度 = （最大值-最小值）/ （桶的數量 - 1）

假設有一個非整數數列：4。5，0。84，3。25，2。18，0。5

第2步，遍歷原始數列，把元素對號入座放入各個桶中

第3步，對每個桶內部的元素分別進行排序（這裡只需對第一個桶進行排序）

第4步，遍歷所有的桶，輸出所有元素

0。5，0。84，2。18，3。25，4。5

3。2 程式碼實現

public class BucketSort {

public static double［］ bucketSort（double［］ array） {

double max = 0；

double min = 0；

//獲得最大值和最小值之間的差

for （int i = 0； i < array。length； i++） {

if （array［i］ > max） {

max = array［i］；

} if （array［i］ < min） {

min = array［i］；

}

}

double d = max - min；

//桶初始化

int bucketNum = array。length；

ArrayList> bucketList =new ArrayList<>（bucketNum）；

for （int i = 0； i < bucketNum； i++） {

bucketList。add（new LinkedList<>（））；

} //將每個元素放入桶中

for （int i = 0； i < array。length； i++） {

int num = （int） （（array［i］ - min） * （bucketNum - 1） / d）；

bucketList。get（num）。add（array［i］）；

} //對每個桶內部進行排序

for （int i = 0； i < bucketList。size（）； i++） {

Collections。sort（bucketList。get（i））；

} //輸出全部元素

double［］ sortedArray = new double［array。length］；

int index = 0；

for （LinkedList list ： bucketList） {

for （double element ： list） {

sortedArray［index］ = element；

index++；

}

}

return sortedArray；

}

public static void main（String［］ args） {

double［］ array = {4。12， 6。421， 0。0023， 3。0， 2。123， 8。122， 4。12， 10。09}；

System。out。println（“排序前：”+Arrays。toString（array））；

double［］ sortedArray = bucketSort（array）；

System。out。println（“排序後：”+Arrays。toString（sortedArray））；

}

}

測試效果：

時間複雜度：O（n）

3。3 幾種排序對比