圖文詳解Java數(shù)據(jù)結(jié)構(gòu)與算法

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

動(dòng)圖展示：

17.2代碼實(shí)現(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){

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

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

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

for(inti=start;ii--){

maxHeap(arr,arr.length,i);

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

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

inttemp=arr[0];

arr[0]=arr[i];

arr[i]=temp;

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

maxHeap(arr,i,0);

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

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

//左子節(jié)點(diǎn)

intleftNode=2*index+1;

//右子節(jié)點(diǎn)

intrightNode=2*index+2;

//先設(shè)當(dāng)前為最大節(jié)點(diǎn)

intmax=index;

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

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;

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

maxHeap(arr,size,max);

//打印每次排序后的結(jié)果

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

}}

17.3時(shí)間復(fù)雜度

最優(yōu)時(shí)間復(fù)雜度：o(nlogn)

最壞時(shí)間復(fù)雜度：o(nlogn)

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

它的運(yùn)行時(shí)間主要是消耗在初始構(gòu)建堆和在重建堆時(shí)的反復(fù)篩選上。

在構(gòu)建堆的過程中，因?yàn)槲覀兪峭耆鏄鋸淖钕聦幼钣疫叺姆墙K端結(jié)點(diǎn)開始構(gòu)建，將它與其孩子進(jìn)行比較和若有必要的互換，對于每個(gè)非終端結(jié)點(diǎn)來說，其實(shí)最多進(jìn)行兩次比較和互換操作，因此整個(gè)構(gòu)建堆的時(shí)間復(fù)雜度為O(n)。

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

所以總體來說，堆排序的時(shí)間復(fù)雜度為O(nlogn)。由于堆排序?qū)υ加涗浀呐判驙顟B(tài)并不敏感，因此它無論是最好、最壞和平均時(shí)間復(fù)雜度均為O(nlogn)。這在性能上顯然要遠(yuǎn)遠(yuǎn)好過于冒泡、簡單選擇、直接插入的O(n2)的時(shí)間復(fù)雜度了。

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

第18章計(jì)數(shù)排序

18.1計(jì)數(shù)排序概念

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

排序步驟：

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

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

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

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

動(dòng)圖展示：

18.2代碼實(shí)現(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]

//計(jì)數(shù)排序

publicstaticvoidsortCount(int[]arr){

//一：求取最大值和最小值，計(jì)算中間數(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ù)中每個(gè)值出現(xiàn)的頻率）

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

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

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

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

//四、遍歷輸出

//先循環(huán)每一個(gè)元素在計(jì)數(shù)排序器的下標(biāo)中

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時(shí)間復(fù)雜度

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

最壞時(shí)間復(fù)雜度：o(n+k)

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

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

第19章桶排序

19.1桶排序概念

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

排序步驟：

設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶；

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

對每個(gè)不是空的桶進(jìn)行排序；

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

動(dòng)圖展示：

靜圖展示：

19.2代碼實(shí)現(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);

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

publicstaticvoidbucketSort(int[]arr){

//大的當(dāng)小的，小的當(dāng)大的

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;//相同的商在同一個(gè)桶中

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

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

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

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

}}

19.3時(shí)間復(fù)雜度

最優(yōu)時(shí)間復(fù)雜度：o(n)

最壞時(shí)間復(fù)雜度：o(n^2)

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

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

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

第20章基數(shù)排序

20.1基數(shù)排序概念

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

排序步驟：

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

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

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

動(dòng)圖展示：

靜圖分析：

20.2代碼實(shí)現(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í)二維數(shù)組表示十個(gè)桶

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

//定義一個(gè)一維數(shù)組，用于記錄在temp中相應(yīng)的數(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];

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

intmaxLength=(max+).length();

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

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

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

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

//計(jì)算余數(shù)

intys=arr[j]/n%10;

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

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

//記錄數(shù)量

counts[ys]++;

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

intindex=0;