归并排序的思想是把一个要排序的数据分成两份,把每一份排好序,然后通过merge()(合并)方法把两个数组归并成一个有序的数组。。。
通过递归的方法。一份变两份,两份变四份,四份变八份。。。。当分到最后只有一个元素的时候,每一份都是有序的了,因为只有一个元素嘛。然后再把每一份排好序的merge()回来,也就是一个变两个,两个变四个,四个变 八个。。。。组成一个原来长度的有序的数组。
归并排序的时间复杂度为(NlogN),相比较插入排序,选择排序,冒泡排序等时间复杂度为(N^2)的,时间效率上还是提高了很多。比如对100个数据进行排序,插入排序的就为100^2 = 10000,而归并排序为100*log100 = 100*2 = 200,10000/200 = 50(倍),应该没算错,再次展现了我雄厚的小学数学知识。这还只是100个数据,要是更大的数据量,相差的倍数会更大,因为logN是个神奇的函数,不信可以试试。
但是归并排序有一个缺点,也是最大的弱点,就是他需要在内存中开辟一个大小等于待排序数组的数组,有点绕,应该能懂,这个数组就是用在merge()的时候,把已排好序的小的数组merge()到这个新的数组中。
下面是归并排序的一个简单的流程:
上代码:
package 归并排序; /** * 归并排序 * * @author TMs * */ public class MergeSort { public static void main(String[] args) { int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; print(data); mergeSort(data); System.out.println("排序后的数组:"); print(data); } public static void mergeSort(int[] data) { sort(data, 0, data.length - 1); } public static void sort(int[] data, int left, int right) { if (left >= right) return; // 找出中间索引 int center = (left + right) / 2; // 对左边数组进行递归 sort(data, left, center); // 对右边数组进行递归 sort(data, center + 1, right); // 合并 merge(data, left, center, right); print(data); } /** * 将两个数组进行归并,归并前面2个数组已有序,归并后依然有序 * * @param data * 数组对象 * @param left * 左数组的第一个元素的索引 * @param center * 左数组的最后一个元素的索引,center+1是右数组第一个元素的索引 * @param right * 右数组最后一个元素的索引 */ public static void merge(int[] data, int left, int center, int right) { // 临时数组 int[] tmpArr = new int[data.length]; // 右数组第一个元素索引 int mid = center + 1; // third 记录临时数组的索引 int third = left; // 缓存左数组第一个元素的索引 int tmp = left; while (left <= center && mid <= right) { // 从两个数组中取出最小的放入临时数组 if (data[left] <= data[mid]) { tmpArr[third++] = data[left++]; } else { tmpArr[third++] = data[mid++]; } } // 剩余部分依次放入临时数组(实际上两个while只会执行其中一个) while (mid <= right) { tmpArr[third++] = data[mid++]; } while (left <= center) { tmpArr[third++] = data[left++]; } // 将临时数组中的内容拷贝回原数组中 // (原right-left范围的内容被复制回原数组) while (tmp <= right) { data[tmp] = tmpArr[tmp++]; } } /** * 打印数组中的元素 * @param data */ public static void print(int[] data) { for (int i = 0; i < data.length; i++) { System.out.print(data[i] + "\t"); } System.out.println(); } }
打印结果,从结果看他的过程:
5 3 6 2 1 9 4 8 7 3 5 6 2 1 9 4 8 7 3 5 6 2 1 9 4 8 7 3 5 6 1 2 9 4 8 7 1 2 3 5 6 9 4 8 7 1 2 3 5 6 4 9 8 7 1 2 3 5 6 4 9 7 8 1 2 3 5 6 4 7 8 9 1 2 3 4 5 6 7 8 9 排序后的数组: 1 2 3 4 5 6 7 8 9
每天做点事,加油咯!
相关推荐
C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序
C语言二路归并排序算法, 写了个二路归并的归并排序小代码,直接贴上来
C++排序算法之归并排序源码
算法设计,给出归并排序的C++实现代码,并利用给随机数方式求运行时间
二路归并算法 排序 归并排序
根据算法导论实现的归并排序算法
易语言归并排序算法源码,归并排序算法,归并排序,子程序_有序数组合并
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
本人自己写的一些排序算法,这是系列1归并排序算法实现,
算法设计实验报告,包括:快速排序和归并排序两种算法各自的基本思想、时间复杂度分析,C++实现代码,两种算法运行时间的比较,运行截图,实验心得。
各种常用c++排序算法,包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
理解归并排序的算法思想及其算法设计理解归并排序的算法思想及其算法设计
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
MATLAB实现《算法设计与分析》中的插入排序、二分归并排序、归并排序实验,其中包括.m文件和实验报告,安徽大学本科课程。
归并排序算法,有程序和复杂性分析,还有解释,挺清楚的,很有用
归并排序 在排序前,先建好一个长度等于原数组长度的临时数组
归并排序算法C语言版
%mergesort 分治算法——归并排序 %divide——将数组一分为二 %conquer——对两部分数组分别排序 %combine——将各自排好序的数组融合 %以此类推递归调用