欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

归并排序--C语言

程序员文章站 2022-05-31 08:19:12
...

  今天写的是归并排序,归并排序的定义为:依次将每两个相邻的有序表合并成一个有序表的排序方法。最经常使用的归并方法是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号单元开始,导致边界条件控制的有问题。这个也提醒了我,以后写代码要具体情况具体分析,不能想当然。
  代码的道路还很长,算法的精通也不是靠一两日之功,经验的积累更是在不断犯错中才实现的。之前一直很浮躁,做事情坚持不了几天,导致现在一无所长。现在看明白了自己想要的是什么,就应该坚定自己的信念,朝着自己的目标走下去~加油!