归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。
图示
归并排序采用分治的思想来将一个大问题分解为多个小问题,并通过合并已排序的子问题来解决原始问题。
归并排序的时间复杂度是O(nlogn),其中n是待排序数组的大小。它是一种稳定的排序算法,适用于各种不同类型的数据。
归并排序的优点是它具有良好的稳定性和可预测性,而且在处理大型数据集时也表现良好。然而,它需要额外的空间来存储临时数组,因此在空间有限的情况下可能不是最佳选择。
基本算法
1、分离
将已有数列不断分离成两段长度基本相同(当已有数列长度是奇数时,则一半长一半短),直到分离成长度为 1 的 n 个数列(其实就是 n 个数)。
2、合并
将两个已排序的子数组合并为一个新的已排序数组。合并操作通过比较两个子数组的元素,并按照顺序将它们逐个放入新数组中。
3、递归
对每个子数组重复上述两个步骤,直到所有子数组都被合并为一个完整的已排序数组。
4、图片讲解
将一个无序数列排好序:
先是分离成长度为 1 的 n 个数列,然后再合并,合并过程中两个红色区域代表两两比较,然后将小的放在前面。
C++程序实现
#include <bits/stdc++.h>
using namespace std;
int n,a[12000],b[12000];
//合并函数
void merge(int low,int mid,int high) //归并
//low 和 mid 分别是要合并的第一个数列的开头和结尾,mid+1 和 high 分别是第二个数列的开头和结尾
{
int i=low,j=mid+1,k=low;
//i、j 分别标记第一和第二个数列的当前位置,k 是标记当前要放到整体的哪一个位置
while (i<=mid && j<=high) //如果两个数列的数都没放完,循环
{
if (a[i]<a[j])
b[k++]=a[i++];
else
b[k++]=a[j++]; //将a[i] 和 a[j] 中小的那个放入 b[k],然后将相应的标记变量增加
} // b[k++]=a[i++] 和 b[k++]=a[j++] 是先赋值,再增加
while (i<=mid)
b[k++]=a[i++];
while (j<=high)
b[k++]=a[j++]; //当有一个数列放完了,就将另一个数列剩下的数按顺序放好
for (int i=low;i<=high;i++)
a[i]=b[i]; //将 b 数组里的东西放入 a 数组,因为 b 数组还可能要继续使用
}
//分离函数
void mergesort(int x,int y) //分离,x 和 y 分别代表要分离数列的开头和结尾
{
if (x>=y) return; //如果开头 ≥ 结尾,那么说明数列分完了,就要返回
int mid=(x+y)/2; //将中间数求出来,用中间数把数列分成两段
mergesort(x,mid);
mergesort(mid+1,y); //递归,继续分离
merge(x,mid,y); //分离完之后就合并
}
int main()
{
cin >>n;
for (int i=1;i<=n;i++)
cin >>a[i];
mergesort(1,n); //调用函数
for (int i=1;i<=n;i++)
cout <<a[i] <<" ";
return 0;
}
总结
归并排序是一种重要的排序算法,对于理解和学习其他高级排序算法也非常有帮助。 今天我们学习了排序中又快又稳定的算法:归并排序,时间复杂度为 O(n log n) 。