C语言带比较器的归并排序

朱雀 2021-03-26 14:33 424阅读 0赞

#include <stdio.h>
     #include <stdlib.h>
     
     typedef int DataType;
     
     //比较器
     int mycmp(const void * a, const void *b); 
     
     //int (*compar)(const void *, const void *) 函数指针
     void Sort(DataType * arr, int from, int to, int (*compar)(const void *, const void *));
     
     void merge(DataType *arr, int from, int mid, int to, int (*compar)(const void *, const void *));
     
     void printArray(DataType * arr, int n);
     
     int main()
     {
         DataType arr[10] = {
       2,3,10,12,6,1,18,14,65,12};
         printf("Befor sort:\n");
         printArray(arr,10);
         Sort(arr, 0, 9, mycmp);
         printf("After sort:\n");
         printArray(arr,10);
         return 0;
     }
     
     void Sort(DataType * arr, int from, int to, int (*compar)(const void *, const void *))
     {
         if(from == to)
             return;
         DataType mid = (from + to)/2;
         Sort(arr, from, mid, *compar);
         Sort(arr, mid+1, to, *compar);
         merge(arr, from, mid, to, *compar);
     
     }
     
     void merge(DataType * arr, int from, int mid, int to, int (*compar)(const void *, const void*))
     {
         int i = 0;
         DataType * first1 = arr + from;
         DataType * end1 = arr + mid + 1;
         DataType * first2 = arr + mid + 1;
         DataType * end2 = arr + to + 1;
         DataType * temp = (DataType *)malloc((to - from + 1)*sizeof(DataType));
         DataType * p = temp;
         while((first1 != end1) && (first2 != end2))
             *p++ = ((*compar)(first1, first2) ? *first1++ : *first2++); 
         if(first1 == end1)
         {
             while(first2 != end2)
                 *p++ = *first2++; 
         }
         else
         {
             while(first1 != end1)
                 *p++ = *first1++;
         }
         p = temp;
         for(int i = from; i <= to; i++)
             arr[i] = *p++;
         free(temp);
     }
     
     int mycmp(const void * a, const void *b)
     {
         const DataType * pa = (const DataType *)a;
         const DataType * pb = (const DataType *)b;
         if(*pa >= *pb)
             return 1;
         else 
             return 0;
     }
     
     void printArray(DataType * arr, int n)
     {
         for(int i = 0; i < n; i++)
             printf("%d ", arr[i]);
         printf("\n");
     }

C语言 带比较器的归并排序