[cpp] view plaincopyprint?
//歸並排序
//歸並排序算法是一種O(nlogn)的算法。它的最差，平均，最好時間都是O(nlogn)。
//但是它需要額外的存儲空間，這在某些內存緊張的機器上會受到限制。
#include <iostream>
#include<stdio.h>
using namespace std;
int a[10]={23,443,534,12,312,3,14,32,34,23};
void merge(int fir,int end,int mid)
{//合並
int tempArr[100];
int fir1=fir,fir2 = mid+1;
for(int i=fir;i<=end;i++)
{
if(fir1>mid)//前半段掃描完畢,直接將後半截賦值
tempArr[i] = a[fir2++];
else if(fir2>end)//後半段掃描完畢,直接將前半截賦值
tempArr[i] = a[fir1++];
//兩端如果都沒掃描完畢的話，就選擇較小的值插在臨時數組後面
else if(a[fir1]>a[fir2])
tempArr[i]=a[fir2++];
else
tempArr[i] = a[fir1++];
}
//將排序號的臨時數據拷貝到原數組中，返回
for(int i=fir;i<=end;i++)
{
a[i] = tempArr[i];
}
}
void mergeSort(int fir,int end)
{
if(fir==end)return;//當元素只有一個時
int mid = (fir+end)/2;
mergeSort(fir,mid);//對左半段遞歸排序
mergeSort(mid+1,end);//對右半段遞歸排序
merge(fir,end,mid);//合並
}
int main()
{
mergeSort(0,9);
for(int i=0;i<=9;i++)
{
printf("%d\t",a[i]);
}
//cout << "Hello world!" << endl;
return 0;
}
//歸並排序
//歸並排序算法是一種O(nlogn)的算法。它的最差，平均，最好時間都是O(nlogn)。
//但是它需要額外的存儲空間，這在某些內存緊張的機器上會受到限制。
#include <iostream>
#include<stdio.h>
using namespace std;
int a[10]={23,443,534,12,312,3,14,32,34,23};
void merge(int fir,int end,int mid)
{//合並
int tempArr[100];
int fir1=fir,fir2 = mid+1;
for(int i=fir;i<=end;i++)
{
if(fir1>mid)//前半段掃描完畢,直接將後半截賦值
tempArr[i] = a[fir2++];
else if(fir2>end)//後半段掃描完畢,直接將前半截賦值
tempArr[i] = a[fir1++];
//兩端如果都沒掃描完畢的話，就選擇較小的值插在臨時數組後面
else if(a[fir1]>a[fir2])
tempArr[i]=a[fir2++];
else
tempArr[i] = a[fir1++];
}
//將排序號的臨時數據拷貝到原數組中，返回
for(int i=fir;i<=end;i++)
{
a[i] = tempArr[i];
}
}
void mergeSort(int fir,int end)
{
if(fir==end)return;//當元素只有一個時
int mid = (fir+end)/2;
mergeSort(fir,mid);//對左半段遞歸排序
mergeSort(mid+1,end);//對右半段遞歸排序
merge(fir,end,mid);//合並
}
int main()
{
mergeSort(0,9);
for(int i=0;i<=9;i++)
{
printf("%d\t",a[i]);
}
//cout << "Hello world!" << endl;
return 0;
}
