女人夜夜春高潮爽A∨片传媒_国产精品VIDEOS麻豆_在线精品亚洲一区二区三区_亚洲熟妇无码av

編程代碼
新聞詳情

十種常見排序算法動圖演示（二）

發布(bu)時間：2020-03-19 09:12:20　最(zui)后更新：2020-11-23 14:41:16　瀏覽次數：3575

5、歸并排序（Merge Sort）

歸并排(pai)序(xu)(xu)(xu)(xu)是建立在歸并操作(zuo)上的(de)(de)(de)一(yi)(yi)種(zhong)有效(xiao)的(de)(de)(de)排(pai)序(xu)(xu)(xu)(xu)算法。該算法是采用(yong)分(fen)治法（Divide and Conquer）的(de)(de)(de)一(yi)(yi)個(ge)非常典型的(de)(de)(de)應(ying)用(yong)。將已有序(xu)(xu)(xu)(xu)的(de)(de)(de)子序(xu)(xu)(xu)(xu)列(lie)(lie)合并，得(de)到完全有序(xu)(xu)(xu)(xu)的(de)(de)(de)序(xu)(xu)(xu)(xu)列(lie)(lie)；即(ji)先使每個(ge)子序(xu)(xu)(xu)(xu)列(lie)(lie)有序(xu)(xu)(xu)(xu)，再使子序(xu)(xu)(xu)(xu)列(lie)(lie)段間有序(xu)(xu)(xu)(xu)。若將兩個(ge)有序(xu)(xu)(xu)(xu)表(biao)合并成一(yi)(yi)個(ge)有序(xu)(xu)(xu)(xu)表(biao)，稱為2-路歸并。 

5.1 算法描述

  • 把長度為n的輸入序列分成兩個長度為n/2的子序列；
  • 對這兩個子序列分別采用歸并排序；
  • 將兩個排序好的子序列合并成一個最終的排序序列。

5.2 動圖演示

5.3 代碼實現

5.4 算法分析

歸(gui)并(bing)排(pai)序是(shi)一(yi)種穩定的(de)排(pai)序方法。和選(xuan)擇排(pai)序一(yi)樣，歸(gui)并(bing)排(pai)序的(de)性能不受輸入(ru)數(shu)據的(de)影響，但表現比選(xuan)擇排(pai)序好的(de)多，因(yin)為始終都是(shi)O(nlogn）的(de)時間復雜度。代(dai)價是(shi)需要(yao)額(e)外(wai)的(de)內(nei)存(cun)空間。

6、快速排序（Quick Sort）

快速排(pai)序(xu)的(de)(de)基本思想(xiang)：通過一趟排(pai)序(xu)將待排(pai)記(ji)(ji)錄(lu)分隔成獨立的(de)(de)兩部分，其中一部分記(ji)(ji)錄(lu)的(de)(de)關鍵(jian)字(zi)均(jun)比另一部分的(de)(de)關鍵(jian)字(zi)小，則可(ke)分別對這兩部分記(ji)(ji)錄(lu)繼續進行排(pai)序(xu)，以達(da)到整個序(xu)列有序(xu)。

6.1 算法描述

快速排序使用(yong)分治法來(lai)把一個(ge)串（list）分為兩個(ge)子串（sub-lists）。具體(ti)算法描述如下(xia)：

  • 從數列中挑出一個元素，稱為 “基準”（pivot）；
  • 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
  • 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

6.2 動圖演示

6.3 代碼實現

7、堆排序（Heap Sort）

堆(dui)排(pai)序（Heapsort）是(shi)指利用(yong)堆(dui)這種(zhong)數據(ju)結(jie)構(gou)所設(she)計的(de)一種(zhong)排(pai)序算法。堆(dui)積是(shi)一個近似(si)完全二(er)叉樹(shu)的(de)結(jie)構(gou)，并同時滿足堆(dui)積的(de)性質(zhi)：即子結(jie)點(dian)的(de)鍵值或索引(yin)總是(shi)小于（或者大于）它(ta)的(de)父節點(dian)。

7.1 算法描述

  • 將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆，此堆為初始的無序區；
  • 將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n]；
  • 由于交換后新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,……Rn-1)調整為新堆，然后再次將R[1]與無序區最后一個元素交換，得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重復此過程直到有序區的元素個數為n-1，則整個排序過程完成。

7.2 動圖演示

7.3 代碼實現

8、計數排序（Counting Sort）

計(ji)數(shu)排序不(bu)是基于比較的(de)排序算法，其核(he)心(xin)在(zai)于將(jiang)輸入的(de)數(shu)據值(zhi)轉化為鍵存儲(chu)在(zai)額外開辟的(de)數(shu)組空間中。 作為一種線性時間復雜度的(de)排序，計(ji)數(shu)排序要求輸入的(de)數(shu)據必須(xu)是有(you)確定范圍(wei)的(de)整數(shu)。

8.1 算法描述

  • 找出待排序的數組中最大和最小的元素；
  • 統計數組中每個值為i的元素出現的次數，存入數組C的第i項；
  • 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；
  • 反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1。

8.2 動圖演示

8.3 代碼實現


8.4 算法分析

計數(shu)(shu)排(pai)(pai)序(xu)是(shi)(shi)一(yi)個(ge)穩定的(de)排(pai)(pai)序(xu)算(suan)法(fa)。當(dang)輸入的(de)元素是(shi)(shi) n 個(ge) 0到 k 之(zhi)間(jian)的(de)整(zheng)數(shu)(shu)時，時間(jian)復(fu)雜度是(shi)(shi)O(n+k)，空(kong)間(jian)復(fu)雜度也是(shi)(shi)O(n+k)，其排(pai)(pai)序(xu)速度快于任何比較(jiao)排(pai)(pai)序(xu)算(suan)法(fa)。當(dang)k不(bu)是(shi)(shi)很(hen)大并且序(xu)列(lie)比較(jiao)集(ji)中時，計數(shu)(shu)排(pai)(pai)序(xu)是(shi)(shi)一(yi)個(ge)很(hen)有效(xiao)的(de)排(pai)(pai)序(xu)算(suan)法(fa)。

9、桶排序（Bucket Sort）

桶(tong)排(pai)(pai)(pai)序(xu)(xu)是計(ji)數排(pai)(pai)(pai)序(xu)(xu)的升級版。它利用了(le)函數的映(ying)射關系，高(gao)效與(yu)否的關鍵就(jiu)在(zai)于(yu)這個映(ying)射函數的確定(ding)。桶(tong)排(pai)(pai)(pai)序(xu)(xu) (Bucket sort)的工作的原理：假設(she)輸入(ru)數據(ju)服從均勻分布(bu)，將數據(ju)分到有(you)限(xian)數量的桶(tong)里，每個桶(tong)再分別排(pai)(pai)(pai)序(xu)(xu)（有(you)可能再使(shi)用別的排(pai)(pai)(pai)序(xu)(xu)算法或是以(yi)遞(di)歸方式繼續(xu)使(shi)用桶(tong)排(pai)(pai)(pai)序(xu)(xu)進行排(pai)(pai)(pai)）。

9.1 算法描述

  • 設置一個定量的數組當作空桶；
  • 遍歷輸入數據，并且把數據一個一個放到對應的桶里去；
  • 對每個不是空的桶進行排序；
  • 從不是空的桶里把排好序的數據拼接起來。 

9.2 圖片演示

9.3 代碼實現

9.4 算法分析

桶(tong)排序最(zui)好情(qing)況(kuang)下使用(yong)線性時間(jian)O(n)，桶(tong)排序的(de)時間(jian)復雜度(du)(du)，取決與(yu)對各個桶(tong)之間(jian)數(shu)據(ju)進(jin)行排序的(de)時間(jian)復雜度(du)(du)，因為(wei)其它部分(fen)的(de)時間(jian)復雜度(du)(du)都(dou)為(wei)O(n)。很顯然，桶(tong)劃分(fen)的(de)越小，各個桶(tong)之間(jian)的(de)數(shu)據(ju)越少，排序所(suo)用(yong)的(de)時間(jian)也會(hui)越少。但(dan)相(xiang)應的(de)空間(jian)消(xiao)耗就會(hui)增大。 

10、基數排序（Radix Sort）

基數排序(xu)(xu)(xu)是(shi)按(an)照(zhao)(zhao)低(di)位(wei)先(xian)排序(xu)(xu)(xu)，然(ran)后(hou)收集；再按(an)照(zhao)(zhao)高(gao)(gao)位(wei)排序(xu)(xu)(xu)，然(ran)后(hou)再收集；依次(ci)類推，直到最(zui)高(gao)(gao)位(wei)。有時候(hou)有些屬性是(shi)有優(you)先(xian)級(ji)順序(xu)(xu)(xu)的，先(xian)按(an)低(di)優(you)先(xian)級(ji)排序(xu)(xu)(xu)，再按(an)高(gao)(gao)優(you)先(xian)級(ji)排序(xu)(xu)(xu)。最(zui)后(hou)的次(ci)序(xu)(xu)(xu)就(jiu)是(shi)高(gao)(gao)優(you)先(xian)級(ji)高(gao)(gao)的在前，高(gao)(gao)優(you)先(xian)級(ji)相同的低(di)優(you)先(xian)級(ji)高(gao)(gao)的在前。

10.1 算法描述

  • 取得數組中的最大數，并取得位數；
  • arr為原始數組，從最低位開始取每個位組成radix數組；
  • 對radix進行計數排序（利用計數排序適用于小范圍數的特點）；

10.2 動圖演示

10.3 代碼實現

10.4 算法分析

基數(shu)(shu)排(pai)序基于(yu)分(fen)別排(pai)序，分(fen)別收集，所以是(shi)穩定的。但基數(shu)(shu)排(pai)序的性(xing)能比桶(tong)排(pai)序要略(lve)差，每一次關(guan)鍵字的桶(tong)分(fen)配都需(xu)要O(n)的時間(jian)復雜(za)度，而且分(fen)配之后得到新的關(guan)鍵字序列(lie)又需(xu)要O(n)的時間(jian)復雜(za)度。假如待(dai)排(pai)數(shu)(shu)據可以分(fen)為d個關(guan)鍵字，則基數(shu)(shu)排(pai)序的時間(jian)復雜(za)度將是(shi)O(d*2n) ，當然d要遠遠小于(yu)n，因此基本(ben)上還是(shi)線(xian)性(xing)級別的。

基數排序的空(kong)(kong)間(jian)復雜度為O(n+k)，其中k為桶的數量(liang)。一般(ban)來說(shuo)n>>k，因(yin)此額(e)外空(kong)(kong)間(jian)需(xu)要大概n個左右。


在線客(ke)服
客服(fu)電話
  • 0755-23712116
  • 13310869691