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

動圖展示：

17.2代碼實現(xiàn)

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){

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

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

//循環(huán)調整為大頂堆

for(inti=start;ii--){

maxHeap(arr,arr.length,i);

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

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

inttemp=arr[0];

arr[0]=arr[i];

arr[i]=temp;

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

maxHeap(arr,i,0);

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

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

//左子節(jié)點

intleftNode=2*index+1;

//右子節(jié)點

intrightNode=2*index+2;

//先設當前為最大節(jié)點

intmax=index;

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

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時間復雜度

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

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

穩(wěn)定性：不穩(wěn)定

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

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

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

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

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

第18章計數(shù)排序

18.1計數(shù)排序概念

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

排序步驟：

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

統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項；

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

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

動圖展示：

18.2代碼實現(xiàn)

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]

//計數(shù)排序

publicstaticvoidsortCount(int[]arr){

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

intmax=arr[0];

intmin=arr[0];

intlen=arr.length;

for(inti:arr){

if(imax){

max=i;

if(imin){

min=i;

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

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

//三.循環(huán)遍歷舊數(shù)組計數(shù)排序:就是統(tǒng)計原始數(shù)組值出現(xiàn)的頻率到中間數(shù)組temp中

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

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

//四、遍歷輸出

//先循環(huán)每一個元素在計數(shù)排序器的下標中

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

intitem=temp[i];

循環(huán)出現(xiàn)的次數(shù)

while(item--!=0){

//以為原來減少了min現(xiàn)在加上min，值就變成了原來的值

arr[index++]=i+min;

}}

18.3時間復雜度

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

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

穩(wěn)定性：不穩(wěn)定

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

第19章桶排序

19.1桶排序概念

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

排序步驟：

設置一個定量的數(shù)組當作空桶；

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

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

從不是空的桶里把排好序的數(shù)據(jù)拼接起來

動圖展示：

靜圖展示：

19.2代碼實現(xiàn)

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]);

//創(chuàng)建初始的桶

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]);//根據(jù)商的不同，放入不同的桶

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

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

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

}}

19.3時間復雜度

最優(yōu)時間復雜度：o(n)

最壞時間復雜度：o(n^2)

穩(wěn)定性：穩(wěn)定

對于桶排序來說，分配過程的時間是O(n)；收集過程的時間為O(k)（采用鏈表來存儲輸入的待排序記錄）。因此，桶排序的時間為O(n+k)。若桶個數(shù)m的數(shù)量級為O(n)，則桶排序的時間是線性的，最優(yōu)即O(n)。

前面說的幾大排序算法，大部分時間復雜度都是O(n2)，也有部分排序算法時間復雜度是O(nlogn)。而桶式排序卻能實現(xiàn)O(n)的時間復雜度。但桶排序的缺點是：首先是空間復雜度比較高，需要的額外開銷大。排序有兩個數(shù)組的空間開銷，一個存放待排序數(shù)組，一個就是所謂的桶，比如待排序值是從0到m-1，那就需要m個桶，這個桶數(shù)組就要至少m個空間。其次待排序的元素都要在一定的范圍內等等。

第20章基數(shù)排序

20.1基數(shù)排序概念

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

排序步驟：

取得數(shù)組中的最大數(shù)，并取得位數(shù)；

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

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

動圖展示：

靜圖分析：

20.2代碼實現(xiàn)

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]

//基數(shù)排序

publicstaticvoidradixSort(int[]arr){

//定義臨時二維數(shù)組表示十個桶

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

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

int[]counts=newint[10];

//存數(shù)組中最大的數(shù)字

intmax=Integer.MIN_VALUE;

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

if(arr[i]max){

max=arr[i];

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

intmaxLength=(max+).length();

//根據(jù)最大長度的數(shù)決定比較的次數(shù)

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

//把每一個數(shù)字分別計算余數(shù)

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

//計算余數(shù)

intys=arr[j]/n%10;

//把當前遍歷的數(shù)據(jù)放入指定的數(shù)組中

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

//記錄數(shù)量

counts[ys]++;

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

intindex=0;