归并排序算法
[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;
}
补充：软件开发 , C++ ,
