ordering3.txt

自底向上排序：思想: 将数组的个部分,两两有序数组进行合并 算法平均时间复杂度: O(nlogn)

bool bottomupsort(int *array,int n)
{
int length=1,temp_length,i;           //temp_length表示单个合并数组的长度
while(length<n)
{
  temp_length=length;     //length表示合并后数组的长度 
  length=2*temp_length; 
  i=0;        //i用于记录合并数组的起始位置
  while(i+length-1<=n-1)           
  {
   merge(array,i,i+temp_length,i+length-1);  //合并i~i+temp_length-1 和 i+temp_length~i+length-1 段
   i=i+length;          //取下一个合并段的起始位置
  }
  if(i+temp_length<n-1)
   merge(array,i,i+temp_length,n-1);         //对尾部剩余段合并
}
return true;
}
bool merge(int *array,int start1,int start2,int n)  //合并两个有序数组
{
int temp_n=n-start1+1,       //两合并数组的长度和
  *temp_array,        
  n1=start2-1,        //第一个有序数组的末端位置
  temp_start1=start1;       //记录start1的初始位置
temp_array=(int *)malloc(sizeof(int)*temp_n);   //申请长度为temp_n的整形空间,用于临时存储合并后的数组
    
for(int i=0;start1<=n1&&start2<=n;i++)          //对两个有序数组进行合并,存储于temp_array
{
  if(array[start1]<=array[start2])
  {
   temp_array[i]=array[start1];
   start1++;
  }
  else
  {
   temp_array[i]=array[start2];
   start2++;
  }
}
if(start1<=n1)         
{
  while(start1<=n1)
  {
   temp_array[i++]=array[start1];
   start1++;
  }
}
else
{
  while(start2<=n)
  {
   temp_array[i++]=array[start2];
   start2++;
  }
}
for(i=0,start1=temp_start1;i<temp_n;start1++,i++)      //将合并后的有序数组,复制到array数组中
{
  array[start1]=temp_array[i];
}
free(temp_array);
return true;
}