归并排序-图文过程

文章目录

• 递归实现
• 非递归实现

一、什么是归并排序

归并排序是建立在归并操作上的一种有效，稳定的排序算法。该算法是采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

二、代码及过程

时间复杂度O（N*logN) 空间复杂度O(N）

**

递归实现

**

 void MergeSort(int* a, int n)//归并排序
 {
     int* tmp =(int*) malloc(sizeof(int) * n);//malloc一个同a数组一样的空间的数组
     if (tmp == NULL)
     {
         perror("malloc fail");
         return;
     }

     _MergeSort(a, 0,n-1,tmp );// 套用递归

     free(tmp);
     tmp = NULL;
 }

// 递归实现
 void _MergeSort(int* a, int begin, int end, int* tmp)
 {
     if (begin >= end)//到这里只有一个元素（即有序）时返回
         return;

     int mid = (begin + end) / 2;//取中
     //分区间[begin,mid],[mid+1,end]
     _MergeSort(a, begin, mid, tmp);//[begin,mid]进去
     _MergeSort(a, mid + 1, end, tmp);//[mid+1,end]进去

     //归并（最小情况两个元素到这，此时begin=mid,mid+1=end）
     int begin1 = begin;
     int end1 = mid;
     int begin2 = mid + 1;
     int end2 = end;
     int i = begin;
//归并
     while (begin1 <= end1 && begin2 <= end2)//取小的元素尾插到tmp
     {
         if (a[begin1] <= a[begin2])
         {
             tmp[i++] = a[begin1++];
         }
         else
         {
             tmp[i++] = a[begin2++];
         }
     }
     if (begin1 <= end1)//若出现一边未尾插完则到这往后尾插
     {
         tmp[i++] = a[begin1++];
     }

     if (begin2 <= end2)
     {
         tmp[i++] = a[begin2++];
     }
     //把tmp数组copy到原数组//这里是全部排序完才copy回原数组
     memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));

 }

非递归实现

 void MergeSortNonR(int* a, int n)
 {
     int* tmp = (int*)malloc(sizeof(int) * n);
     if (tmp == NULL)
     {
         perror("malloc fail");
         return;
     }
     int gap = 1;

     while (gap < n)
     {
        //gap个数据归并

         for (int j=0; j < n; j += 2 * gap)
         {

             int begin1 = j; int end1 = j + gap - 1;
             int begin2 = j + gap; int end2 = j + 2 * gap - 1;
             // 
             if (end1 > n)//第一组越界-只有一种情况-一个一个数都没有--n=0
             {
                 break;
             }
             if (begin2 > n)
//第二组全部越界-此时第一组已经归并完成并打印到a数组上了-直接break
             {
                 break;
             }
             if (end2 > n)//第二组部分越界-只需要把界限改为最后的元素即可
             {
                 end2 = n - 1;
             }

             int i = j;
             while (begin1 <= end1 && begin2 <= end2)//取小的元素尾插到tmp
             {
                 if (a[begin1] <= a[begin2])

                 {
                     tmp[i++] = a[begin1++];
                 }
                 else
                 {
                     tmp[i++] = a[begin2++];
                 }

             }
             if (begin1 <= end1)//若出现一边未尾插完则到这往后尾插
             {
                 tmp[i++] = a[begin1++];
             }

             if (begin2 <= end2)
             {
                 tmp[i++] = a[begin2++];
             }
             //把tmp数组copy到原数组
             memcpy(a + j, tmp + j, sizeof(int) * (end2 -j+ 1));

         }
         gap *= 2;
         printf("\n");
     }
     free(tmp);
     tmp = NULL;
 }

总结

归并排序相对简单，但也得掌喔好噢，你也快来学习一下吧！！！

如果以上内容对你有帮助的话，不妨给个小小的赞支持一下吧！！！