归并排序--C语言

红太狼 2022-03-18 06:26 169阅读 0赞

今天写的是归并排序，归并排序的定义为：依次将每两个相邻的有序表合并成一个有序表的排序方法。最经常使用的归并方法是2-路归并。假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到⎡n/2⎤个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。今天的算法代码就是按照2-路归并排序的思想写的。  
代码如下：

#include<stdio.h>
    #include<stdlib.h>
    
    /*
     * arr为待排序数组，归并的元素为arr[s...m]和arr[m+1...n]*/
    void merge(int arr[],int s,int m,int n)
    {
        
        int len = n - s + 1;//存放归并后的有序元素的数组长度
        int *arr1 = (int*)malloc(len * sizeof(int));
        int i = 0;
        int j = 0;
        int k = 0;
        for(i = s,j = m + 1,k = 0;i <= m && j <= n;k++)
        {
        
            if(arr[i] <= arr[j])
            {
        
                arr1[k] = arr[i];
                i++;
            }
            else{
        
                arr1[k] = arr[j];
                j++;
            }
        }
        if(i <= m)
        {
        
            for(;i <= m;i++)
            {
        
                arr1[k++] = arr[i];
            }
        }
        if(j <= n)
        {
        
            for(;j <= n;j++)
            {
        
                arr1[k++] = arr[j];
            }
        }
        for(i = 0;i < k;i++)
        {
        
            arr[i + s] = arr1[i];
        }
        free(arr1);
    }
    
    void mergeSort(int arr[],int len)
    {
        
        int m = 0;
        int i = 0;
        for(m = 1;m < len;m = m * 2)
        {
        
            for(i = m;i < len;i = i + 2 * m)
            {
        
                if(i + m < len)
                {
        
                    merge(arr,i - m,i - 1,i + m - 1);
                }
                else{
        
                    merge(arr,i - m,i - 1,len - 1);
                }
            }
        }
    }
    
    int main()
    {
        
        int i = 0;
        int arr[] = {
        49,38,65,97,76,13,27};
        for(i = 0;i < 7;i++)
        {
        
            printf("%d ",arr[i]);
        }
        printf("\n");
        mergeSort(arr,7);
        for(i = 0;i < 7;i++)
        {
        
            printf("%d ",arr[i]);
        }
        printf("\n");
        return 0;
    }

归并排序算法之前很少用到，之前读书的时候也没有写过完整的代码运行过，所以今天还是稍微费了一点时间才写好，主要是以往的排序算法，我都是从下标1开始的，0号单元没有使用。而今天则是从0号单元开始，导致边界条件控制的有问题。这个也提醒了我，以后写代码要具体情况具体分析，不能想当然。  
  代码的道路还很长，算法的精通也不是靠一两日之功，经验的积累更是在不断犯错中才实现的。之前一直很浮躁，做事情坚持不了几天，导致现在一无所长。现在看明白了自己想要的是什么，就应该坚定自己的信念，朝着自己的目标走下去～加油！