第圖文詳解Java數據結構與算法重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，反復執行調整+交換步驟，直到整個序列有序

動圖展示：

17.2代碼實現

importjava.util.Arrays;publicclassHeapSort{

publicstaticvoidmain(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]

//堆排序

publicstaticvoidheapSort(int[]arr){

//開始位置是最后一個非葉子節點（最后一個節點的父節點）

intstart=(arr.length-1)/2;

//循環調整為大頂堆

for(inti=start;ii--){

maxHeap(arr,arr.length,i);

//先把數組中第0個和堆中最后一個交換位置

for(inti=arr.length-1;ii--){

inttemp=arr[0];

arr[0]=arr[i];

arr[i]=temp;

//再把前面的處理為大頂堆

maxHeap(arr,i,0);

//數組轉大頂堆,size:調整多少（從最后一個向前減），index:調整哪一個（最后一個非葉子節點）

publicstaticvoidmaxHeap(int[]arr,intsize,intindex){

//左子節點

intleftNode=2*index+1;

//右子節點

intrightNode=2*index+2;

//先設當前為最大節點

intmax=index;

//和兩個子節點分別對比，找出最大的節點

if(leftNodesizearr[leftNode]arr[max]){

max=leftNode;

if(rightNodesizearr[rightNode]arr[max]){

max=rightNode;

//交換位置

if(max!=index){

inttemp=arr[index];

arr[index]=arr[max];

arr[max]=temp;

//交換位置后，可能會破壞之前排好的堆，所以之間排好的堆需要重新調整

maxHeap(arr,size,max);

//打印每次排序后的結果

System.out.println(Arrays.toString(arr));

}}

17.3時間復雜度

最優時間復雜度：o(nlogn)

最壞時間復雜度：o(nlogn)

穩定性：不穩定

它的運行時間主要是消耗在初始構建堆和在重建堆時的反復篩選上。

在構建堆的過程中，因為我們是完全二叉樹從最下層最右邊的非終端結點開始構建，將它與其孩子進行比較和若有必要的互換，對于每個非終端結點來說，其實最多進行兩次比較和互換操作，因此整個構建堆的時間復雜度為O(n)。

在正式排序時，第i次取堆頂記錄重建堆需要用O(logi)的時間（完全二叉樹的某個結點到根結點的距離為log2i＋1），并且需要取n-1次堆頂記錄，因此，重建堆的時間復雜度為O(nlogn)。

所以總體來說，堆排序的時間復雜度為O(nlogn)。由于堆排序對原始記錄的排序狀態并不敏感，因此它無論是最好、最壞和平均時間復雜度均為O(nlogn)。這在性能上顯然要遠遠好過于冒泡、簡單選擇、直接插入的O(n2)的時間復雜度了。

空間復雜度上，它只有一個用來交換的暫存單元，也非常的不錯。不過由于記錄的比較與交換是跳躍式進行，因此堆排序是一種不穩定的排序方法。

第18章計數排序

18.1計數排序概念

計數排序（CountingSort）不是基于比較的排序算法，其核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

排序步驟：

找出待排序的數組中最大和最小的元素；

統計數組中每個值為i的元素出現的次數，存入數組C的第i項；

對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；

反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1

動圖展示：

18.2代碼實現

importjava.util.Arrays;publicclassCountingSort{

publicstaticvoidmain(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]

//計數排序

publicstaticvoidsortCount(int[]arr){

//一：求取最大值和最小值，計算中間數組的長度：

intmax=arr[0];

intmin=arr[0];

intlen=arr.length;

for(inti:arr){

if(imax){

max=i;

if(imin){

min=i;

//二、有了最大值和最小值能夠確定中間數組的長度（中間數組是用來記錄原始數據中每個值出現的頻率）

int[]temp=newint[max-min+1];

//三.循環遍歷舊數組計數排序:就是統計原始數組值出現的頻率到中間數組temp中

for(inti=0;ilen;i++){

temp[arr[i]-min]+=1;

//四、遍歷輸出

//先循環每一個元素在計數排序器的下標中

for(inti=0,index=0;itemp.length;i++){

intitem=temp[i];

循環出現的次數

while(item--!=0){

//以為原來減少了min現在加上min，值就變成了原來的值

arr[index++]=i+min;

}}

18.3時間復雜度

最優時間復雜度：o(n+k)

最壞時間復雜度：o(n+k)

穩定性：不穩定

計數排序是一個穩定的排序算法。當輸入的元素是n個0到k之間的整數時，時間復雜度是O(n+k)，空間復雜度也是O(n+k)，其排序速度快于任何比較排序算法。當k不是很大并且序列比較集中時，計數排序是一個很有效的排序算法

第19章桶排序

19.1桶排序概念

桶排序（Bucketsort）或所謂的箱排序，是一個排序算法，工作的原理是將數組分到有限數量的桶里。每個桶再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序），最后依次把各個桶中的記錄列出來記得到有序序列。桶排序是鴿巢排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間o(n)。但桶排序并不是比較排序，他不受到O(nlogn)下限的影響。

排序步驟：

設置一個定量的數組當作空桶；

遍歷輸入數據，并且把數據一個一個放到對應的桶里去；

對每個不是空的桶進行排序；

從不是空的桶里把排好序的數據拼接起來

動圖展示：

靜圖展示：

19.2代碼實現

packagesort;importjava.util.ArrayList;importjava.util.Collections;publicclassBucketSort{

publicstaticvoidmain(String[]args){

int[]arr={29,25,3,49,9,37,21,43};

bucketSort(arr);

//分桶后結果為:[[3,9],[],[21,25],[29],[37],[43,49]]

publicstaticvoidbucketSort(int[]arr){

//大的當小的，小的當大的

intmax=Integer.MIN_VALUE;

intmin=Integer.MAX_VALUE;

//找出最小最大值

for(inti=0,len=arr.length;ii++){

max=Math.max(max,arr[i]);

min=Math.min(min,arr[i]);

//創建初始的桶

intbucketNum=(max-min)/arr.length+1;

ArrayListArrayListIntegerbucketArr=newArrayList(bucketNum);

//這一步是不可缺少的，上面的初始化只初始化了一維列表。二維列表需額外初始化

for(inti=0;ibucketNum;i++){

bucketArr.add(newArrayList());

for(inti=0,len=arr.length;ii++){

intnum=(arr[i]-min)/arr.length;//相同的商在同一個桶中

bucketArr.get(num).add(arr[i]);//根據商的不同，放入不同的桶

for(inti=0;ibucketArr.size();i++){//同一桶內，自己排序

Collections.sort(bucketArr.get(i));

System.out.println(分桶后結果為:+bucketArr.toString());

}}

19.3時間復雜度

最優時間復雜度：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個空間。其次待排序的元素都要在一定的范圍內等等。

第20章基數排序

20.1基數排序概念

基數排序（RadixSort）是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前

排序步驟：

取得數組中的最大數，并取得位數；

arr為原始數組，從最低位開始取每個位組成radix數組；

對radix進行計數排序（利用計數排序適用于小范圍數的特點）

動圖展示：

靜圖分析：

20.2代碼實現

importjava.util.Arrays;publicclassRadixSort{

publicstaticvoidmain(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]

//基數排序

publicstaticvoidradixSort(int[]arr){

//定義臨時二維數組表示十個桶

int[][]temp=newint[10][arr.length];

//定義一個一維數組，用于記錄在temp中相應的數組中存放數字的數量

int[]counts=newint[10];

//存數組中最大的數字

intmax=Integer.MIN_VALUE;

for(inti=0;iarr.length;i++){

if(arr[i]max){

max=arr[i];

//計算最大數字是幾位數（才能知道排序次數）

intmaxLength=(max+).length();

//根據最大長度的數決定比較的次數

for(inti=0,n=1;imaxLength;i++,n*=10){

//把每一個數字分別計算余數

for(intj=0;jarr.length;j++){

//計算余數

intys=arr[j]/n%10;

//把當前遍歷的數據放入指定的數組中

temp[ys][counts[ys]]=arr[j];

//記錄數量

counts[ys]++;

//記錄取的元素需要放的位置

intindex=0;