归并排序的定义
归并排序算法采用的是分治算法,即把两个(或两个以上)有序表合并成一个新的有序表,即把待排序的序列分成若干个子序列,每个子序列都是有序的,然后把有序子序列合并成整体有序序列,这个过程也称为2-路归并.注意:归并排序的一种稳定排序,即相等元素的顺序不会改变.
归并排序的原理
常见的排序主要有两种,一种是先把待排序的序列一次分割,使子序列的长度减小至1,然后在合并,另外一种是把待排序两两分组排序然后在合并,具体过程用图来解释:
(1) 先分割再合并
待排序序列(14,12,15,13,11,16)
(2) 分组合并
待排序序列(25,57,48,37,12,92,86)
(图片显示不了,无语,有空画一个。)
归并排序实现的示例代码:
#include<stdio.h>
//将有二个有序子数组a[begin...mid]和a[mid+1...end]合并。
void MergeArray(int a[],int begin,int mid,int end,int temp[])
{
int i=begin,j=mid+1;
int m=mid,n=end;
int k=0;
while(i<=m && j<=n)
{
if(a[i]<=a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=m)
temp[k++]=a[i++];
while(j<=n)
temp[k++]=a[j++];
//把temp数组中的结果装回a数组
for(i=0;i<k;i++)
a[begin+i]=temp[i];
}
void mergesort(int a[],int begin,int end,int temp[])
{
if(begin<end)
{
int mid = (begin+end)/2;
mergesort(a,begin,mid,temp); //左边有序
mergesort(a,mid+1,end,temp); //右边有序
MergeArray(a,begin,mid,end,temp); //将左右两边有序的数组合并
}
}
int main()
{
int num[10]={2,5,9,3,6,1,0,7,4,8};
int temp[10];
mergesort(num,0,9,temp);
for(int i=0;i<10;i++)
{
printf("%d",num[i]);
}
printf("\n");
}
归并排序的时间复杂度
归并排序的最好、最坏和平均时间复杂度都是O(nlogn),而空间复杂度是O(n),比较次数介于(nlogn)/2和(nlogn)-n+1,赋值操作的次数是(2nlogn)。因此可以看出,归并排序算法比较占用内存,但却是效率高且稳定的排序算法。
分享到:
相关推荐
排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的...本文主要介绍快速排序算法和归并排序算法的基本概念、原理以及具体的实现方法,并对这两种排序算法的时间复杂度进行分析。
选择排序、冒泡排序、归并排序、快速排序、插入排序的算法原理。不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
归并排序的时间复杂度是 O(n log n),其中 n 是数组的大小。这是因为它需要将数组分解成两半,然后再合并成一个有序的数组。归并排序的空间复杂度是 O(n),因为在合并过程中需要额外的空间来存储临时变量。
该源码使用Qt可以可视化展示归并排序算法实现效果,通过可视化的方式和实时显示算法比较和移动的次数,方便初学者理解归并排序算法的时间复杂度和原理
归并排序的时间复杂度是 O(n log n),其中 n 是数组的大小。这是因为它需要将数组分解成两半,然后再合并成一个有序的数组。归并排序的空间复杂度是 O(n),因为在合并过程中需要额外的空间来存储临时变量。
归并排序 简介 复杂度与稳定性 过程介绍 图示过程 主要代码实现 快速排序 简介 复杂度与稳定性 过程介绍 图示过程 主要代码实现 计数排序 简介 复杂度与稳定性 过程介绍 图示过程 代码实现 桶式...
归并排序一、排序原理二、API设计三、代码实现【Merge .java】【MergeTest .java】【运行结果】四、时间复杂度分析 一、排序原理 简介: 归并排序是建立在归并操作上的一种有效的排序算法 ,该算法是采用分治法的一个...
归并排序归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。值得注意的是归并排序是一种稳定的排序方法。...时间复杂度:时间复杂度为O(nl
通过对这些算法的详细讲解和代码实现,学生将能够深入理解排序算法的原理、时间复杂度、空间复杂度以及实际应用场景。 本教程适用于计算机科学、软件工程和数据科学等专业的学生。在学习过程中,学生将能够掌握各种...
虽然选择排序在效率上不如其他一些排序算法(如快速排序、归并排序等),但它的实现简单,且对于小规模的数据排序非常适用。在处理一些特定问题时,选择排序也表现出较好的性能。例如,在处理接近有序的数据时,选择...
数据结构中九大排序算法:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,堆排序,归并排序,基数排序,就时间复杂度,空间复杂度,稳定性,基本原理的简要总结与比较
六个基础排序算法,分别是冒泡排序,选择排序,插入排序,希尔排序,归并排序和快速排序;2.了解这六种算法的时间复杂度和稳定性; 阅读建议:建议在阅读过程中,可以尽量自己手动敲一遍,让印象更深刻,不要Ctrl+C...
归并排序等,需要熟练掌握其原理、时间复杂度及实现方法。 2.搜索算法:包括深度优先搜索(DFS)和广度优先搜索(BFS),在 图论、树的遍历等场景下应用较为广泛。 3.动态规划算法:动态规划算法是解决最优化问题...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
要求能够手写时间复杂度位O(nlogn)的排序算法:快速排序、归并排序、堆排序 1.冒泡排序 思想:相邻的两个数字进行比较,大的向下沉,最后一个元素是最大的。列表右边先有序。 时间复杂度$O(n^2)$,原地排序,稳定的...
排序算法(平方排序算法的应用,Shell排序,快速排序,归并排序,时间复杂度下界,三种线性时间排 序,外部排序) 数论(整除,集合论,关系,素数,进位制,辗转相除,扩展的辗转相除,同余运算,解线性同余...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...