摘要：归并排序是一种十分优秀的排序方法，在一开始学习的时候可能会对它的实现思路有点难以理解，不过当你想通了之后就会发现这种方法的绝妙之处。
归并排序是一种十分优秀的排序方法，在一开始学习的时候可能会对它的实现思路有点难以理解，不过当你想通了之后就会发现这种方法的绝妙之处。
由上图应该可以很清楚的理解到归并排序的基本步骤就是
1.先把一个数组以二分法的方式递归的分组，（分）
2.然后再将相邻的两个数组进行作对比，把两个已排序好的子数组中的数字由小到大（由大到小）地放到辅助数组temp[]中，（合）
3.最后再把辅助数组中的元素复制到原数组中返回。
这种排序的时间复杂度为O(NlgN),同时需要O(N)的辅助空间——保存N个元素。
这是一种稳定的算法。
代码实现如下：
public static void mergeSort(int[] nums) {
//创建与原数组相同长度的数组
int[] temp = new int[nums.length];
mergeSort(nums, temp, 0, nums.length-1);
}
private static void mergeSort(int[] nums, int[] temp, int left, int right) {
if(left < right) {
//从中间将数组分成两半
int mid = (left + right) >> 1;
mergeSort(nums, temp, left, mid);
mergeSort(nums, temp, mid+1, right);
//将两个数组重新合并
merge(nums, temp, left, mid+1, right);
}
}
private static void merge(int[] nums, int[] temp,
int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
//对比左右两个数组并将较小的数先放到辅助数组
while(leftPos <= leftEnd && rightPos <= rightEnd) {
if(nums[leftPos] <= nums[rightPos]) {
temp[tmpPos++] = nums[leftPos++];
}else {
temp[tmpPos++] = nums[rightPos++];
}
}
//把左边数组剩下的原数放到辅助数组
while(leftPos <= leftEnd) {
temp[tmpPos++] = nums[leftPos++];
}
//把右边数组剩下的原数放到辅助数组
while(rightPos <= rightEnd) {
temp[tmpPos++] = nums[rightPos++];
}
//把辅助数组复制到原数组
for(int i = 0; i < numElements; i++,rightEnd--) {
nums[rightEnd] = temp[rightEnd];
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/71259.html
摘要：排序之归并排序简介归并排序的算法是将多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表，则成为二路合并。对于一个原始的待排序数列，往往可以通过分割的方法来归结为多路合并排序。 Java排序之归并排序 1. 简介 归并排序的算法是将多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表，则成为二路合并。对于一个原始的待排序数列，往往可以通过分割的方法来归结为多路合...
摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。 常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...
摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。 常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...
摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。 常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...
摘要：本文介绍几种常见排序算法选择排序，插入排序，希尔排序，归并排序，快速排序，堆排序，对算法的思路性质特点具体步骤实现以及图解进行了全面的说明。最后对几种排序算法进行了比较和总结。 本文介绍几种常见排序算法（选择排序，插入排序，希尔排序，归并排序，快速排序，堆排序），对算法的思路、性质、特点、具体步骤、java实现以及trace图解进行了全面的说明。最后对几种排序算法进行了比较和总结。 写...
阅读 3212·2021-09-22 15:49
阅读 3082·2021-09-08 09:35
阅读 1252·2019-08-30 15:55
阅读 2109·2019-08-30 15:44
阅读 536·2019-08-29 16:59
阅读 1496·2019-08-29 16:16
阅读 331·2019-08-28 18:06
阅读 763·2019-08-27 10:55
