【大话数据结构C语言】69 归并排序（递归和迭代实现）

浅浅的花香味﹌ 2022-10-15 04:45 217阅读 0赞

堆排序之所以效率比较高是利用了完全二叉树，但是堆排序的设计本身是比较复杂的

那就引出一个问题，有没有更简单的使用完全二叉树来排序的算法呢？

**这就引出了归并排序算法**

### **归并排序** ###

归并排序就是利用归并的思想实现的排序方法，原理是假设初始序列含有n个记录，则可以看出是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或者1的有序子序列；再两两归并。。。。如此反复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路规定排序

其排序的过程就是完全二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyODI4_size_16_color_FFFFFF_t_70][]

### 时间复杂度 ###

归并排序的时间复杂度也是nlogn,且这是归并排序中最好，最坏，平均的时间性能,因此归并排序是一种稳定的排序

其空间复杂度为n+logn

也就是说，归并排序是一种比较占用内存，但是效率高且稳定的算法

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyODI4_size_16_color_FFFFFF_t_70 1][]

### 递归实现： ###

#include <stdio.h>
    #define MAXSIZE 10
    
    // 实现归并，并把最后的结果存放到list1里
    void merging(int *list1, int list1_size, int *list2, int list2_size)
    {
        int i, j, k, m;
        int temp[MAXSIZE];
    
        i = j = k = 0;
    
        while( i < list1_size && j < list2_size )
        {
            if( list1[i] < list2[j] )
            {
                temp[k++] = list1[i++];
            }
            else
            {
                temp[k++] = list2[j++];
            }
        }
    
        while( i < list1_size )
        {
            temp[k++] = list1[i++];
        }
    
        while( j < list2_size )
        {
            temp[k++] = list2[j++];
        }
    
        for( m=0; m < (list1_size + list2_size); m++ )
        {
            list1[m] = temp[m];
        }
    }
    
    void MergeSort(int k[], int n)
    {
        if( n > 1)
        {
            int *list1 = k;
            int list1_size = n/2;
            int *list2 = k + n/2;
            int list2_size = n - list1_size;
    
            MergeSort(list1, list1_size);
            MergeSort(list2, list2_size);
    
            merging(list1, list1_size, list2, list2_size);
        }
    }
    
    int main()
    {
        int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    
        MergeSort(a, 10);
    
        printf("排序后的结果是：");
        for( i=0; i < 10; i++ )
        {
            printf("%d", a[i]);
        }
        printf("\n\n");
    
        return 0;
    }

### **非递归实现归并排序（迭代实现）** ###

递归本身是有限制的（时间和空间上的性能损耗），之前也说过，大多数递归都是可以改造为迭代

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 10
    
    void MergeSort(int k[], int n)
    {
        int i, next, left_min, left_max, right_min, right_max;
        int *temp = (int *)malloc(n * sizeof(int));
    
        for( i=1; i < n; i*=2 ) 
        {
            for( left_min=0; left_min < n-i; left_min = right_max )
            {
                right_min = left_max = left_min + i;
                right_max = left_max + i;
    
                if( right_max > n )
                {
                    right_max = n;
                }
    
                next = 0;
    
                while( left_min < left_max && right_min < right_max )
                {
                    if( k[left_min] < k[right_min] )
                    {
                        temp[next++] = k[left_min++];
                    }
                    else
                    {
                        temp[next++] = k[right_min++];
                    }
                }
    
                while( left_min < left_max )
                {
                    k[--right_min] = k[--left_max];
                }
    
                while( next > 0 )
                {
                    k[--right_min] = temp[--next];
                }
            }
        }
    }
    
    int main()
    {
        int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    
        MergeSort(a, 10);
    
        printf("排序后的结果是：");
        for( i=0; i < 10; i++ )
        {
            printf("%d", a[i]);
        }
        printf("\n\n");
    
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyODI4_size_16_color_FFFFFF_t_70]: /images/20221014/e87195a35b33451a8fc07ec7710e5ad2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyODI4_size_16_color_FFFFFF_t_70 1]: /images/20221014/d724710f603f4364b28368359a44b2c4.png