C语言分治法实现归并排序-6ren

C语言分治法实现归并排序

转载作者：qq735679552 更新时间：2022-09-28 22:32:09

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C语言分治法实现归并排序由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

本文实例为大家分享了C语言实现归并排序的具体代码，供大家参考，具体内容如下。

归并排序的基本思想:

将两个及其以上的有序表合并为一张有序表，把待排序序列通过分治法分为若干个有序子序列，然后每两个子序列合并为一个子序列，经过多次合并后整合为一张有序表.

排序过程如图:

C语言分治法实现归并排序

代码如下:

 
    ? 
   
         #include "stdio.h" 
        
         #define MAX 100 
        
         int 
         is1[MAX],is2[MAX]; 
         //原数组is1，临时空间数组is2 
        
         void 
         merge( 
         int 
         low, 
         int 
         mid, 
         int 
         high){ 
        
         int 
         i=low,j=mid+1,k=low; 
        
         while 
         (i<=mid&&j<=high) 
        
         if 
         (is1[i]<is1[j]) 
        
         is2[k++]=is1[i++]; 
        
         else 
        
         is2[k++]=is1[j++]; 
        
         while 
         (i<=mid) 
        
         is2[k++]=is1[i++]; 
        
         while 
         (j<=high) 
        
         is2[k++]=is1[j++]; 
        
         for 
         ( i = low; i <=high ; i++) { 
        
         is1[i]=is2[i]; 
        
         printf 
         ( 
         "%5d" 
         ,is1[i]); 
        
         } 
        
         printf 
         ( 
         "\n" 
         ); 
        
         } 
        
         void 
         mergeSort( 
         int 
         a,  
         int 
         b){ 
        
         if 
         (a<b){ 
        
         int 
         mid=(a+b)/2; 
        
         mergeSort(a,mid); 
        
         mergeSort(mid+1,b); 
        
         merge(a,mid,b); 
        
         } 
        
         } 
        
         void 
         main(){ 
        
         int 
         i,n; 
        
         printf 
         ( 
         "请输入元素个数：" 
         ); 
        
         scanf 
         ( 
         "%d" 
         ,&n); 
        
         printf 
         ( 
         "请依次输入每个元素：\n" 
         ); 
        
         for 
         ( i = 1; i <=n ; ++i) { 
        
         scanf 
         ( 
         "%d" 
         ,&is1[i]); 
        
         } 
        
         mergeSort(1,n); 
        
         printf 
         ( 
         "排序后的序列为：\n" 
         ); 
        
         for 
         ( i = 1; i <=n ; ++i) { 
        
         printf 
         ( 
         "%4d" 
         ,is1[i]); 
        
         } 
        
         }