歸并排序的迭代實(shí)現(xiàn)方法是什么

本篇內(nèi)容介紹了“歸并排序的迭代實(shí)現(xiàn)方法是什么”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

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

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

迭代和遞歸(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)過程中的分與治，而采用迭代實(shí)現(xiàn)時(shí)，策略上有兩點(diǎn)發(fā)生了變化：

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 分的方式采用循環(huán)(迭代)，而不是遞歸的方式;

3. 分的策略和遞歸的方式有別，依舊符合歸并排序的思想;

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

第一步：合并 5 和 1

第二步：合并 4 和 2

第三步：合并 8 和 4 ;

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

第五步：合并 [4,8]

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

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

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

而迭代就不同了，默認(rèn)將數(shù)組當(dāng)中的元素當(dāng)做 n 個(gè)長度為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)中，僅從圖中似乎看不到分的過程，但事實(shí)上，合并前已經(jīng)進(jìn)行了分，只不過這個(gè)分與遞歸調(diào)用的分不同，而是采用迭代。

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

static void mergeSort(int arr[], int n)  {        int curr_size; //標(biāo)識(shí)當(dāng)前合并的子數(shù)組的大小，從 1 已知到 n/2     int left_start; //標(biāo)識(shí)當(dāng)前要合并的子數(shù)組的起點(diǎn)     for (curr_size = 1; curr_size <= n-1; curr_size = 2*curr_size)      {          for (left_start = 0; left_start < n-1; left_start += 2*curr_size)          {              int mid = Math.min(left_start + curr_size - 1, n-1);                int right_end = Math.min(left_start + 2*curr_size - 1, n-1);                 merge(arr, left_start, mid, right_end);          }       }  }  //合并略

歸并排序的迭代實(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)問如何用迭代實(shí)現(xiàn)三路歸并排序?

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

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

原地歸并排序

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

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

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

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

第一步：比較 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)代碼：

static void merge(int arr[], int start1, int mid, int end){     int start2 = mid + 1;          //如果 mid 小于等于 mid+1 的元素，表明數(shù)組已經(jīng)有序，不需要合并     if(arr[mid] <= arr[start2]){         return;     }          while(start1 <= mid && start2 <= end){         if(arr[start1] <= arr[start2]){             start1++;         }         else{             int value = arr[start2];             int index = start2;                          //將 [start1,start2 - 1]中的元素向后移動(dòng)             while(index != start1){                 arr[index] = arr[index - 1];                 index--;             }                          arr[start1] = value;                          start1++;             mid++;             start2++;         }     } }

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

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

“歸并排序的迭代實(shí)現(xiàn)方法是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！