• 【C语言】归并排序和计次排序

    一、归并排序

            归并排序要额外多开一个数组用于存放归并后的数据，然后再把排序好的数据放回原数组。

            归并排序使用递归的写法，大致分位两个步骤，一个是分解，一个是归并。而归并的数据必须是有序的才行，那么如何保证其最开始是有序的呢？

            其实这里进入递归到了最底层，其数据被分为单一个数为一个区间的时候，这里就认为其是有序的。

            分解会把数据分解为两个区间，然后做比较，如果是升序的话，一个个比较，把较小的放到临时数组。

            此时此段区间就变为有序了，返回上一层这段区间就又可以用来被归并。

    简单讲解归并流程，假设这里数组已经被分解为了两个有序的区间：

            这里就要依次进行比较然后把较小的数据放到临时数组。把数据放下去以后，i 往前走一步，然后再进行比较。

             

            这里2<4，把2放到下面的数组，然后 j 往前走一位。

            依次走到最后数组数据就排序好了，但是这里要注意一个情况，这种比较的方法固定要有一个区间先走完，这里左区间先走完了，但是右区间还剩一个数，也没办法比较了。

            所以为了防止这个情况，在归并结束后，如果哪个区间还有数据，就直接加到数组后面就可以，因为排序的数组是有序的，所以直接加到数组后面不会出错。

     

             

     代码：

    1. void _MergeSort(int* a, int begin, int end, int* temp)
    2. {
    3.  
    4.     if (begin >= end) //至少要有两个区间
    5.         return;
    6.  
    7.     int mid = (begin + end) / 2;
    8.  
    9.     //分治  [beging,mid]  [mid+1,end]
    10.     _MergeSort(a ,begin,mid,temp);
    11.     _MergeSort(a, mid+1, end, temp);
    12.  
    13.     int begin1 = begin，end1 = mid;
    14.     int begin2 = mid + 1，end2 = end;
    15.  
    16.     int i = begin1;    //这里注意是beging1
    17.  
    18.     //归并 把小的放到temp数组中去
    19.     while (begin1 <= end1 && begin2 <= end2) {
    20.  
    21.         if (a[begin1]<a[begin2]) {
    22.  
    23.             temp[i++] = a[begin1++];
    24.         }
    25.         else {
    26.             temp[i++] = a[begin2++];
    27.         }
    28.  
    29.     }
    30.  
    31.     //如果一个数组走完了，还剩有数据，全部放到数组后面去
    32.     while (begin1<=end1) {
    33.         temp[i++] = a[begin1++];
    34.     }
    35.  
    36.     while (begin2<=end2) {
    37.         temp[i++] = a[begin2++];
    38.     }
    39.  
    40.     //把数据拷贝回原数组 
    41.     memcpy(a + begin, temp + begin,(end-begin+1)*sizeof(int));
    42. } 
    43.  
    44.  
    45. //递归实现
    46. void MergeSort(int *a,int n)
    47. {
    48.     int* temp = (int*)calloc(n, sizeof(int));
    49.     
    50.     if (temp==NULL){
    51.         perror("tmp初始化失败\n");
    52.         return;
    53.     }
    54.  
    55.     _MergeSort(a, 0, n-1, temp);
    56.     free(temp);
    57. }

    测试：

            归并排序的时间复杂度是典型的：O(N*logN )；

            

    二、归并排序非递归实现

            归并的非递归直接可以在数组中处理。

            其思路是把数组中的数进行分组，设gap个数为一组，每组数又有两个区间，这两个区间做比较，归并成一个有序的区间。有序的区间又可以分组，然后归并。

           

            gap=1，每单个一个数分为一组，归并后刚好变为gap=2，两个数的组。依次归并，最后整个数组就有序了。

    1. //归并排序的非递归     
    2. void MergeSortNonR(int* a, int n)
    3. {
    4.  
    5.     int* temp = (int*)calloc(n, sizeof(int));
    6.     if (temp == NULL) {
    7.         perror("tmp初始化失败\n");
    8.         return;
    9.     }
    10.  
    11.     int gap = 1;
    12.  
    13.     while (gap < n) {
    14.  
    15.         for (int i = 0; i < n; i += 2*gap) { //注意这里是一次跳两组
    16.  
    17.             //[i][i+gap-1] [i+gap][i+2*gap-1]
    18.             int begin1 = i, end1 = i + gap - 1;
    19.             int begin2 = i + gap, end2 = i + 2 * gap - 1;
    20.  
    21.  
    22.             int j = begin1;
    23.             while (begin1 <= end1 && begin2 <= end2)
    24.             {
    25.                 if (a[begin1] < a[begin2]) {
    26.  
    27.                     temp[j++] = a[begin1++];
    28.                 }
    29.                 else {
    30.                     temp[j++] = a[begin2++];
    31.                 }
    32.             }
    33.  
    34.             while (begin1 <= end1)
    35.             {
    36.                 temp[j++] = a[begin1++];
    37.             }
    38.  
    39.             while (begin2 <= end2) {
    40.  
    41.                 temp[j++] = a[begin2++];
    42.  
    43.             }
    44.  
    45.         }
    46.  
    47.         //这里每个数据都归并了所以可以全部拷贝回去。
    48.         memcpy(a, temp, sizeof(int) * n);
    49.  
    50.         gap *= 2;
    51.  
    52.     }
    53.     
    54.     free(temp);
    55. }


            思路比较好理解，但是要注意的是边界的控制。如果数组的长度不为2的次方倍数，那么不控制边界会造成越界。

            比如一个数组长度等于9，调试的时候这里打印一下区间。

             这里就会发现，有点地方的区间大于了数组的长度（数组下标是0-8，9也越界了）。除了begin1不会越界以外，其他的边界都会越界。

             所以这里为了防止边界越界，要控制一下边界。

    1.  
    2. //归并排序的非递归     
    3. void MergeSortNonR(int* a, int n)
    4. {
    5.  
    6.     int* temp = (int*)calloc(n, sizeof(int));
    7.     if (temp == NULL) {
    8.         perror("tmp初始化失败\n");
    9.         return;
    10.     }
    11.  
    12.     int gap = 1;
    13.  
    14.     while (gap < n) {
    15.  
    16.         printf("gap=%d-->",gap);
    17.         for (int i = 0; i < n; i += 2*gap) { //注意这里是一次跳两组
    18.  
    19.             //[i][i+gap-1] [i+gap][i+2*gap-1]
    20.             int begin1 = i, end1 = i + gap - 1;
    21.             int begin2 = i + gap, end2 = i + 2 * gap - 1;
    22.  
    23.             //修正边界
    24.             if (end1 >= n) { //end1越界
    25.                 
    26.                 end1 = n - 1;
    27.                 begin2 = n;
    28.                 end2 = n - 1;
    29.             }
    30.             else if (begin2 >= n) { //begin2越界
    31.                 
    32.                 begin2 = n;
    33.                 end2 = n - 1;
    34.             }
    35.             else if (end2 >= n) { //end2越界
    36.                 
    37.                 end2 = n - 1;
    38.             }
    39.  
    40.             //打印边界:
    41.             printf("--[%d][%d],[%d][%d]",begin1,end1,begin2,end2);
    42.             int j = begin1;
    43.             while (begin1 <= end1 && begin2 <= end2)
    44.             {
    45.                 if (a[begin1] < a[begin2]) {
    46.  
    47.                     temp[j++] = a[begin1++];
    48.                 }
    49.                 else {
    50.                     temp[j++] = a[begin2++];
    51.                 }
    52.             }
    53.  
    54.             while (begin1 <= end1)
    55.             {
    56.                 temp[j++] = a[begin1++];
    57.             }
    58.  
    59.             while (begin2 <= end2) {
    60.  
    61.                 temp[j++] = a[begin2++];
    62.  
    63.             }
    64.  
    65.         }
    66.         //这里每个数据都归并了所以可以全部拷贝回去。
    67.         memcpy(a, temp, sizeof(int) * n);
    68.         printf("\n");
    69.         gap *= 2;
    70.  
    71.     }
    72.     
    73.     free(temp);
    74. }

    PS：越界后设 begin2 < end2 ，这样越界的右区间就不会进入归并的步骤了。

    测试： 

            

            

            还有一种思路，如果区间发生数组越界，那么就不进行归并了。

    1.  
    2. //归并排序的非递归    第二个控制边界的办法   
    3. void MergeSortNonR_Test(int* a, int n)
    4. {
    5.  
    6.     int* temp = (int*)calloc(n, sizeof(int));
    7.     if (temp == NULL) {
    8.         perror("tmp初始化失败\n");
    9.         return;
    10.     }
    11.  
    12.     int gap = 1;
    13.  
    14.     while (gap < n) {
    15.  
    16.  
    17.         printf("gap=%d-->", gap);
    18.         for (int i = 0; i < n; i += 2 * gap) { //注意这里是一次跳两组
    19.  
    20.             //[i][i+gap-1] [i+gap][i+2*gap-1]
    21.             int begin1 = i, end1 = i + gap - 1;
    22.             int begin2 = i + gap, end2 = i + 2 * gap - 1;
    23.  
    24.  
    25.             //如果end1、begin2越界就不归了
    26.             if (end1 >= n || begin2 >= n) {
    27.                 
    28.                 break;
    29.             }
    30.             else if (end2 >= n) { //end2越界还是要归并
    31.                 
    32.                 end2 = n - 1;
    33.             }
    34.            
    35.  
    36.             int m = end2 - begin1 + 1;
    37.  
    38.             //打印边界:
    39.             printf("--[%d][%d],[%d][%d]", begin1, end1, begin2, end2);
    40.  
    41.  
    42.             int j = begin1;
    43.             while (begin1 <= end1 && begin2 <= end2)
    44.             {
    45.                 if (a[begin1] < a[begin2]) {
    46.  
    47.                     temp[j++] = a[begin1++];
    48.                 }
    49.                 else {
    50.                     temp[j++] = a[begin2++];
    51.                 }
    52.             }
    53.  
    54.             while (begin1 <= end1)
    55.             {
    56.                 temp[j++] = a[begin1++];
    57.             }
    58.  
    59.             while (begin2 <= end2) {
    60.  
    61.                 temp[j++] = a[begin2++];
    62.  
    63.             }
    64.             //注意如果不归并了，这里不能把数据拷贝回去，不然会把未初始化的值拷贝回去,所以只能拷贝已经归并了的数据。
    65.             memcpy(a + i, temp + i, sizeof(int) * m);
    66.         }
    67.  
    68.  
    69.         printf("\n");
    70.         gap *= 2;
    71.  
    72.     }
    73.  
    74.     free(temp);
    75. }

    PS：如果是区间越界就跳过归并的话，这里要注意就不能把全部的数据都拷贝回原来的数组，因为没发生归并，这里临时数组里面是未初始化的值，拷贝回去会造成覆盖。所以这里要注意，这里拷贝的话只能拷贝已经归并了的数据。

    三、计次排序

            计次排序也要额外申请一个数组，其数组大小是原数组最大元素和最小元素的差值。其存的数据是原数组里面数据出现的次数。

            然后按照出现的次数把数据写回原来的数组。此排序是个非比较排序。

            

            

      代码：

    1. //计次循环
    2. void CountSort(int *a,int n)
    3. {
    4.     //选出最大最小的数，计算差值
    5.     int max=a[0], min=a[0];
    6.  
    7.     for (int i = 0; i < n;i++) {
    8.         if (a[i]>max) {
    9.             max = a[i];
    10.         }
    11.         if (a[i]<min) {
    12.             min = a[i];
    13.         }
    14.     }
    15.  
    16.     int rang = max - min+1;
    17.  
    18.     int* count = (int*)calloc(rang,sizeof(int));
    19.     if (count==NULL) {
    20.         perror("count为NULL");
    21.         exit(-1);
    22.     }
    23.  
    24.     for (int i = 0; i < n;i++) {
    25.            
    26.         //记录出现数据的次数
    27.         count[a[i] - min]++;
    28.     }
    29.  
    30.     //放回原数组
    31.     int k = 0;
    32.     for (int j = 0; j < rang;j++) {
    33.  
    34.         while (count[j]--) {
    35.             a[k++] = j + min;
    36.         }
    37.  
    38.     }
    39.  
    40.  
    41.     free(count);
    42. }

    测试：

           

    局限性：

            1.浮点数、字符串不能排序。

            2.数据范围大，空间复杂度会很高。

            此排序的性质就决定了它只能排序范围比较小，重复度较高的数据。如果数据范围交到，其时间和空间的消耗都比较多。

    时间复杂度： O( max(rang,N) )        

    空间复杂度： O(rang)        //最小值和最大值的差值越大约消耗空间

  • 相关阅读:
    【力扣10天SQL入门】Day2
    96. 不同的二叉搜索树
    【ESP 保姆级教程】疯狂Node.js服务器篇 ——钉钉/微信/飞书报警从Arduino移植到NodeJs服务器实现
    【论文阅读】MAG：一种用于航天器遥测数据中有效异常检测的新方法
    实战：大数据Flink CDC同步Mysql数据到ElasticSearch
    力扣 寻找旋转排序数组中的最小值 二分
    幸福消费成酒店投资趋势红利，荟语酒店凭何打造品牌核心优势
    【React Hooks&Redux--学习小结】
    JVM执行流程
    qt 使用qt_material库打包报错 ImportError: cannot import name ‘uic‘ from ‘PyQt5‘
  • 原文地址：https://blog.csdn.net/weixin_45423515/article/details/125627853