養成習慣,先贊後看!!!
你的點贊與關注真的對我非常有幫助.如果可以的話,動動手指,一鍵三連吧!!!
十大經典排序算法-堆排序,計數排序,桶排序,基數排序前言這是十大經典排序算法詳解的最後一篇了.還沒有看多之前兩篇文章的小夥伴可以先去看看之前的兩篇文章:
十大經典排序算法詳解(一)冒泡排序,選擇排序,插入排序十大經典排序算法詳解(二)希爾排序,歸并排序,快速排序
這一篇文章真的耗費了我巨大的時間和精力,由于 堆排序是基于二叉樹 的,所以寫的篇幅比較大并且由于是關于樹的,所以畫圖動态演示的工程量就進一步增加,其次就是因為計數排序,桶排序以及基數排序并不是基于比較的,所以算法的思想講解相對于之前的基于比較的算法而言會稍微難一點.
其次就是這次的調試過程也比之前多了很多需要注意的地方,這些我都會在下面的代碼中通過注釋的方式提醒大家.
最後如果大家覺得我的文章寫得還可以或者覺得文章對你有幫助的話,可以選擇關注我的公衆号:萌萌哒的瓤瓤,或者你也可以幫忙給文章來個一鍵三連吧.你的支持對我真的很有用.
算法思想:
在介紹算法之前我們首先需要了解一下下面這些概念:什麼是二叉樹,什麼是完全二叉樹,什麼是大根堆,什麼是小根堆.
學過數據結構的小夥伴肯定知道什麼是二叉樹,這部分主要是為那些可能還不太了解數據結構的小夥伴們說的.
二叉樹的定義就是每個結點至多能有兩個子樹,二叉樹是一種最簡單的樹,下面我們舉幾個樹的例子:
我們可以來哦稍微區分一下,很明顯隻有4号樹并不是我們所說的二叉樹,因為它的1号結點下有三棵子樹,所以4号樹并不是我們所說的二叉樹.到這裡,相信大家也已經基本了解二叉樹得出概念了,那麼接下來我們再來了解一下另一個概念完全二叉樹.
說到完全二叉樹,就應該知道它首先應該滿足二叉樹的一些條件,就比如說每個節點至多隻能有兩個子樹,那麼除了這個條件以外,還需要什麼條件才能稱得上是完全二叉樹呢.
官方是這樣說的: 一棵深度為k的有n個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編号，如果編号為i（1≤i≤n）的結點與滿二叉樹中編号為i的結點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。
但是很明顯說的太官方了,我們肯定需要簡化一下概念.其實說白了就是在二叉樹的基礎上,所有的節點順序必須要按照下面這樣的順序進行排列,否則就不能說是完全二叉樹
并且每次必須是已經放滿2的幂數之後才能放到下一層,并且必須是從每層最左邊的節點開始添加節點,并且必須是先添加左節點在添加右節點.否則就不能稱為是完全二叉樹,這裡呢,我們舉幾個反例,大家就知道我說的是什麼意思了:
上面的這兩棵樹就是最明顯的反例,看完這兩棵樹之後,相信大家就能更加了解什麼是完全二叉樹了.
大根堆其實很容易理解,大根堆在完全二叉樹的基礎上就一條判定條件就是:每個根節點的值必須大于它的左孩子節點已經右孩子節點的值.滿足這樣條件的二叉樹,我們就稱這個二叉樹是大根堆.當然了隻要有一個節點不滿足這樣的情況,那麼就不能稱這是大根堆.
舉個例子,下面這棵二叉樹就是一個大根堆:
舉完正确的例子之後,我們當然也需要來舉幾個反例來幫助我們更好的理解什麼是大根堆:
看完這兩個反例之後相信大家就能更加理解什麼是大根堆了.
當然了,理解完什麼是大根堆了之後,大家就能舉一反三地了解什麼叫做小根堆了.這裡就不再給大家廢話.
在了解完上面的這些概念之後,我們就可以來講解什麼是堆排序了.
堆排序的算法步驟其實很簡單,總共就三步.
之後重複上述2,3步驟,直到需要重構成大根堆的數組為空為止.
算法的步驟的确簡潔明了,其實大家看了也應該已經懂了.
因為每次重構成大根堆之後,根據大根堆的特性,每個節點的值一定大于左右孩子節點的值,所以很明顯大根堆的根節點就是二叉樹中值最大的值同時也就是數組中最大的值.所以重構成大根堆之後交換數組隊頭與隊尾元素的操作就是在将最大的元素進行定位.也就意味着這一輪結束之後,數組中已經确定了一個元素的最終位置了.
算法的思想就是這樣,誰都能說的出來,但是呢,堆排序的難點就是在于我們如何将數組重構成我們大根堆.這個就是堆排序的難點.
那麼接下來,我們就着重講解一下重構大根堆的過程是怎麼樣的.
首先我們需要明白一點就是我們一開始構建二叉樹的時候遵循的是這樣的原則: 從上往下,從左往右 .但是到了将二叉樹重構成大根堆的時候我們的原則就必須要反過來了:從下往上,從右往左.這個大家動動小腦瓜應該就能理解了.
顯然我們每次對小子樹進行重構成大根堆的操作時,最後都會使得最大的元素上移,對不對,既然大的元素是在上移的,那麼很顯然我們就應該從下往上開始構建.
既然我們已經知道重構的順序是什麼樣的之後,我們就需要再明白一點,那就是我們應該對哪些元素進行重構的操作呢?上面我們已經說過了,大根堆的一個硬性條件就是每個節點必需要大于它的左右孩子節點,那麼很顯然如果節點本身沒有孩子節點的話,就不需要進行重構了.所以我們需要進行重構的元素必定包含孩子節點.并且結合我們上面所說重構順序基本就可以得出一個結論:重構的元素就是最後一個非葉子節點之前的所有節點,包括該節點本身.,就比方下面這張圖中紅色圈圈的元素.
之後我們隻需要通過循環,依次進行下面的操作:
比較節點及其左右孩子節點,如果有孩子節點的值大于該節點,那麼就交換兩者的位置.這裡需要大家特别注意!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
這裡需要大家特别注意!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
這裡需要大家特别注意!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!交換兩者的位置之後我們還需要進行一個步驟 重新校驗特别注意!!!特别注意!!!重複這個過程,直到最後一個元素為止.
到這裡堆排序的基本思想也就已經基本講解完畢了,接下來就是通過圖來動态的演示一下堆排序的過程,這樣能夠讓大家更好的理解堆排序:
這是第一輪堆排序:
)第二次堆排序:
)第三次堆排序:
)這裡給大家模拟三次,大家應該就差不多懂這個流程了.主要是這圖圖畫起來實在是太麻煩了.能力有限就隻畫這三次的了.在下面的代碼裡面,我還會着重講重新校驗的過程,大家如果這裡還沒理解的,也可以接着往下面看.
算法的基本思想大家應該基本上就能理解了.那麼我們再來稍微聊聊堆排序的一些特點:
算法圖解:
示例代碼:這是我寫的第一版的代碼:
//交換數組中的元素
public static void swap(int[]num ,int i,int j) {
int temp=num[i];
num[i]=num[j];
num[j]=temp;
}
//将待排序的數組構建成大根堆
public static void buildbigheap(int []num,int end) {
//從最後一個非葉子節點開始構建,依照從下往上,從右往左的順序
for(int i=end/2;i>=0;i--) {
int left=2*i 1;
int right=2*i 2;
int big=i;
//判斷小分支那個是大元素
if(left<end&&num[i]<num[left])
// swap(num, i, left);
i=left;
if(right<end&&num[i]<num[right])
// swap(num, i, right);
i=right;
swap(num, i, big);
}
}
public static void main(String[] args) {
int []num ={7,4,9,3,2,1,8,6,5,10};
long startTime=System.currentTimeMillis();
//第一次構建大根堆
buildbigheap(num, num.length);
for(int j=num.length-1;j>0;j--) {
//交換隊頭已經排序得到的最大元素與隊尾元素
swap(num, 0, j);
System.out.print("第" (num.length-j) "次排序: ");
for(int k=0;k<num.length;k ) {
System.out.print(num[k] " ");
}
System.out.println();
//交換結束之後,大根堆已經内破壞,需要開始重新構建大根堆
buildbigheap(num,j);
}
long endTime=System.currentTimeMillis();
System.out.println("程序運行時間： " (endTime-startTime) "ms");
}
一開始我覺得我的代碼是對的,并且運行出來的結果也和我預期的一樣,但是當我自己畫圖以後畫到這張圖的時候我就知道算法還是有BUG的,這個BUG就是每次構建大根堆的時候:我們的确能夠在每次構建大根堆的時候将最大的元素挑選出來,但是,我們在挑選出當前最大的元素之後,我們的大根堆真的還是大根堆嗎,這裡用上面畫的圖,我們就能看出來了:
很明顯這個這一步我們的确已經将最大的元素挑選出來了,但是我們當前的已經不是大根堆了,所以我就在想我到底是哪一步做錯了呢.之後我參考了網上的資料發現,該算法還有一個重點就是:如果我們發現根節點與孩子節點交換順序之後,我們就需要重新檢查交換之後的孩子節點以下的所有節點是否還滿足大根堆的定義,因為可能我們交換後的孩子節點的值還是比他的孩子節點要小的.就比方上面那張圖裡我們所看到的.所以修改後的代碼主要就是加上了重新校驗的過程.
修改後的第二版代碼:
//交換數組中的元素
public static void swap(int[]num ,int i,int j) {
int temp=num[i];
num[i]=num[j];
num[j]=temp;
}
//将待排序的數組構建成大根堆
public static void buildbigheap(int []num,int end) {
//從最後一個非葉子節點開始構建,依照從下往上,從右往左的順序
for(int i=end/2;i>=0;i--) {
adjustnode(i, end, num);
}
}
//調整該節點及其以下的所有節點
public static void adjustnode(int i,int end,int []num) {
int left=2*i 1;
int right=2*i 2;
int big=i;
//判斷小分支那個是大元素
if(left<end&&num[i]<num[left])
i=left;
if(right<end&&num[i]<num[right])
i=right;
if(i!=big) {
//交換順序之後需要繼續校驗
swap(num, i, big);
//重新校驗,防止出現交換之後根節點小于孩子節點的情況
adjustnode(i, end, num);
}
}
public static void main(String[] args) {
int []num ={5,3,7,1,4,6,2};
long startTime=System.currentTimeMillis();
//第一次構建大根堆
buildbigheap(num, num.length);
for(int j=num.length-1;j>0;j--) {
System.out.print("第" (num.length-j) "次排序前: ");
for(int k=0;k<num.length;k ) {
System.out.print(num[k] " ");
}
//交換隊頭已經排序得到的最大元素與隊尾元素
swap(num, 0, j);
System.out.print("第" (num.length-j) "次排序後: ");
for(int k=0;k<num.length;k ) {
System.out.print(num[k] " ");
}
System.out.println();
//交換結束之後,大根堆已經被破壞,需要開始重新構建大根堆
buildbigheap(num,j);
}
long endTime=System.currentTimeMillis();
System.out.println("程序運行時間： " (endTime-startTime) "ms");
}
這裡我們将這兩個排序結果對比一下,大家就更加能了解重新校驗步驟的重要性了.
相信經過我這樣的講解之後,大家一定能夠更好的理解堆排序了.
複雜度分析:
理解完堆排序的基本思想之後,我們就需要來分析一下他的時間複雜度,空間複雜度.
算法思想:計數排序最核心的思想就是計數序列中每個元素出現的次數,我們将每個元素的數量都記錄下來之後.我們就可以通過按
了解完計數排序的基本思想之後,我們就來看看看這個算法的實現步驟又是怎麼樣的呢?主要就是下面這幾個步驟:
計數排序的基本思想基本就是這樣,按照慣例,還是通過下面的圖來幫助大家更好的理解計數排序的基本思想:
了解完計數排序的基本思想之後,我們還是按照慣例分析一下計數排序算法的一些特點:
-計數排序是穩定的 ,這個大家應該能很明顯的看出來,因為計數排序本身并不是基于比較的算法.
-計數排序需要的額外空間比較大,這個大家很明顯的看出來,并且空間浪費的情況也會比較嚴重,因為一旦序列中MAX與MIN的差距過大,那麼需要的内存空間就會非常大.并且假如序列中的元素都是散布在一個特定的區間内,那麼内存空間浪費的情況也會非常明顯.
算法圖解:
示例代碼:
public static void main(String[] args) {
int []num ={7,4,9,3,2,1,8,6,5,10};
long startTime=System.currentTimeMillis();
int min=Integer.MAX_VALUE;
int max=Integer.MIN_VALUE;
//先找出數組中的最大值與最小值
for(int i=0;i<num.length;i ) {
if(num[i]<min)
min=num[i];
if(num[i]>max)
max=num[i];
}
//創建一個長度為max-min 1長度的數組來進行計數
int []figure=new int [max-min 1];
for(int i=0;i<num.length;i ) {
//計算每個數據出現的次數
figure[num[i]-min] ;
}
int begin=0;
//創建一個新的數組來存儲已經排序完成的結果
int []num1=new int [num.length];
for(int i=0;i<figure.length;i ) {
//循環将數據pop出來
if(figure[i]!=0) {
for(int j=0;j<figure[i];j ) {
num1[begin ]=min i;
}
}
}
System.out.println("數據範圍:" min "~" max);
System.out.println("計數結果: ");
for(int i=0;i<num.length;i )
System.out.println(" " num[i] "出現" figure[num[i]-min] "次");
System.out.print("排序結果: ");
for(int i=0;i<num1.length;i )
System.out.print(num1[i] " ");
System.out.println();
long endTime=System.currentTimeMillis();
System.out.println("程序運行時間： " (endTime-startTime) "ms");
}
複雜度分析:
理解完計數排序的基本思想之後,我們就需要來分析一下他的時間複雜度,空間複雜度.
算法思想:大家第一眼看到這個算法的名字時相信大家的反應應該和我是一樣的,桶排序?排序怎麼還需要用到桶呢?桶排序裡的桶又是主要是幹什麼的呢?
其實這個大家類比到我們平常生活中就能基本知道桶排序的桶是幹嘛的呢?在我們的日常生活中,我們的桶一般都是用來裝東西的,我們可能是用來裝水,又或者是裝錢的反正不管怎麼樣,我們的桶最後都是一個容器,是用來存儲相應的物質的.
顯然我們當前存在的隻有我們的待排序的序列,那麼我們的桶就是用來存儲我們的序列中的元素的.就像下圖所示:
可以看到我們把相應的元素放入相應的桶裡面了.這個放入的規則是這樣的:桶是從大到小排列的,并且每一個桶都會有一個數據範圍,意思就是0号桶存放是1~ 2數據範圍的數據,1号桶存放3~4數據範圍的數據,2号桶存放吧5 ~6數據範圍内的數據.詳細的放入規則我會在下面的實現步驟裡面說.這裡大家先簡單了解一下.
這裡大家要注意的一點就是,我們在把元素放入各自相應的桶裡面的時候,是需要對桶内的序列進行排序的,意思就是等到每個元素都放入相應的桶裡面之後,桶裡面相應的序列本身也已經有序了.就如下圖所示:
可以看到上面,每個桶内的序列都已經排好序了,那麼很顯然我們最後就隻需要按照桶的序号大小将桶内的元素打印出來,那麼我們的序列就已經排好序了.
說完桶排序的基本思想之後,我們接下來就說一下桶排序在代碼上是如何實現的,大緻有下面這幾步:
接下來我們還是通過下面的圖來動态演示一下桶排序的過程:
了解完桶排序的基本思想之後,按照慣例我們還是來簡單分析一下他的一些特點:
算法圖解:
示例代碼:
//在鍊表中添加元素的同時需要進行元素的排序
public static void sort(ArrayList<Integer>list,int i) {
if(list==null)
list.add(i);
//這裡采用的排序方式為插入排序
else {
int flag=list.size()-1;
while(flag>=0&&list.get(flag)>i) {
if(flag 1>=list.size())
list.add(list.get(flag));
else
list.set(flag 1, list.get(flag));
flag--;
}
if(flag != (list.size()-1))
//注意這裡是flag 1,自己可以嘗試将這裡換成flag看看,會出現數組越界的情況
list.set(flag 1, i);
else
list.add(i);
}
}
public static void Bucketsort(int []num,int sum) {
//遍曆得到數組中的最大值與最小值
int min=Integer.MAX_VALUE;
int max=Integer.MIN_VALUE;
for(int i=0;i<num.length;i ) {
min = min <= num[i] ? min: num[i];
max = max >= num[i] ? max: num[i];
}
//求出每個桶的長度,這裡必須使用Double
double size=(double)(max-min 1)/sum;
ArrayList<Integer>list[]=new ArrayList[sum];
for(int i=0;i<sum;i ) {
list[i]=new ArrayList<Integer>();
}
//将每個元素放入對應的桶之中同時進行桶内元素的排序
for(int i=0;i<num.length;i ) {
System.out.println("元素:" String.format("%-2s", num[i]) ", 被分配到" (int)Math.floor((num[i]-min)/size) "号桶");
sort(list[(int)Math.floor((num[i]-min)/size)], num[i]);
}
System.out.println();
for(int i=0;i<sum;i ) {
System.out.println(String.format("%-1s", i) "号桶内排序:" list[i]);
}
System.out.println();
//順序遍曆各個桶,得出我們 已經排序号的序列
for(int i=0;i<list.length;i ) {
if(list[i]!=null){
for(int j=0;j<list[i].size();j ) {
System.out.print(list[i].get(j) " ");
}
}
}
System.out.println();
System.out.println();
}
public static void main(String[] args) {
int []num ={7,4,9,3,2,1,8,6,5,10};
long startTime=System.currentTimeMillis();
//這裡桶的數量可以你自己定義,這裡我就定義成了3
Bucketsort(num, 3);
long endTime=System.currentTimeMillis();
System.out.println("程序運行時間： " (endTime-startTime) "ms");
}
這裡的時間是不準确的,因為我需要将每輪排序的結果打印出來給大家看,所以會多花費一些時間,如果大家想要看真實的時間的話,大家可以把我打印結果的代碼注釋掉再看看算法的執行時間.
複雜度分析:
理解完桶排序的基本思想之後,我們就需要來分析一下他的時間複雜度,空間複雜度.
算法思想:
基數排序的實現步驟非常好理解,但是想要真正理解他的算法思想就稍微有點難度了.那麼接下來就來講解基數排序的算法思想.
首先基數排序是根據數位來進行排序的.他是從個位開始,然後按照每一位的數進行排序,如下圖所示:
排完序之後就往前進一位,然後再将所有的數按照這一位所在的數進行排序,如下圖所示:
重複這個過程直到所有的位數都已經被排過序了.如下圖所示:
并且如果這個過程中碰到某個數在這個位上沒有數的話就進行補零操作,将該位看成是0.就比方下圖我用紅框圈出來的部分:
等到所有的位數都已經排序完畢之後,我們就可以看到我們已經排序好的序列了.
這個過程相信大家肯定都很好理解,但是相信大家如果是第一次看這個算法的肯定會有和我當初一樣的困惑,那就是為什麼基數排序選擇的是從低位到高位來進行排序的呢,而不是像我們平常比較數據的大小一樣,從高位到低位來比較呢?
這裡呢我們先不講為什麼,我們先看下面這兩個案例:
|
原序列 |
百位排好序後 |
十位排好序後 |
個位排好序後 |
|
329 |
839 |
657 |
839 |
|
457 |
720 |
457 |
329 |
|
657 |
657 |
355 |
657 |
|
839 |
457 |
839 |
457 |
|
436 |
436 |
436 |
436 |
|
720 |
329 |
720 |
355 |
|
355 |
355 |
329 |
720 |
|
原序列 |
個位排好序後 |
十位排好序後 |
百位排好序後 |
|
329 |
720 |
720 |
329 |
|
457 |
355 |
329 |
355 |
|
657 |
436 |
436 |
436 |
|
839 |
457 |
839 |
457 |
|
436 |
657 |
355 |
657 |
|
720 |
329 |
451 |
720 |
|
355 |
839 |
657 |
839 |
對比看了上面兩個例子之後相信大家就知道了,很明顯我們看到如果是從該我到低位來進行比較的話,我們會發現比較到最後之後序列仍然是無序的,但是從低位到高位進行比較的話,我們就會發現序列到最後已經排好序了.
是不是很奇怪,同樣的執行過程,隻不過執行的順序發生了改變,為什麼結果就會産生這樣的結果呢?産生這個差異的重點就是在我們忽略了一個問題,那就是我們在進行高位到低位比較的時候,高位的權重是高于低位的.就比方下圖所示:
正是因為這個原因,所以我們采取的是從低位到高位比較的過程.
說完基本思想之後,我們來說一下算法的實現步驟:
接下來我們還是通過下面的圖來動态演示一下基數排序的過程:個位排序:
十位排序:
百位排序:
千位排序:
在了解完基數排序的基本思想之後,按照慣例我們還是來簡單分析一下基數排序的特點:
算法圖解:
示例代碼:
//将所有的數組合并成原來的數組
public static void merge(ArrayList<Integer> list[],int num[]) {
int k=0;
for(int i=0;i<list.length;i ) {
if(list[i]!=null) {
for(int j=0;j<list[i].size();j ) {
num[k ]=list[i].get(j);
System.out.print(num[k-1] " ");
}
}
//合并完成之後需要将鍊表清空,否則元素會越來越多
list[i].clear();
}
System.out.println();
}
//将所有的元素分散到各個鍊表之中
public static void split(ArrayList<Integer> list[],int num[],int k) {
for(int j=0;j<num.length;j ) {
list[num[j]/k].add(num[j]);
}
System.out.println("-----------------------------------------------------------------------");
System.out.println("個位開始數,第" (String.valueOf(k).length()) "位排序結果:");
for(int j=0;j<10;j ) {
System.out.println((String.valueOf(k).length()) "号位,數值為" j "的鍊表結果:" list[j]);
}
}
public static void main(String[] args) {
ArrayList<Integer>list[]=new ArrayList [10];
for(int i=0;i<10;i ) {
list[i]=new ArrayList<Integer>();
}
int []num ={7,14,9,333,201,1,88,6,57,10,56,74,36,234,456};
long startTime=System.currentTimeMillis();
int max=Integer.MIN_VALUE;
//第一次遍曆獲得序列中的最大值
for(int i=0;i<num.length;i ) {
if(num[i]>max)
max=num[i];
}
int k=1;
for(int i=0;i<String.valueOf(max).length();i ) {
split(list, num, k);
System.out.println("第" (i 1) "次排序");
merge(list, num);
k=k*10;
}
long endTime=System.currentTimeMillis();
System.out.println("程序運行時間： " (endTime-startTime) "ms");
}
複雜度分析:
理解完基數排序的基本思想之後,我們就需要來分析一下他的時間複雜度,空間複雜度.
到這裡十大經典排序算法詳解的内容就已經全部講解完畢了.這一次文章不管是在内容的質量上或者是在文章的排版上,都是目前工作量比較大的一期.所以如果大家覺得文章還行或者覺得文章對你有幫助的話,UP希望能關注一下我的公衆号:萌萌哒的瓤瓤,或者覺得關注公衆号麻煩的話,也可以給我的文章一鍵三連.新人UP真的很需要你的支持!!!
不點在看,你也好看!
點點在看,你更好看!
,更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
