動(dòng)畫演示地址
https://visualgo.net/zh/sorting
數(shù)組排序任務(wù)可以如下完成:
1)把前一半排序
2)把后一半排序
3)把兩半歸并到一個(gè)新的有序數(shù)組,然后再拷貝回原數(shù)組,排序完成
用分支解決歸并排序
#include <iostream>
using namespace std;
void Merge(int a[],int s,int m,int e,int tmp[])
{//將數(shù)組a的局部a[s,m]和a[m+1,e]合并到tmp,并保證tmp有序,然后再拷貝回a[s,m]
//歸并操作時(shí)間復(fù)雜度: O(e-m+1)即O(n)
int pb = 0;
int p1 = s,p2 = m+1;
while(p1<=m && p2<=e){
if(a[p1] < a[p2])
//p1++是將值賦給之后,要指向下一個(gè)元素
tmp[pb++] = a[p1++];
else
tmp[pb++] = a[p2++];
}
//當(dāng)兩個(gè)數(shù)組比較完之后,可能其中一個(gè)數(shù)組元素比另一個(gè)多,再把多的賦給tmp[]
while(p1<=m)
tmp[pb++] = a[p1++];
while(p2<=e)
tmp[pb++] = a[p2++];
//最后再把tmp[]中元素復(fù)制給a[],tmp[]在這個(gè)過程中作中轉(zhuǎn)
//為何是e-s+1,因?yàn)閟,e不一定是開頭或者末尾,如果是的話可以i<e+1;
for(int i=0;i<e-s+1;++i)
a[s+i] = tmp[i];
}
//從s開始到e
void MergeSort(int a[],int s, int e,int tmp[])
{
if(s<e){
//從中間分開,m代表中間
int m = s +(e-s)/2; //或者int m = (s+e)/2;
//a[]數(shù)組前一半
MergeSort(a,s,m,tmp);
//a[]數(shù)組后一半
MergeSort(a,m+1,e,tmp);
Merge(a,s,m,e,tmp);
}
}
int a[10] = {13,27,19,2,8,12,2,8,30,89};
int b[10];
int main()
{
int size = sizeof(a)/sizeof(int);
//待排序的起始位置0到size-1,b是臨時(shí)存儲(chǔ)的數(shù)組,就是tmp[]
MergeSort(a,0,size-1,b);
for(int i=0;i<size;++i)
cout<<a[i]<<",";
cout<<endl;
return 0;
}
時(shí)間復(fù)雜度
