归并排序

归并排序   分治法  先分然后合并
网上很多都是  利用等大的数据空间    然后排序
即 时间复杂度  Onlog2n 空间复杂度  O(n)

我自己没事写了一个 大致思路相同 
区别是 我采用 元素的移动 没有采用等大的 数据空间
大概是  时间复杂度 Onlog2n  空间复杂度 O(1)

大家可以研究研究  ,欢迎吐槽  哈哈 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/**
归并排序 
Onlog2N O(1)
没有采用数组等大空间
author:lb
DATE:2019-08-09
*/
//打印数组
void printArr(int arr[],int len){
for(int i=0;i<len;i++){
printf("%i,",arr[i]);
}
printf("\n");
}
//声明
void mergeArr(int arr[],int start,int len);

//拆分 排序
void mergeSort(int arr[],int start,int len){
if(start <len){
int mid=(start+len)/2;

if((mid-start) >1){  //是否可分割
 mergeSort(arr,start,mid);
}

if((len-mid) >1){  //是否可:分割
mergeSort(arr,mid,len);
}

mergeArr(arr,start,len);
}

}

//最小范围内排序
void mergeArr(int arr[],int start,int len){
int mid=(start+len) /2;


int index=start;
int s1=start,e1=mid,s2=mid,e2=len;
int temp1,temp2,s3,s4;

//temp1 始终指向前分区当前比较的元素
//temp2 互换位置用.
//s3  始终指向 前分区 下一个待比较的元素
//s4  始终指向 将被覆盖的元素 容身之地 

temp1=arr[index];
s3=s4=mid;   //默认 前分区被覆盖的元素 从后分区第一个元素开始保存

printf("开始排序--start=%i,len=%i,s1=%i,e1=%i,s2=%i,e2=%i\n",start,len,s1,e1,s2,e2);

while(s1 <e1 || s2 < e2){
//printf("头元素temp1=%i,s1=%i,s2=%i,s3=%i,s4=%i\n",temp1,s1,s2,s3,s4);
//printArr(arr,len);

if(s1==e1){
arr[index++]=arr[s2++];
}else if(s2==e2){

for(int i=s4;i>s3 && i<s2;i-- ){
  arr[i]=arr[i-1];
}
arr[index]=temp1;
printArr(arr,len);
return;
}else{

 if(temp1 > arr[s2]){
 if(s1 < index){ //存在覆盖
  temp2=arr[index];  
  if(index >=s3){ //后退
    for(int i=s4;i>=s3 && i<s2;i-- ){
      arr[i]=arr[i-1];
    }
    s3++;
    s4++;
  }
  arr[index]=arr[s2];
  if(index <mid){
   arr[s4++]=temp2;
  }
  index++;
  s2++;
 }else{
  arr[index++]=arr[s2++];
 }
}else{
  if(s1 <index){//存在覆盖
   temp2=arr[index];
  
   int back=1; // 如果后退了就不前进了
   if(index >=s3){ //后退
     printf("后退s3=%i,s4=%i\n",s3,s4);
     for(int i=s4;i>=s3 && i<s2;i--){
      arr[i]=arr[i-1];
     }
     s3++;
     s4++;
     printf("后退后s3=%i,s4=%i\n",s3,s4);
     back=0;
   }

   arr[index]=temp1;
   if(index < mid){
     arr[s4++]=temp2;
   }
   temp1=arr[s3++];
  
   if(back){ //前进
   printf("前进s3=%i,s4=%i\n",s3,s4);   
   for(int i=s3;i<s4;i++ ){
      arr[i-1]=arr[i];
   }
   s4--;
   s3--;
   printf("前进后s3=%i,s4=%i\n",s3,s4);
   }
   index++;
   s1++;
  }else{
   arr[index++] =temp1;
   temp1=arr[++s1];
  }
}
}

printArr(arr,len);
printf("\n");
}

}
//测试
int main(){
//int arr[]={18,25,30,40,45,1,10,41,42,60};
//int arr[]={18,25,60,70,80,1,10,41,42,45};
//int arr[]={46,17, 39, 23, 28, 55, 18, 46,66,45,85,61,1,5,2,9,3,12,15,6,14,16,34,64,85,29,100,11,22,44,33};

//17,18,23,28,39,46,55,1,5,45,46,61,61,85,19,29,3,234,221,234,22

int arr[]={17,18,23,28,39,46,55,1,5,45,46,61,61,85,19,29,3,234,221,234,22};
int len=21;
printArr(arr,len);
printf("排序后------\n");
mergeSort(arr,0,len);
printArr(arr,len);

}