Java排序算法(九):归并排序
归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归 并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
归并排序算法稳定,数组需要O(n)的额外空间,链表需要O(log(n))的额外空间,时间复杂度为O(nlog(n)),算法不是自适应的,不需要对数据的随机读取。
工作原理:
1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
2、设定两个指针,最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4、重复步骤3直到某一指针达到序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾
代码实现:
- public class MergeSortTest {
- 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++];
- }
- // 将临时数组中的内容拷贝回原数组中
- // (原left-right范围的内容被复制回原数组)
- while (tmp <= right) {
- data[tmp] = tmpArr[tmp++];
- }
- }
- 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
http://blog.csdn.net/apei830/article/details/6591632
相关推荐
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
详解Java常用排序算法-归并排序
idea项目:一个主类选择调用6个排序类,记录了学习排序算法的过程,可以自己更改优化,每一种排序是一个类,有需要可以copy走,可重用性强
自己编写的基于java的快速排序和归并算法
Java排序算法:插入,冒泡,选择,Shell,快速排序,归并排序,堆排序,桶式排序,基数排序
java实现的常用的几种基本排序算法,插入、交换、选择、归并
java写的基于比较的各种排序算法,都是一个一个的小函数。简单排序包括:选择排序,插入排序,折半插入排序,冒泡排序。 分治思想的排序包括:归并排序,快速排序,堆排序。 程序把随机生成的整数进行排序,开始时用...
java排序算法汇总 将数据结构里的排序算法使用java实现 包括:归并 快速排序 直接选择 插入。。。。
归并排序 在排序前,先建好一个长度等于原数组长度的临时数组
各类java排序算法: 1.插入排序2.冒泡排序3.选择排序4.Shell排序5.快速排序6.归并排序7.堆排序8.桶式排序9.基数排序
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
Java数据挖掘18大算法实现和10大常见排序算法以及其他相关经典DM算法集合。 18大数据挖掘的经典算法以及代码实现,涉及到了决策分类,聚类,链接挖掘,关联挖掘,模式挖掘等等方面,后面都是相应算法的文章,希望能够...
主要介绍了Java排序算法之归并排序简单实现,具有一定借鉴价值,需要的朋友可以参考下。
自动生成500个随机数,然后对这500个随机数进行归并排序
该工具包含有Java一些比较常见的排序算法和查找算法。 排序算法包括:冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数排序(桶排序) 查找算法包括:线性查找、二分查找、插值查询、斐波那契...
java 基本算法之归并排序实例代码.docx
算法实验(java快速排序。归并排序,分治算法,回溯算法,n后问题)
各类排序算法java的实现,as 插入排序:冒泡排序:选择排序:Shell排序:快速排序:改进后的快速排序:归并排序:改进后的归并排序: 堆排序:SortUtil
Java常用排序算法源码 稳定:冒泡排序、插入排序、归并排序和基数排序;不稳定:选择排序、快速排序、希尔排序、堆排序