一辕狰、合并排序
基本思想：把待排序列分解成兩個(gè)規(guī)模大致相等的子序列勋眯。如果不易解決浪箭，再將得到的子序列繼續(xù)分解穗椅，直到子序列中包含的元素個(gè)數(shù)為1.因?yàn)閱蝹€(gè)元素的序列本身有序，此時(shí)便可以進(jìn)行合并奶栖，從而得到一個(gè)完整的有序序列
-
算法思想：基于分治策略
- 分解：將待排序列分成規(guī)模大致相等的兩個(gè)子序列
- 治理：對(duì)兩個(gè)子序列進(jìn)行合并排序
- 合并：將排好序的的有序子序列進(jìn)行合并匹表，得到最終的有序序列
時(shí)間復(fù)雜度：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;
}
三驼抹、趣學(xué)數(shù)據(jù)結(jié)構(gòu)版
#include<iostream>
using namespace std;
void Merge(int A[],int low,int mid,int high)//合并函數(shù)
{
int *B=new int[high-low+1];//申請(qǐng)一個(gè)輔助數(shù)組
int i=low,j=mid+1,k=0;
while(i<=mid&&j<=high) {//按從小到大存放到輔助數(shù)組B[]中
if(A[i]<=A[j])
B[k++]=A[i++];
else
B[k++]=A[j++];
}
while(i<=mid) B[k++]=A[i++];//將數(shù)組中剩下的元素放置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;//取中點(diǎn)
MergeSort(A,low,mid);//對(duì)A[low:mid]中的元素合并排序
MergeSort(A,mid+1,high);//對(duì)A[mid+1:high]中的元素合并排序
Merge(A,low,mid,high);//合并
}
}
int main()
{
int n, A[100];
cout<<"請(qǐng)輸入數(shù)列中的元素個(gè)數(shù)n為："<<endl;
cin>>n;
cout<<"請(qǐng)依次輸入數(shù)列中的元素："<<endl;
for(int i=0;i<n;i++)
cin>>A[i];
MergeSort(A,0,n-1);
cout<<"合并排序結(jié)果："<<endl;
for(int i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
return 0;
}
四桑孩、陳越版
更加專業(yè)
- 遞歸實(shí)現(xiàn)
/* 歸并排序 - 遞歸實(shí)現(xiàn) */
/* L = 左邊起始位置, R = 右邊起始位置, RightEnd = 右邊終點(diǎn)位置*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* 將有序的A[L]~A[R-1]和A[R]~A[RightEnd]歸并成一個(gè)有序序列 */
int LeftEnd, NumElements, Tmp;
int i;
LeftEnd = R - 1; /* 左邊終點(diǎn)位置 */
Tmp = L; /* 有序序列的起始位置 */
NumElements = RightEnd - L + 1;
while( L <= LeftEnd && R <= RightEnd ) {
if ( A[L] <= A[R] )
TmpA[Tmp++] = A[L++]; /* 將左邊元素復(fù)制到TmpA */
else
TmpA[Tmp++] = A[R++]; /* 將右邊元素復(fù)制到TmpA */
}
while( L <= LeftEnd )
TmpA[Tmp++] = A[L++]; /* 直接復(fù)制左邊剩下的 */
while( R <= RightEnd )
TmpA[Tmp++] = A[R++]; /* 直接復(fù)制右邊剩下的 */
for( i = 0; i < NumElements; i++, RightEnd -- )
A[RightEnd] = TmpA[RightEnd]; /* 將有序的TmpA[]復(fù)制回A[] */
}
void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{ /* 核心遞歸排序函數(shù) */
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( "空間不足" );
}
- 循環(huán)實(shí)現(xiàn)
/* 歸并排序 - 循環(huán)實(shí)現(xiàn) */
/* 這里Merge函數(shù)在遞歸版本中給出 */
/* length = 當(dāng)前有序子列的長(zhǎng)度*/
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個(gè)子列*/
Merge( A, TmpA, i, i+length, N-1);
else /* 最后只剩1個(gè)子列*/
for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}
void Merge_Sort( ElementType A[], int N )
{
int length;
ElementType *TmpA;
length = 1; /* 初始化子序列長(zhǎng)度*/
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
