归并排序中的“归并”的意思是将两个或者两个以上的有序表组合成一个新的有序表。他的实现无论是顺序存储结构还是链表结构,都可以在O(m+n)的时间级上实现。
复杂度:
时间复杂度:O(nlogn)
空间复杂度:O(n)
用途:
1、排序(速度仅次于快速排序,但较稳定)
2、求逆序对数
在实现单数组的归并排序之前,首先了解一下双数组的归并排序
这个双数组归并的前提是两个数组a和b都是已经排序好的
package sort;
import java.util.Arrays;
public class Test1 {
public static void main(String args[])
{
int a[]={1,2,3,4,6,7,8,10};
int b[]={1,2,5,9};
int c[] = new int[a.length+b.length];
mergeSort(a,a.length,b,b.length,c);
System.out.println(Arrays.toString(c));
}
public static void mergeSort(int a[],int n,int b[],int m,int c[])
{
int i,j,k;
i=j=k=0;
//只有满足i<n&&j<m才执行,分别扫描两个数组,将数组中的元素进行对比,从小到大赋值给临时数组c
while(i<n&&j<m)
{
if(a[i]<b[j])
c[k++]=a[i++];
else
c[k++]=b[j++];
}
//将剩余的a数组的元素放入c中
while(i<n)
{
c[k++]=a[i++];
}
//将剩余的b数组的元素放入c中
while(j<m)
{
c[k++]=b[j++];
}
}
}
运行结果如下:
[1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10]
下面开始实现单数组的归并排序算法
例如:49 38 65 97 76 13 27
思想:首先将数组中个单独的一个元素作为一个已经排序好的序列,然后,将两两相邻的元素进行归并排序,依次类推,直到最后归并为一个排序好的序列
如上图:
首先将每个元素作为一个已经排序好的序列,一共7个序列
然后,将每两个相邻的序列归并为一个序列,如49 38归并排序后变成 38 49,依次分成了4个序列,然后再将之前已经排序好的两个相邻的序列进行排序,变成2个序列,每个序列都是排序好的,最后归并为一个排序好的序列
实现代码:
package sort;
import java.util.Arrays;
public class MergeSort {
public static void main(String args[])
{
int[] array = {49,38,65,97,76,13,27};
System.out.println(Arrays.toString(array));
System.out.println("---------排序前-------------");
mergeSort(array,0,array.length-1);
System.out.println("---------排序后-------------");
System.out.println(Arrays.toString(array));
}
/**
* 这里依然需要递归来达到数组元素的排序,如果有两个已有元素的数组的话,就不用这么麻烦您了
* 不过这种归并排序依然是效率最好的排序方法之一,而且还是稳定的(相比快速排序,快速排序不稳定)
*/
public static void mergeSort(int array[],int low,int high)
{
if(low<high)
{
mergeSort(array,low,(low+high)/2);//左边排序
mergeSort(array,(low+high)/2+1,high);//右边排序
merge(array,low,(high+low)/2,high);//将两个序列归并为一个序列
System.out.println(Arrays.toString(array));
}
}
public static void merge(int array[],int low,int mid,int high)
{
int temp[]=new int[high-low+1];
int i = low;
int j = mid+1;
int k=0;
/**
* 将array数组分成两个数组来扫描,每一次都会将前后相邻的两个有序的序列归并为一个有序的序列
*/
while(i<=mid&&j<=high)
{
if(array[i]<=array[j])
temp[k++]=array[i++];
else
temp[k++]=array[j++];
}
//下面这两种while循环每次只执行其中一个
//将剩余的array[i]存入temp中
while(i<=mid)
{
temp[k++]=array[i++];
}
//将剩余的array[j]存放到temp中
while(j<=high)
{
temp[k++]=array[j++];
}
for(int m=0;m<temp.length;m++)
{
array[low+m]=temp[m];
}
}
}
运行结果如下:
[49, 38, 65, 97, 76, 13, 27]
---------排序前-------------
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 13, 76, 27]
[38, 49, 65, 97, 13, 27, 76]
[13, 27, 38, 49, 65, 76, 97]
---------排序后-------------
[13, 27, 38, 49, 65, 76, 97]
- 大小: 4.8 KB
分享到:
相关推荐
详解Java常用排序算法-归并排序
排序算法-归并排序详细讲解(MergeSort)
基于python的排序算法-归并排序Merge Sort
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - 选择排序Selection sort 经典排序算法 - 鸡尾酒排序Cocktail sort 经典排序算法 - 希尔排序Shell sort 经典排序算法 - ...
算法-数据结构和算法-14-归并排序.rar
算法-理论基础- 排序- 归并排序(包含源程序).rar
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序,很有意思,可以下载看看!
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
归并排序,排序等算法,数据结构,快速排序,链表排序归并排序,排序等算法,数据结构,快速排序,链表排序
算法设计,给出归并排序的C++实现代码,并利用给随机数方式求运行时间
大数据-算法-基于归并的高效排序算法的研究.pdf
python 归并排序算法 归并排序是一种基于分治思想的排序算法,它将待排序的序列分成若干个子序列,每个子序列都是有序的,然后再将这些有序的子序列合并成一个有序的序列。归并排序的时间复杂度为O(nlogn),是一种...
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序...
C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序
十大经典排序算法 ... (2)排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部...常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
根据算法导论实现的归并排序算法