点击收藏
00 月 00 00:00:00 周几
JSON在线格式化校验工具 - www.qjson.cn

死磕归并排序算法

前端 2023-07-05 17:29:38
59阅读

序言

这篇大家谈一种根据合并实际操作进行排列的优化算法。

归并排序优化算法构思

要将一个数组排序，能够 先将二维数组分成2个二维数组各自排列，随后再将結果归并在一起，反复递归这一全过程，直至二维数组总体井然有序，这就是归并排序的优化算法构思。

归并排序的优势是它可以确保随意长短为N的数组排序需要的時间与 NlogN 正相关，这一优势是初中级排列没法做到的。

缺陷是由于合并实际操作必须引进附加的二维数组，附加的室内空间与N正相关

原地不动合并完成

在完成归并排序以前，大家必须先进行2个井然有序二维数组的合并实际操作，将要2个井然有序的数组合并成一个井然有序的二维数组；

  • 在这里全过程中大家必须引进一个輔助二维数组；
  • 界定的方式 签字为merge(a, lo, mid, hi)，这一方式 将二维数组a[lo..mid]与a[mid..hi]合并成一个井然有序的二维数组，結果储放到a[lo..mid]中；
  • 该方式 中必须应用的上一篇中的公共性涵数 less ，参照上一篇文章《常见的初级排序算法，这次全搞懂》
 
    
  
  1. public class MergeSort implements SortTemplate { 
    2. 
  
  2.     private Comparable[] aux; 
    3. 
  
  3.  
    4. 
  
  4.     @Override 
    5. 
  
  5.     public void sort(Comparable[] array) { 
    6. 
  
  6.         //待完成 
    7. 
  
  7.     } 
    8. 
  
  8.  
    9. 
  
  9.     private void merge(Comparable[] a, int lo, int mid, int hi) { 
    10. 
  
  10.         for (int i = lo; i <= hi; i  ) { 
    11. 
  
  11.             aux[i] = a[i]; 
    12. 
  
  12.         } 
    13. 
  
  13.         int i = lo, j = mid   1; 
    14. 
  
  14.         for (int k = lo; k <= hi; k  ) { 
    15. 
  
  15.             if (i > mid) { 
    16. 
  
  16.                 a[k] = aux[j  ]; 
    17. 
  
  17.             } else if (j > hi) { 
    18. 
  
  18.                 a[k] = aux[i  ]; 
    19. 
  
  19.             } else if (less(aux[i], aux[j])) { 
    20. 
  
  20.                 a[k] = aux[i  ]; 
    21. 
  
  21.             } else { 
    22. 
  
  22.                 a[k] = aux[j  ]; 
    23. 
  
  23.             } 
    24. 
  
  24.         } 
    25. 
  
  25.     } 
    26. 
  
  26.  
    27. 
  
  27. } 
    28.

自顶向下的归并排序

根据分而治之的观念，大的数组排序，先递归拆分为小的二维数组，确保小的二维数组井然有序再合并，直至全部二维数组井然有序，这一实际操作便是自顶向下的归并排序

 
    
  
  1. public class MergeSort implements SortTemplate { 
    2. 
  
  2.     private Comparable[] aux; 
    3. 
  
  3.  
    4. 
  
  4.     @Override 
    5. 
  
  5.     public void sort(Comparable[] array) { 
    6. 
  
  6.         aux = new Comparable[array.length]; 
    7. 
  
  7.         doSort(array, 0, array.length - 1); 
    8. 
  
  8.     } 
    9. 
  
  9.  
    10. 
  
  10.     private void doSort(Comparable[] array, int lo, int hi) { 
    11. 
  
  11.         if (lo >= hi) { 
    12. 
  
  12.             return; 
    13. 
  
  13.         } 
    14. 
  
  14.         int mid = (hi - lo) / 2   lo; 
    15. 
  
  15.         doSort(array, lo, mid); 
    16. 
  
  16.         doSort(array, mid   1, hi); 
    17. 
  
  17.         merge(array, lo, mid, hi); 
    18. 
  
  18.     } 
    19. 
  
  19.  
    20. 
  
  20.     private void merge(Comparable[] a, int lo, int mid, int hi) { 
    21. 
  
  21.         //省去 
    22. 
  
  22.     } 
    23. 
  
  23.  
    24. 
  
  24. } 
    25.

之上编码是规范的递归归并排序实际操作，可是历经细心思索以后，该优化算法也有能够 提升的地区

「检测二维数组是不是早已井然有序」；如果a[mid]<=a[mid 1]，那麼大家就可以绕过merge方式 ，降低merge实际操作；修补以后的doSort方式

 
    
  
  1. private void doSort(Comparable[] array, int lo, int hi) { 
    2. 
  
  2.     if (lo >= hi) { 
    3. 
  
  3.         return; 
    4. 
  
  4.     } 
    5. 
  
  5.     int mid = (hi - lo) / 2   lo; 
    6. 
  
  6.     doSort(array, lo, mid); 
    7. 
  
  7.     doSort(array, mid   1, hi); 
    8. 
  
  8.     if (array[mid].compareTo(array[mid   1]) >= 0) { 
    9. 
  
  9.         merge(array, lo, mid, hi); 
    10. 
  
  10.     } 
    11. 
  
  11. } 
    12.

「针对小规模纳税人的二维数组能够 是用插入排序」；针对小规模纳税人的二维数组应用归并排序会提升递归调用栈，因此我们可以考虑到应用插入排序来解决子二维数组的排列

 
    
  
  1. private void doSort(Comparable[] array, int lo, int hi) { 
    2. 
  
  2.     if (lo >= hi) { 
    3. 
  
  3.         return; 
    4. 
  
  4.     } 
    5. 
  
  5.  
    6. 
  
  6.     if (hi - lo < 5) { //检测，低于5就应用插入排序 
    7. 
  
  7.         insertionSort(array, lo, hi); 
    8. 
  
  8.         return; 
    9. 
  
  9.     } 
    10. 
  
  10.  
    11. 
  
  11.     int mid = (hi - lo) / 2   lo; 
    12. 
  
  12.     doSort(array, lo, mid); 
    13. 
  
  13.     doSort(array, mid   1, hi); 
    14. 
  
  14.     if (less(array[mid   1], array[mid])) { 
    15. 
  
  15.         merge(array, lo, mid, hi); 
    16. 
  
  16.     } 
    17. 
  
  17. } 
    18. 
  
  18.  
    19. 
  
  19. //插入排序 
    20. 
  
  20. private void insertionSort(Comparable[] array, int lo, int hi) { 
    21. 
  
  21.     for (int i = lo; i <= hi; i  ) { 
    22. 
  
  22.         for (int j = i; j > lo && less(array[j], array[j - 1]); j--) { 
    23. 
  
  23.             exch(array, j, j - 1); 
    24. 
  
  24.         } 
    25. 
  
  25.     } 
    26. 
  
  26. } 
    27.

「节约拷贝原素到輔助二维数组的時间」；要完成该实际操作较不便，必须在每一层递归的情况下互换键入数据信息和輸出二维数组的人物角色；改动以后的详细编码以下：

 
    
  
  1. public class MergeSort implements SortTemplate { 
    2. 
  
  2.     private Comparable[] aux; 
    3. 
  
  3.  
    4. 
  
  4.     @Override 
    5. 
  
  5.     public void sort(Comparable[] array) { 
    6. 
  
  6.         aux = array.clone(); 
    7. 
  
  7.         doSort(aux, array, 0, array.length - 1); 
    8. 
  
  8.     } 
    9. 
  
  9.  
    10. 
  
  10.     private void doSort(Comparable[] src, Comparable[] dest, int lo, int hi) { 
    11. 
  
  11.         if (lo >= hi) { 
    12. 
  
  12.             return; 
    13. 
  
  13.         } 
    14. 
  
  14.  
    15. 
  
  15.         if (hi - lo < 5) { //检测，低于5就应用插入排序 
    16. 
  
  16.             insertionSort(dest, lo, hi); 
    17. 
  
  17.             return; 
    18. 
  
  18.         } 
    19. 
  
  19.  
    20. 
  
  20.         int mid = (hi - lo) / 2   lo; 
    21. 
  
  21.         doSort(dest, src, lo, mid); 
    22. 
  
  22.         doSort(dest, src, mid   1, hi); 
    23. 
  
  23.         if (less(src[mid   1], src[mid])) { 
    24. 
  
  24.             merge(src, dest, lo, mid, hi); 
    25. 
  
  25.         } 
    26. 
  
  26.     } 
    27. 
  
  27.  
    28. 
  
  28.     //插入排序 
    29. 
  
  29.     private void insertionSort(Comparable[] array, int lo, int hi) { 
    30. 
  
  30.         for (int i = lo; i <= hi; i  ) { 
    31. 
  
  31.             for (int j = i; j > lo && less(array[j], array[j - 1]); j--) { 
    32. 
  
  32.                 exch(array, j, j - 1); 
    33. 
  
  33.             } 
    34. 
  
  34.         } 
    35. 
  
  35.     } 
    36. 
  
  36.  
    37. 
  
  37.     private void merge(Comparable[] src, Comparable[] dest, int lo, int mid, int hi) { 
    38. 
  
  38.         int i = lo, j = mid   1; 
    39. 
  
  39.         for (int k = lo; k <= hi; k  ) { 
    40. 
  
  40.             if (i > mid) { 
    41. 
  
  41.                 dest[k] = src[j  ]; 
    42. 
  
  42.             } else if (j > hi) { 
    43. 
  
  43.                 dest[k] = src[i  ]; 
    44. 
  
  44.             } else if (less(src[i], src[j])) { 
    45. 
  
  45.                 dest[k] = src[i  ]; 
    46. 
  
  46.             } else { 
    47. 
  
  47.                 dest[k] = src[j  ]; 
    48. 
  
  48.             } 
    49. 
  
  49.         } 
    50. 
  
  50.     } 
    51. 
  
  51.  
    52. 
  
  52. } 
    53.

每一层递归实际操作都是会让子二维数组井然有序，可是子二维数组可能是aux[lo..hi]也是有可能是a[lo..hi]；因为第一次启用doSort传到的是src=aux，dest=array，因此递归最终的結果一定是键入到array中，确保了array总体排列进行

自底向上的归并排序

完成合并优化算法也有另一种构思，便是先合并什么小的二维数组，随后再成对合并获得子二维数组，直至全部二维数组井然有序

 
    
  
  1. public class MergeSort implements SortTemplate { 
    2. 
  
  2.     private Comparable[] aux; 
    3. 
  
  3.  
    4. 
  
  4.     @Override 
    5. 
  
  5.     public void sort(Comparable[] array) { 
    6. 
  
  6.         int length = array.length; 
    7. 
  
  7.         aux = new Comparable[length]; 
    8. 
  
  8.         for (int sz = 1; sz < length; sz  = sz) { 
    9. 
  
  9.             for (int i = 0; i < length - sz; i  = 2 * sz) { 
    10. 
  
  10.                 merge(array, i, i   sz - 1, Math.min(i   2 * sz - 1, length - 1)); 
    11. 
  
  11.             } 
    12. 
  
  12.         } 
    13. 
  
  13.     } 
    14. 
  
  14.  
    15. 
  
  15.     private void merge(Comparable[] a, int lo, int mid, int hi) { 
    16. 
  
  16.         for (int i = lo; i <= hi; i  ) { 
    17. 
  
  17.             aux[i] = a[i]; 
    18. 
  
  18.         } 
    19. 
  
  19.         int i = lo, j = mid   1; 
    20. 
  
  20.         for (int k = lo; k <= hi; k  ) { 
    21. 
  
  21.             if (i > mid) { 
    22. 
  
  22.                 a[k] = aux[j  ]; 
    23. 
  
  23.             } else if (j > hi) { 
    24. 
  
  24.                 a[k] = aux[i  ]; 
    25. 
  
  25.             } else if (less(aux[i], aux[j])) { 
    26. 
  
  26.                 a[k] = aux[i  ]; 
    27. 
  
  27.             } else { 
    28. 
  
  28.                 a[k] = aux[j  ]; 
    29. 
  
  29.             } 
    30. 
  
  30.         } 
    31. 
  
  31.     } 
    32. 
  
  32.  
    33. 
  
  33. } 
    34.
the end
免责声明：本文不代表本站的观点和立场，如有侵权请联系本站删除！本站仅提供信息存储空间服务。

精选推荐

随机推荐