随机产生0~50的10个数字并对其用归并算法排序
学习要点：
- 递归算法的理解和使用
- 归并算法的理解和使用
- 随机数的生成
算法介绍：
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
算法的思路
如何将2个有序数列合并？答案很简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
那将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
归并算法的原理
归并算法原理
平均时间复杂度：O(NlogN)
并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。
代码实现
#include <iostream>
#include <ctime>
#include <stdio.h>
using namespace std;
int compar (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int gbpx(int a[],int first,int last,int temp[]);
int hb(int a[],int first,int middle,int end,int temp[]);
int main(int argc, char *argv[])
{
srand(time(0));//如果要每次运行时产生的随机数不同，需要设置一个种子
int temp[11]={0},a[11]={0},i;
for(i=1;i<=10;i++)
{
a[i]=rand()%50;//产生一个0~50的随机数，并通过for循环赋值给数组a
}
gbpx(a,1,10,temp);//将所需参数传递给归并排序函数
for(i=0;i<10;i++)
{
cout<<a[i]<<" ";//利用for循环输出排序后的数组
}
return 0;
}
/*函数开始*/
int gbpx(int a[],int first,int last,int temp[])
{
int middle;
if(first<last)
{
middle=(first+last)/2;//将数组拆分
gbpx(a,first,middle,temp);//左边排序
gbpx(a,middle+1,last,temp);//右边排序
hb(a,first,middle,last,temp);//合并排序后的数组
}
}
/*合并的函数开始*/
int hb(int a[],int first,int middle,int end,int temp[])
{
int i=first,m=middle,j=middle+1,n=end,k=0,ii=0;
while(i<=m && j<=n)
{
if(a[i] <= a[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k] = a[j];
k++;
j++;
}
}
while(i<=m)
{
temp[k] = a[i];
k++;
i++;
}
while(j<=m)
{
temp[k] = a[j];
k++;
j++;
}
for(ii=0;ii<k;ii++)
{
a[first + ii] = temp[ii];
}
}
学习网址参考
十大编程算法助程序员走上高手之路 | 菜鸟教程
排序算法总结 | 菜鸟教程
一些心得
- 对于各种排序归并是种很好的的算法了，但学习排序算法只是为了锻炼思维，并不像高考是为了背下来日后使用，切记！
- 对于函数的声明和使用要注意，在学习过程中就出现下面的错误，引起报错
[Error]collect2: ld returned 1 exit status
声明为
int cfpx(int a[]);
实现为：
int cfpx(int a[],int first,int last,int temp[])
{
int middle;
if(first<last)
{
middle=(first+last)/2;
cfpx(a,first,middle,temp);
cfpx(a,middle+1,last,temp);
hb(a,first,middle,last,temp);
}
}
发表于 2020-11-17 20:43
