归并排序 O(N*logN) 是另一种效率很高的排序方法。"归并"的含义就是将两个或两个以上的有序表组合成一个有序表。加入两个有序表的长度分别为m、n,则一次归并的时间复杂度为O(m+n)。
我们可以用"归并"的思想来实现排序。假如待排序列含有n个关键字,则可看成是n个有序的子序列,每个序列长度为1,然后两两归并,得到[n/2]个长度为2或1的子序列,在两两归并....,知道得到一个长度为n的有序序列为止。这就是2-路归并算法。
下图就是2-路归并排序的一个例子:
我们可以用分治的思想解决归并排序,给定一个有N个关键字的有序序列,分治法的步骤如下:
(1)划分: 如果S中有1个元素,则直接返回S,因为它已经有序了。否则(S中至少有两个元素),把它们分别放入两个序列S1和S2中,S1和S2各包含大约S中的一半元素,即S1包含S中的前[N/2]个元素,S2包含S中的后[N/2]个元素。
(2)递归:递归求解子问题S1和S2。
(3)求解:归并有序序列S1和S2,使得他们成为一个有序序列,将其中的元素放回S中。
#include<iostream.h>
#include<malloc.h>
/************************
* 归并排序 Merge Sort *
***********************/
class MergeSort{
public:
//递增排序
static void inc_sort(int keys[], int size);
private:
//归并排序算法
static void merge_sort(int raw[], int *merged, int s, int t);
//归并
static void merge(int raw[], int *merged, int si, int mi, int ti);
};
void MergeSort:: merge(int raw[], int *merged, int si, int mi, int ti){
//把已近排序号的si-mi,mi-ti两个序列赋值给raw
for(int t=si;t<=ti;t++)
raw[t]=merged[t];
//归并
int i=si,j=mi+1,k=si;
for(;i<=mi&&j<=ti;){
if(raw[i]<=raw[j]) merged[k++]=raw[i++];
else merged[k++]=raw[j++];
}
if(i<=mi)
for(int x=i;x<=mi;)
merged[k++]=raw[x++];
if(j<=ti)
for(int y=j;y<=ti;)
merged[k++]=raw[y++];
}
//划分
void MergeSort:: merge_sort(int raw[], int *merged, int s, int t){
if(s==t) merged[s]=raw[s];
else{
int m=(s+t)/2;
MergeSort::merge_sort(raw, merged, s, m);
MergeSort::merge_sort(raw, merged, m+1,t);
MergeSort::merge(raw, merged, s,m,t);
}
}
void MergeSort:: inc_sort(int keys[],int size){
int * merged=(int *)malloc(size*sizeof(int));
MergeSort::merge_sort(keys,merged,0,size-1);
//打印排序结果
for(int i=0;i<size;i++)
cout<<merged[i]<<" ";
cout<<endl;
free(merged);
}
//Test MergeSort
void main(){
int raw[]={49,38,65,97,76,13,27,49};
int size=sizeof(raw)/sizeof(int);
MergeSort::inc_sort(raw,size);
}
代价分析:
上图可以看出,一个N关键字的序列,两两归并可以构造一棵高度为[logN]的归并排序树。而每一次归并的时间复杂度为O(m+n)。因此每一趟归并的时间复杂度为O(N),如上图。归并排序算法的总时间复杂度为O(N*logN) 。其所需要的辅助空间就是一个能容纳中间合并结果的数量为N的连续空间。因此空间复杂度为O(N) 。是稳定排序方法 。
分享到:
相关推荐
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
数据结构排序选择排序归并排序基数排序PPT学习教案.pptx
随机产生1000个0~9的数,并分别用堆排序,快速排序,归并排序将产生的这1000个随机数排序,并将排序结果写入文件
关于序列的归并排序,涉及到序列的长度
《数据结构》严蔚敏版——归并排序
归并排序,排序等算法,数据结构,快速排序,链表排序归并排序,排序等算法,数据结构,快速排序,链表排序
归并排序,两种实现方法,一种是递归实现,另一种是非递归实现……可直接在vc6.0平台上编译运行,并按要求输入,便可从小到大的顺序输出……
数据结构:快速排序、堆排序、归并排序、希尔排序 c++实现
(1)输入一组数,用递归和非递归程序实现归并排序 (2)分析归并排序的复杂度 (3)将归并排序的思想用于外部排序中
快速排序、归并排序、堆排序 并比较排序时间 数据结构与算法
本章主要介绍一些常用的排序算法:插入排序、交换排序、选择排序、归并排序和基数排序。这里介绍的排序算法都是基于待排序的数据元素序列构成的线性表采用顺序存储结构,即采用数组存储,并且默认为按关键字非递减...
归并排序 经典数据结构算法 ppt.
合并排序(MERGE SORT)是又一类不同的排序方法,合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并算法。它的基本思想就是假设数组A有N个元素,那么可以看成数组A是又N个...
数据结构中的内部排序法 归并排序 非常的好用
归并排序 实验题目:归并排序 实验要求:对输入的一组数据利用归并排序算法进行排序并输出 1 需求分析 本实验要求对输入的一组数据利用归并排序算法进行排序并输出。 归并排序是利用归并过程的算法。所谓归并,是指...
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
数据结构-归并排序 PPT文档
二路归并和多路归并排序PPT数据结构课件