归并排序 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) 。是稳定排序方法 。
分享到:
相关推荐
本文将深入探讨三种常见的高效排序算法:堆排序、快速排序和归并排序。它们都是基于不同的原理和策略,具有各自的优势和适用场景。 首先,堆排序是一种基于比较的排序算法,利用了二叉堆的数据结构。二叉堆是一个...
直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序和二路归并排序是计算机科学中经典的排序算法,它们在数据处理和算法学习中占有重要地位。这些排序算法各有特点,适用场景不同,下面将逐一详细介绍,并结合...
《数据结构》严蔚敏版是计算机科学的经典教材,其中对归并排序有深入的阐述。下面我们将详细探讨归并排序的原理、实现方式以及其在实际应用中的优势。 一、归并排序的基本概念 归并排序的核心思想是将大问题分解为...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
数据结构排序选择排序归并排序基数排序PPT学习教案.pptx
归并排序(Merge Sort)是一种非常有效的排序算法,尤其在处理大量数据时表现出良好的稳定性和效率。 归并排序的基本思想源于分治法,即将大问题分解为小问题来解决。在归并排序中,我们首先将待排序的序列拆分为两...
关于序列的归并排序,涉及到序列的长度
以下是关于"插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序"这十大经典排序算法的详细解释: 1. 插入排序:插入排序是一种简单的排序算法,它通过构建有序...
在本资源中,我们主要关注的是使用MATLAB编程语言实现三种经典的排序算法:插入排序、二分归并排序以及归并排序。这些算法是计算机科学基础中的重要组成部分,特别是在算法设计与分析领域。MATLAB是一种强大的数值...
以下是关于"冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序"这七种常见排序算法的源码实现及相关知识点的详细解释: 1. **冒泡排序**:冒泡排序是一种简单的排序算法,它重复地遍历待排序的...
本主题将深入探讨四种常见的排序算法:归并排序、快速排序以及与链表相关的排序方法。 首先,我们来讨论归并排序(Merge Sort)。这是一种基于分治策略的排序算法。归并排序将大问题分解为小问题,然后逐步合并这些...
根据给定的文件信息,我们将深入探讨两种经典的排序算法——快速排序和归并排序,并结合Java语言实现进行详细解析。 ### 快速排序算法 快速排序是一种高效的排序算法,采用分而治之的策略,其核心思想是选择一个...
【归并排序】是一种高效的排序算法,基于分治策略。它的基本思想是将大问题分解成小问题,然后逐个解决。在归并排序中,我们首先将一个未排序的数组拆分成多个只包含一个元素的子数组,然后通过不断地合并这些子数组...
归并排序是一种高效的排序算法,基于分治策略。在Java中实现归并排序,我们可以创建一个名为`MergeSort`的类来封装整个过程。归并排序的基本思想是将待排序的序列分成两个或更多的子序列,对每个子序列分别进行排序...
4. **归并排序**: 归并排序是分治策略的典型应用,它将大问题分解为小问题,再将小问题的解合并起来。首先将序列分为两半,对每一半进行排序,然后将两个已排序的半序列合并成一个完整的有序序列。归并排序的时间...
4. 归并排序:同样基于分治策略,将数组分成两半,分别进行排序,然后合并两个已排序的子数组。归并排序是稳定的排序算法,时间复杂度为O(n log n)。 5. 插入排序:对于未排序的元素,依次将其插入到已排序部分的...
本项目涵盖了五种经典的排序算法:快速排序、堆排序、归并排序、插入排序和选择排序。接下来,我们将深入探讨这些算法的原理、实现及性能特点。 1. **快速排序**: 快速排序由C.A.R. Hoare在1960年提出,是一种采用...
**三路归并排序**是一种高效的排序算法,尤其在处理含有大量重复元素的序列时表现优秀。该算法基于归并排序的思想,但将其分为三...在C语言中,通过合理的指针管理和递归结构,可以实现清晰且高效的三路归并排序算法。
快速排序、归并排序和堆排序都是经典且高效的排序算法,它们各自具有独特的实现方式和性能特点。这篇文章将详细探讨这三个排序算法,并对比它们的时间复杂度。 首先,我们来看快速排序。快速排序由C.A.R. Hoare在...
- 在C#中,归并排序通常用递归实现,通过两个辅助数组进行合并操作。 7. **基数排序**(Radix Sort): - 基数排序不是比较型排序,而是利用数字的位数进行排序。从低位到高位,对每个位数进行一次分配排序,如桶...