当前位置: 代码迷 >> 综合 >> 排序专题(三) / 稳定的内部排序 / 递归的2-路归并排序
  详细解决方案

排序专题(三) / 稳定的内部排序 / 递归的2-路归并排序

热度:19   发布时间:2024-01-16 21:47:00.0
  • 递归的2-路归并排序
    • 平均时间复杂度:O(nlogn)
    • 算法思想,见图:
    • 递归实现很简单,发帖出来一定程度上只是为了保证这个排序专题的完整性,望勿拍
    • 直接上code:
    • public class MergeSort {/**  Merge these two parts : *      "fromIndex --> splitPoint"*      "splitPoint + 1 --> toIndex"*/private static void merge(int[] array, int fromIndex, int splitPoint, int toIndex) {int[] tempArray = new int[toIndex - fromIndex + 1];int index = 0;int i = fromIndex;int j = splitPoint + 1;while (i <= splitPoint && j <= toIndex) {if (array[i] < array[j]) {tempArray[index ++] = array[i ++];} else if (array[i] == array[j]) {tempArray[index ++] = array[i ++];tempArray[index ++] = array[j ++];} else {tempArray[index ++] = array[j ++];}}while (i <= splitPoint) {tempArray[index ++] = array[i ++];}while (j <= toIndex) {tempArray[index ++] = array[j ++];}for (int k = fromIndex, m = 0; k <= toIndex; k ++) {array[k] = tempArray[m ++];}}public static void mergeSort(int[] array, int fromIndex, int toIndex) {int splitPoint = fromIndex + (toIndex - fromIndex) / 2;if (fromIndex == toIndex) {return;}mergeSort(array, fromIndex, splitPoint);mergeSort(array, splitPoint + 1, toIndex);merge(array, fromIndex, splitPoint, toIndex);}}

  相关解决方案