如何使用歸并排序算法

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

歸并排序算法思路

要將一個(gè)數(shù)組排序，可以先將數(shù)組分為兩個(gè)數(shù)組分別排序，然后再將結(jié)果歸并在一起，重復(fù)遞歸這個(gè)過(guò)程，直到數(shù)組整體有序，這就是歸并排序的算法思路。

歸并排序的優(yōu)點(diǎn)是它能夠保證任意長(zhǎng)度為N的數(shù)組排序所需的時(shí)間與 NlogN 成正比，這個(gè)優(yōu)點(diǎn)是初級(jí)排序無(wú)法達(dá)到的。

缺點(diǎn)是因?yàn)闅w并操作需要引入額外的數(shù)組，額外的空間與N成正比

原地歸并實(shí)現(xiàn)

在實(shí)現(xiàn)歸并排序之前，我們需要先完成兩個(gè)有序數(shù)組的歸并操作，即將兩個(gè)有序的數(shù)組合并成一個(gè)有序的數(shù)組；

• 在此過(guò)程中我們需要引入一個(gè)輔助數(shù)組；

• 定義的方法簽名為merge(a, lo, mid, hi)，這個(gè)方法將數(shù)組a[lo..mid]與a[mid..hi]歸并成一個(gè)有序的數(shù)組，結(jié)果存放到a[lo..mid]中；

• 該方法中需要使用的上一篇中的公共函數(shù) less ，參考上一篇文章《常見(jiàn)的初級(jí)排序算法，這次全搞懂》

public class MergeSort implements SortTemplate {     private Comparable[] aux;      @Override     public void sort(Comparable[] array) {         //待實(shí)現(xiàn)     }      private void merge(Comparable[] a, int lo, int mid, int hi) {         for (int i = lo; i <= hi; i++) {             aux[i] = a[i];         }         int i = lo, j = mid + 1;         for (int k = lo; k <= hi; k++) {             if (i > mid) {                 a[k] = aux[j++];             } else if (j > hi) {                 a[k] = aux[i++];             } else if (less(aux[i], aux[j])) {                 a[k] = aux[i++];             } else {                 a[k] = aux[j++];             }         }     }  }

自頂向下的歸并排序

基于分而治之的思想，大的數(shù)組排序，先遞歸拆分成小的數(shù)組，保證小的數(shù)組有序再歸并，直到整個(gè)數(shù)組有序，這個(gè)操作就是自頂向下的歸并排序

public class MergeSort implements SortTemplate {     private Comparable[] aux;      @Override     public void sort(Comparable[] array) {         aux = new Comparable[array.length];         doSort(array, 0, array.length - 1);     }      private void doSort(Comparable[] array, int lo, int hi) {         if (lo >= hi) {             return;         }         int mid = (hi - lo) / 2 + lo;         doSort(array, lo, mid);         doSort(array, mid + 1, hi);         merge(array, lo, mid, hi);     }      private void merge(Comparable[] a, int lo, int mid, int hi) {         //省略     }  }

以上代碼是標(biāo)準(zhǔn)的遞歸歸并排序操作，但是經(jīng)過(guò)仔細(xì)思考之后，該算法還有可以優(yōu)化的地方

「測(cè)試數(shù)組是否已經(jīng)有序」；如果a[mid]<=a[mid+1]，那么我們就可以跳過(guò)merge方法，減少merge操作；修復(fù)之后的doSort方法

private void doSort(Comparable[] array, int lo, int hi) {     if (lo >= hi) {         return;     }     int mid = (hi - lo) / 2 + lo;     doSort(array, lo, mid);     doSort(array, mid + 1, hi);     if (array[mid].compareTo(array[mid + 1]) >= 0) {         merge(array, lo, mid, hi);     } }

「對(duì)于小規(guī)模的數(shù)組可以是用插入排序」；對(duì)于小規(guī)模的數(shù)組使用歸并排序會(huì)增加遞歸調(diào)用棧，所以我們可以考慮使用插入排序來(lái)處理子數(shù)組的排序

private void doSort(Comparable[] array, int lo, int hi) {     if (lo >= hi) {         return;     }      if (hi - lo < 5) { //測(cè)試，小于5就使用插入排序         insertionSort(array, lo, hi);         return;     }      int mid = (hi - lo) / 2 + lo;     doSort(array, lo, mid);     doSort(array, mid + 1, hi);     if (less(array[mid + 1], array[mid])) {         merge(array, lo, mid, hi);     } }  //插入排序 private void insertionSort(Comparable[] array, int lo, int hi) {     for (int i = lo; i <= hi; i++) {         for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {             exch(array, j, j - 1);         }     } }

「節(jié)省復(fù)制元素到輔助數(shù)組的時(shí)間」；要實(shí)現(xiàn)該操作較麻煩，需要在每一層遞歸的時(shí)候交換輸入數(shù)據(jù)和輸出數(shù)組的角色；修改之后的完整代碼如下：

public class MergeSort implements SortTemplate {     private Comparable[] aux;      @Override     public void sort(Comparable[] array) {         aux = array.clone();         doSort(aux, array, 0, array.length - 1);     }      private void doSort(Comparable[] src, Comparable[] dest, int lo, int hi) {         if (lo >= hi) {             return;         }          if (hi - lo < 5) { //測(cè)試，小于5就使用插入排序             insertionSort(dest, lo, hi);             return;         }          int mid = (hi - lo) / 2 + lo;         doSort(dest, src, lo, mid);         doSort(dest, src, mid + 1, hi);         if (less(src[mid + 1], src[mid])) {             merge(src, dest, lo, mid, hi);         }     }      //插入排序     private void insertionSort(Comparable[] array, int lo, int hi) {         for (int i = lo; i <= hi; i++) {             for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {                 exch(array, j, j - 1);             }         }     }      private void merge(Comparable[] src, Comparable[] dest, int lo, int mid, int hi) {         int i = lo, j = mid + 1;         for (int k = lo; k <= hi; k++) {             if (i > mid) {                 dest[k] = src[j++];             } else if (j > hi) {                 dest[k] = src[i++];             } else if (less(src[i], src[j])) {                 dest[k] = src[i++];             } else {                 dest[k] = src[j++];             }         }     }  }

每一層遞歸操作都會(huì)讓子數(shù)組有序，但是子數(shù)組可能是aux[lo..hi]也有可能是a[lo..hi]；由于第一次調(diào)用doSort傳入的是src=aux，dest=array，所以遞歸最后的結(jié)果一定是輸入到了array中，保證了array整體排序完成

自底向上的歸并排序

實(shí)現(xiàn)歸并算法還有另一種思路，就是先歸并哪些小的數(shù)組，然后再成對(duì)歸并得到子數(shù)組，直到整個(gè)數(shù)組有序

public class MergeSort implements SortTemplate {     private Comparable[] aux;      @Override     public void sort(Comparable[] array) {         int length = array.length;         aux = new Comparable[length];         for (int sz = 1; sz < length; sz += sz) {             for (int i = 0; i < length - sz; i += 2 * sz) {                 merge(array, i, i + sz - 1, Math.min(i + 2 * sz - 1, length - 1));             }         }     }      private void merge(Comparable[] a, int lo, int mid, int hi) {         for (int i = lo; i <= hi; i++) {             aux[i] = a[i];         }         int i = lo, j = mid + 1;         for (int k = lo; k <= hi; k++) {             if (i > mid) {                 a[k] = aux[j++];             } else if (j > hi) {                 a[k] = aux[i++];             } else if (less(aux[i], aux[j])) {                 a[k] = aux[i++];             } else {                 a[k] = aux[j++];             }         }     }  }

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