日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
這兩個(gè)問(wèn)題都不清楚，還說(shuō)會(huì)「歸并排序」？

今天分享的的內(nèi)容涉及以下兩個(gè)問(wèn)題：

  1. 歸并排序的迭代實(shí)現(xiàn)方式;
  2. 實(shí)現(xiàn)一個(gè)原地歸并排序(In-Place Merge Sort);

歸并排序的迭代實(shí)現(xiàn)

在正式看代碼前，希望你心中清楚歸并排序的遞歸實(shí)現(xiàn)方式，不熟悉也無(wú)妨，看這篇文章 圖解「歸并排序」算法(修訂版) 文章。

迭代和遞歸(Iteration & Recursion)本就心心相惜，你中有我，我中有你，任何一個(gè)算法的遞歸實(shí)現(xiàn)都可以將其變成一個(gè)迭代的實(shí)現(xiàn)方式，只要代價(jià)足夠小，收益(獲得的空間和時(shí)間效率的提升)足夠高就可以。

歸并排序同樣可以做到，只是歸并排序的迭代實(shí)現(xiàn)方式較為特殊，不像大多數(shù)遞歸與迭代的轉(zhuǎn)化，歸并排序并不需要程序中出現(xiàn)一個(gè)顯式的 stack 輔助棧，但同樣能夠去掉遞歸調(diào)用，以迭代的方式實(shí)現(xiàn)歸并排序。

 

這張圖一定很熟悉了，這就是標(biāo)準(zhǔn)的遞歸實(shí)現(xiàn)過(guò)程中的分與治，而采用迭代實(shí)現(xiàn)時(shí)，策略上有兩點(diǎn)發(fā)生了變化：

  1. 分的方式采用循環(huán)(迭代)，而不是遞歸的方式;
  2. 分的策略和遞歸的方式有別，依舊符合歸并排序的思想;

我們依舊以下面的數(shù)組為例說(shuō)明(感覺(jué)這個(gè)數(shù)組萬(wàn)能，哈哈)：

 

第一步：合并 5 和 1

 

第二步：合并 4 和 2

 

第三步：合并 8 和 4 ;

 

第四步：合并 [1,5,2,4]

 

第五步：合并 [4,8]

 

第六步：合并 [1,2,4,5,4,8]

 

看到這里，并不能清晰地看出歸并排序迭代和遞歸之間的差異，客官莫急：

 

這次就會(huì)清晰可見了，歸并排序的迭代實(shí)現(xiàn)方式中的合并順序與遞歸明顯不同，遞歸是將長(zhǎng)度為 n 的原始數(shù)組一分為二，然后再將兩個(gè)(1/2)的數(shù)組再一分為二，直到分為n個(gè)長(zhǎng)度為1的元素。然后兩兩按大小合并，如此反復(fù)，直到最后形成包含 n 個(gè)數(shù)的一個(gè)有序數(shù)組。

而迭代就不同了，默認(rèn)將數(shù)組當(dāng)中的元素當(dāng)做 n 個(gè)長(zhǎng)度為1的元素;依次按照 2 個(gè)一組合并，4 個(gè)元素為一組進(jìn)行合并(不足 4 個(gè)，比如 [4,8] ，不足 4 個(gè)就按照剩余個(gè)數(shù) 2 合并)，....，最后以 n/2 個(gè)元素為一組進(jìn)行合并，得到我們的有序數(shù)組。

迭代實(shí)現(xiàn)中，僅從圖中似乎看不到分的過(guò)程，但事實(shí)上，合并前已經(jīng)進(jìn)行了分，只不過(guò)這個(gè)分與遞歸調(diào)用的分不同，而是采用迭代。

忽略合并的實(shí)現(xiàn)細(xì)節(jié)，我們僅看一下迭代的實(shí)現(xiàn)方式。

 
 
 
 
    
  
  
  
  
  1. static void mergeSort(int arr[], int n)  
    2. 
  
  
  
  
  2. {  
    3. 
  
  
  
  
  3.   
    4. 
  
  
  
  
  4.     int curr_size; //標(biāo)識(shí)當(dāng)前合并的子數(shù)組的大小，從 1 已知到 n/2 
    5. 
  
  
  
  
  5.     int left_start; //標(biāo)識(shí)當(dāng)前要合并的子數(shù)組的起點(diǎn) 
    6. 
  
  
  
  
  6.     for (curr_size = 1; curr_size <= n-1; curr_size = 2*curr_size)  
    7. 
  
  
  
  
  7.     {  
    8. 
  
  
  
  
  8.         for (left_start = 0; left_start < n-1; left_start += 2*curr_size)  
    9. 
  
  
  
  
  9.         {  
    10. 
  
  
  
  
  10.             int mid = Math.min(left_start + curr_size - 1, n-1);  
    11. 
  
  
  
  
  11.   
    12. 
  
  
  
  
  12.             int right_end = Math.min(left_start + 2*curr_size - 1, n-1); 
    13. 
  
  
  
  
  13.     
    14. 
  
  
  
  
  14.             merge(arr, left_start, mid, right_end); 
    15. 
  
  
  
  
  15.          }  
    16. 
  
  
  
  
  16.      }  
    17. 
  
  
  
  
  17. }  
    18. 
  
  
  
  
  18. //合并略 
    19.

歸并排序的迭代實(shí)現(xiàn)就是將遞歸中 遞 的操作修改成了兩層的 for 循環(huán)，為了理解這兩層循環(huán)所進(jìn)行的操作，建議最好自己將數(shù)組 [5,1,4,2,8,4] 代進(jìn)去手動(dòng)的計(jì)算一遍，下圖中給出了merge(arr, left_start, mid, right_end); 函數(shù)依次調(diào)用數(shù)據(jù)：

 

請(qǐng)問(wèn)如何用迭代實(shí)現(xiàn)三路歸并排序?

答案很簡(jiǎn)單了，將上面提供的二路歸并排序的迭代實(shí)現(xiàn)中的所有 2 替換為 3，合并過(guò)程將變成下圖：

 

改日再詳述 3 路歸并排序，接著看第二個(gè)問(wèn)題。

原地歸并排序

所謂原地排序(In-place Sort)就是空間復(fù)雜度為的排序算法。圖解「歸并排序」算法(修訂版) 中所講的歸并排序空間復(fù)雜度為，時(shí)間復(fù)雜度為，其中的空間復(fù)雜度是由 merge(arr, left, mid, right) 函數(shù)所造成的，所以關(guān)于這個(gè)問(wèn)題的解決就是折騰 merge 函數(shù)。

該如何折騰呢?看栗子(哈哈，就是廢話少)。

同樣以最后一次合并為例：

 

這里的 start1 、start2 還有 mid 的初始設(shè)置就不多說(shuō)了，看原地合并過(guò)程即可。

第一步：比較 start1 指向的元素 1 和 start2 指向的元素 2 ，1 < 2 ，所以直接將 start1右移，即 start1++ .

 

第二步：比較 start1 指向的元素 4 和 start2 指向的元素 2 ，4 > 2 ，此時(shí)不使用額外空間實(shí)現(xiàn)合并操作，將 start2 之前，start1 (包含 start1) 之后的元素向后移動(dòng)，并將 2 拷貝到 start1 所指向的位置，然后將 start1 、start2 還有 mid 均向后移動(dòng)：

 

第三步：比較 start1 指向的元素 4 和 start2 指向的元素 4 ，4 = 4 ，所以直接將 start1右移，即 start1++ .

 

第四步：與第二步類似，比較 start1 指向的元素 5 和 start2 指向的元素 4 ，5 > 4 ，將 4向前移動(dòng)，將 5 向后移動(dòng)，然后將 start1 、start2 還有 mid 均向后移動(dòng)：

 

第五步：比較 start1 指向的元素 5 和 start2 指向的元素 8 ，**5 < 8 ** ，直接將 start1右移，即 start1++ ;此時(shí) start1 > mid ,表明合并完成了。

 

空間復(fù)雜度為 的合并操作的實(shí)現(xiàn)代碼：

 
 
 
 
    
  
  
  
  
  1. static void merge(int arr[], int start1, int mid, int end){ 
    2. 
  
  
  
  
  2.     int start2 = mid + 1; 
    3. 
  
  
  
  
  3.      
    4. 
  
  
  
  
  4.     //如果 mid 小于等于 mid+1 的元素，表明數(shù)組已經(jīng)有序，不需要合并 
    5. 
  
  
  
  
  5.     if(arr[mid] <= arr[start2]){ 
    6. 
  
  
  
  
  6.         return; 
    7. 
  
  
  
  
  7.     } 
    8. 
  
  
  
  
  8.      
    9. 
  
  
  
  
  9.     while(start1 <= mid && start2 <= end){ 
    10. 
  
  
  
  
  10.         if(arr[start1] <= arr[start2]){ 
    11. 
  
  
  
  
  11.             start1++; 
    12. 
  
  
  
  
  12.         } 
    13. 
  
  
  
  
  13.         else{ 
    14. 
  
  
  
  
  14.             int value = arr[start2]; 
    15. 
  
  
  
  
  15.             int index = start2; 
    16. 
  
  
  
  
  16.              
    17. 
  
  
  
  
  17.             //將 [start1,start2 - 1]中的元素向后移動(dòng) 
    18. 
  
  
  
  
  18.             while(index != start1){ 
    19. 
  
  
  
  
  19.                 arr[index] = arr[index - 1]; 
    20. 
  
  
  
  
  20.                 index--; 
    21. 
  
  
  
  
  21.             } 
    22. 
  
  
  
  
  22.              
    23. 
  
  
  
  
  23.             arr[start1] = value; 
    24. 
  
  
  
  
  24.              
    25. 
  
  
  
  
  25.             start1++; 
    26. 
  
  
  
  
  26.             mid++; 
    27. 
  
  
  
  
  27.             start2++; 
    28. 
  
  
  
  
  28.         } 
    29. 
  
  
  
  
  29.     } 
    30. 
  
  
  
  
  30. } 
    31.

注意這個(gè)合并操作中涉及到了兩個(gè)嵌套的 while 循環(huán)，所以與空間復(fù)雜度為，時(shí)間復(fù)雜度為的標(biāo)準(zhǔn)實(shí)現(xiàn)相比，這種合并策略雖然將空間復(fù)雜度降到了 ，但同時(shí)也犧牲了時(shí)間復(fù)雜度，時(shí)間復(fù)雜度變成了

時(shí)間復(fù)雜度和空間復(fù)雜度就似陰陽(yáng)之術(shù)，得失之理，生死之界;要得其一，必失其一，這個(gè)世上沒(méi)有兩全其美的事情!

  本文轉(zhuǎn)載自微信公眾號(hào)「景禹」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系景禹公眾號(hào)。


網(wǎng)頁(yè)標(biāo)題：這兩個(gè)問(wèn)題都不清楚，還說(shuō)會(huì)「歸并排序」？
鏈接URL：http://www.dlmjj.cn/article/dpoepos.html