排序算法之归并排序

归并排序是个稳定的内部排序算法,时间复杂度为0(nlog2n),空间复杂度为O(n),一般来说当n的值很大,就可以考虑选择这种排序算法,和直接插入排序算法结合使用.

下面是两路归并算法:

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

void merge(int *data, int low,int mid,int high){
 int i ,p ,k = 0;
 int *temp;
 temp = (int *)malloc((high - low + 1)*sizeof(int));
 if(!temp){
   printf("内存分配失败!!!");
   return;
 }
 for( i = low,p = mid; i < mid && p <= high;){
     //printf("执行000000!!!");
    if(data[i] < data[p]){
      temp[k++] = data[i++];
    }else{
       temp[k++] = data[p++];
    }
 }
//printf("执行0!!!");
while(i < mid) temp[k++] = data[i++];
while(p <= high)temp[k++] = data[p++];
//printf("执行1!!!");
i = low; p = 0;
while(p < k){
 data[i++] = temp[p++];
}
 free(temp);
// printf("执行一!!!");
 
}

void  mergeSort(int data[] ,int s,int t){
   int m;
   if(s < t){
       m =  (s + t)/2;
       mergeSort(data,s,m);
       mergeSort(data,m+1,t);
       merge(data,s,m+1,t);

   }

   // printf("执行000000!!!");
}

int main(int argc,char *argv[]){

   int data[] = {48,37,64,96,75,12,26,48,54,3};
  // int num = sizeof(data)/sizeof(data[0]);
    //printf("%d",num);
   mergeSort(data,0,10);
   for(int i = 0; i < 10; i++){
     printf("%d\n",data[i]);
   }
   return 0;
}