java归并_java归并排序
概述
归并排序与快速排序相同，同样是借鉴二叉树的思想，时间复杂度O(n),与快速排序一样是大量数据排序的最优方式之一。
思路分析
归并排序是将目标数组分成左右两个数组，左右两个数组必须是有序的，然后对这两个数组合并从而实现排序。对于任意的数组都可以将所有的数据分成若干个数组，每个数组中都只有一个元素，然后两两合并。(因此，归并排序的内存开销会比快速排序多)
代码实现private void mergeSort(int[] array, int left, int right) { if (left >= right) { return;
} int mid = (left + right) >> 1;
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
merge(array, left, mid + 1, right);
} private void merge(int[] array, int left, int mid, int right) { int leftSize = mid - left; int rightSize = right - mid + 1; int[] leftArray = new int[leftSize]; int[] rightArray = new int[rightSize];
System.arraycopy(array, left, leftArray, 0, leftSize);
System.arraycopy(array, mid, rightArray, 0, rightSize); int index=left; int leftIndex = 0; int rightIndex = 0; while (leftIndex
}else { array[index++] = rightArray[rightIndex++];
}
} while (leftIndex
} while (rightIndex
}
}
测试代码@Test public void testMergeSort() { int[] array = new int[]{1, 3, 4, 10, 2, 5, 6, 9, 7, 8};
mergeSort(array, 0, array.length - 1); for (int i = 0; i
System.out.println(array[i]);
}
}
结果打印1
2
3
4
5
6
7
8
9
10
作者：夜亦明
链接：https://www.jianshu.com/p/31f982cac502