一、合并排序
基本思想：把待排序列分解成两个规模大致相等的子序列。如果不易解决，再将得到的子序列继续分解，直到子序列中包含的元素个数为1.因为单个元素的序列本身有序，此时便可以进行合并，从而得到一个完整的有序序列
-
算法思想：基于分治策略
- 分解：将待排序列分成规模大致相等的两个子序列
- 治理：对两个子序列进行合并排序
- 合并：将排好序的的有序子序列进行合并，得到最终的有序序列
时间复杂度：n log n
二、AcWing模板
模板题：AcWing 787. 归并排序
//
// Created by zk on 2021/6/1.
//
#include <iostream>
using namespace std;
const int N = 1000010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r){
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid+1, r);
int k = 0;
int i = l;
int j = mid + 1;
while(i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k ++] = q[j++];
while(i <= mid) tmp[k ++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(i=l, j=0; i<=r; i++, j++) q[i] = tmp[j];
}
int main(){
scanf("%d", &n);
for(int i=0; i<n; i++) scanf("%d", &q[i]);
merge_sort(q, 0, n-1);
for(int i=0; i<n; i++) printf("%d ", q[i]);
return 0;
}
三、趣学数据结构版
#include<iostream>
using namespace std;
void Merge(int A[],int low,int mid,int high)//合并函数
{
int *B=new int[high-low+1];//申请一个辅助数组
int i=low,j=mid+1,k=0;
while(i<=mid&&j<=high) {//按从小到大存放到辅助数组B[]中
if(A[i]<=A[j])
B[k++]=A[i++];
else
B[k++]=A[j++];
}
while(i<=mid) B[k++]=A[i++];//将数组中剩下的元素放置B中
while(j<=high) B[k++]=A[j++];
for(i=low,k=0;i<=high;i++)
A[i]=B[k++];
delete []B;//释放空间
}
void MergeSort(int A[],int low,int high)//合并排序
{
if(low<high)
{
int mid=(low+high)/2;//取中点
MergeSort(A,low,mid);//对A[low:mid]中的元素合并排序
MergeSort(A,mid+1,high);//对A[mid+1:high]中的元素合并排序
Merge(A,low,mid,high);//合并
}
}
int main()
{
int n, A[100];
cout<<"请输入数列中的元素个数n为："<<endl;
cin>>n;
cout<<"请依次输入数列中的元素："<<endl;
for(int i=0;i<n;i++)
cin>>A[i];
MergeSort(A,0,n-1);
cout<<"合并排序结果："<<endl;
for(int i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
return 0;
}
四、陈越版
更加专业
- 递归实现
/* 归并排序 - 递归实现 */
/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
int LeftEnd, NumElements, Tmp;
int i;
LeftEnd = R - 1; /* 左边终点位置 */
Tmp = L; /* 有序序列的起始位置 */
NumElements = RightEnd - L + 1;
while( L <= LeftEnd && R <= RightEnd ) {
if ( A[L] <= A[R] )
TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
else
TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
}
while( L <= LeftEnd )
TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
while( R <= RightEnd )
TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
for( i = 0; i < NumElements; i++, RightEnd -- )
A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}
void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{ /* 核心递归排序函数 */
int Center;
if ( L < RightEnd ) {
Center = (L+RightEnd) / 2;
Msort( A, TmpA, L, Center ); /* 递归解决左边 */
Msort( A, TmpA, Center+1, RightEnd ); /* 递归解决右边 */
Merge( A, TmpA, L, Center+1, RightEnd ); /* 合并两段有序序列 */
}
}
void MergeSort( ElementType A[], int N )
{ /* 归并排序 */
ElementType *TmpA;
TmpA = (ElementType *)malloc(N*sizeof(ElementType));
if ( TmpA != NULL ) {
Msort( A, TmpA, 0, N-1 );
free( TmpA );
}
else printf( "空间不足" );
}
- 循环实现
/* 归并排序 - 循环实现 */
/* 这里Merge函数在递归版本中给出 */
/* length = 当前有序子列的长度*/
void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length )
{ /* 两两归并相邻有序子列 */
int i, j;
for ( i=0; i <= N-2*length; i += 2*length )
Merge( A, TmpA, i, i+length, i+2*length-1 );
if ( i+length < N ) /* 归并最后2个子列*/
Merge( A, TmpA, i, i+length, N-1);
else /* 最后只剩1个子列*/
for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}
void Merge_Sort( ElementType A[], int N )
{
int length;
ElementType *TmpA;
length = 1; /* 初始化子序列长度*/
TmpA = malloc( N * sizeof( ElementType ) );
if ( TmpA != NULL ) {
while( length < N ) {
Merge_pass( A, TmpA, N, length );
length *= 2;
Merge_pass( TmpA, A, N, length );
length *= 2;
}
free( TmpA );
}
else printf( "空间不足" );
}
五、 可视化展示
- Data Structure Visualization: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
merge sort
- VisuAlgo: https://visualgo.net/zh
merge sort
- algorithm-visualizer: https://algorithm-visualizer.org/
merge sort
