自下而上合并排序算法
归并排序算法
时间复杂度: O(nlogn)
稳定性: 稳定排序算法
算法
void Merge(short A[],int p,int q,int r)//合并
{
short *B=new short[r-p+1];
int s=p,t=q+1,k=0;
while ( (s<=q) && (t<=r) )
{
if(A[s]<=A[t])
B[k++]=A[s++];
else
B[k++]=A[t++];
}
if(s==q+1)
{
while(t<=r)
B[k++]=A[t++];
}
else
{
while(s<=q)
B[k++]=A[s++];
}
for(int i=0;i<k;i++)A[i+p]=B[i];
delete [] B;
}
void BottomUpSort(short a[],int n)//自下而上合并排序
{
int t=1,s,i;
while(t<n)
{
s=t;t=2*s;i=0;
while(t+i<=n)
{
Merge(a,i+1,i+s,i+t);
i=i+t;
}
if(i+s<n)
Merge(a,i+1,i+s,n);
}
}
void BottomUpSort(short A[],int low, int high)//递归
{
int mid;
if(low < high)
{
mid= (low+high) / 2; //分
BottomUpSort(A,low,mid);
BottomUpSort(A, mid+1,high);
Merge(A, low, mid, high); //合
}
}
归并排序算法复杂度分析
归并排序算法的精髓是分治法
分:将一个列表分为两个子列表,子列表继续分为两个子列表直至只含有两个元素或者无法再分
治:对最小子列表进行排序,然后再将两个子列表进行合并为一个有序的列表
归并排序的算法比较简单,比较次数小于快速排序的比较次数,但对空间的消耗较大。
归并排序算法测试
#include "stdafx.h"
#include <iostream>
#include <windows.h>
#include <stdlib.h>
#include <stdio.h>
#include <iomanip.h>
#include <time.h>
const int N=65535*2;
int main()
{
short A[N+1];
srand(time(NULL));
for(int i=1;i<=N;i++)A[i]=rand()%10000;
clock_t start, end;
printf("BottomUpSort 排序中:\n"); //进行排序
start = clock();
BottomUpSort(A,N);//迭代
// BottomUpSort(A,1,N);// 递归
end = clock();
printf("\n排序耗费时间= %d 毫秒\n",end-start);
printf("排列后数据:(每2048个)\n");
system("pause");
for(int j = 1; j <=N; j++) //输出排列结果
{
printf("%d\t",A[j]);
if(j%2048==0){printf("\n");;system("pause");printf("\n");}
}
return 0;
}