2、段的元素都行一个自然地有序序列，然后利用分治策略将每小段的元素进行合并，合并后的数组元素依然为一个有序序列。例：n=10随机序列为：5142308967，正确输出为：0123456789，它的自然有序分段的起始下标值为：01358。【实验原理】原理：对于一个给定的数组a，通常会有长度大于1的有序子序列，我们称之为自然有序子序列。自然归并排序是找出给定数组中的自然子序列，将其开始的下标位置保存起来，然后对两个子序列之间进行插入排序形成一个大的有序子序列，直到整个数组排序完成。思路：首先定义一个全局变量n，控制数组的长度。在给定
3、数组长度的前提，考虑数组子序列数最遭的情况就是整个数组对我们要求的序列刚好成一个反序列，即子序列的个数就是数组元素的个数。所以定义两个长度为n的数组a、b，一个保存数组元素啊a[i]，另一个保存自然子序列的起始下标值b[i]。得到起始下标后我们的排序循环应该为：b[i]≤j≤b[i+1]-1，其中当b[i]为最后一个的子序列的起始下标是，我们的循环应给为：b[i]≤j≤n。每次循环都将相当前的子序列个数进行分治，知道形成两个相对时才进行排序。方法：利用函数的相互调用和函数的递归调用实现程序的最终实现，一个主函数，三个子函数。
4、在主函数中只是单独的调用了将数组进行子序列划分的子函数zgb，然后以zgb为入口进行分治策略函数zgb1的调用，再在zgb1中调用zgb1函数本身和调用进行排序的函数zgb2。例：有数组a={4,8,3,7,1,5,6,2,0,9},则自然有序子序列有{4,8}，{3,7}，{1,5,6}，{2}和{0,9}。用一次对数组的扫描就可以找出这些子序列的起始下标位置为{0,2,4,7,8,}。对上面子序列进行一次归并排序后得到的子序列为{3,4,7,8}，{1,5,6}，{0,2,9}，排序后的下标起始位置为{0，4，7}。如此
5、的重复上面的排序动作，直到最后整个数组排序完成，即下标起始位置的值只剩下0号位置后退出。【源程序代码】#include"stdio.h"//输入输出的库函数#include"stdlib.h"//自然生成数据的库函数intn;//全局变量，数组的长度//函数的定义voidzgb(int*p);//自然分组的规划voidzgb1(intx,inty,int*q,int*p,intm);//递归实现的分治策略voidzgb2(intx,inty,intz,int*p);//排序函数voidmain()//主函数{inti,m;c
6、harch=13;//变量的定义while(1)//主菜单选择的循环{if(ch==13);//判断控制换行system("cls");//清屏printf("------------请选择：--------------1、运行程序。0、退出程序。");//主菜单scanf("%d",&m);//接受菜单选择值system("cls");//清屏if(!m)//判断程序是否执行。exit(0);//如果m的值非1，则执行退出printf("请输入数列的长度n。");//提示语句scanf("%d",&n);/
7、/从键盘输入一个值给n，规定数组的长度int*a=newint[n];//定义原数据数组printf("随机数列如下：");for(i=0;i8、最终的回车符，进入主菜单的下次循环}}voidzgb(int*p)//自然分组函数{inti,m;int*b=newint[n];//定义保存自然分组的起始下标值的数组m=0;b[0]=0;for(i=1;ip[i+1])//判断取得起始下标的值b[m+=
