当前位置：首页 > article >正文

归并排序算法

article 2025/1/10 21:58:41

1、基本思想

归并排序是建立在归并操作上的一种有效的排序算法，它采用分治法的策略。其基本思想是将一个待排序的数组分成两个或多个子数组，先对每个子数组进行排序，然后再将已排序的子数组合并成一个最终的排序数组。

对于两个有序的数组，很容易做到合并之后仍然有序。归并排序就是利用这一点，将待排序数组分成两个有序数组（如何保证分成的两个数组都有序：不停拆分，直到每个数组中只剩一个数，那么一定有序。）。待得到有序数组后，往回进行不停的合并操作。

2、算法步骤

2.1、算法步骤描述：

1、分解：将待排序的数组不断地拆分成左右两个子数组，直到每个子数组只包含一个元素为止。这一步是通过不断地计算数组的中间位置来实现的，例如对于数组 arr，中间位置 mid = (left + right) / 2（这里假设 left 是数组起始索引，right 是数组结束索引），从而将数组 arr 拆分成 arr[left...mid] 和 arr[mid + 1...right] 两个子数组。

2、排序与合并：对拆分后的子数组递归地调用归并排序算法，使其各自有序。然后将两个已经有序的子数组合并成一个更大的有序数组。合并操作是通过比较两个子数组的首元素，将较小的元素依次放入一个临时数组中，直到其中一个子数组的元素全部放入临时数组，再将另一个子数组剩余的元素全部放入临时数组，最后将临时数组中的元素复制回原数组对应的位置。

2.2、归并排序算法过程演示图：

2.3、归并排序算法动态演示图：

归并排序

动态演示图来源网站URL：https://visualgo.net

3、代码实现

c语言代码实现如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define N 10
void add(int arr[], int *left, int leftlen, int *right, int rightlen)
{
    int i = 0, j = 0, k = 0;//分别代表左数组下标，右数组下标，合并后数组下标
    while(i < leftlen && j < rightlen)//两个子数组都没合并完
    {
        if(left[i] <= right[j])//每次将两子数组中最小值填入
            arr[k++] = left[i++];
        else
            arr[k++] = right[j++];
    }
    //两个子数组可能不会同时完成填入
    //当左子数组没有完成
    while(i < leftlen)
    {
        arr[k++] = left[i++];
    }
    //当右子数组没有完成
    while(j < rightlen)
    {
        arr[k++] = right[j++];
    }
}
void sort(int arr[], int len)
{
    //设定递归终止条件，拆分到数组长度为一时，一定有序
    if(1 == len)
        return;
    int i;
    int mid = len/2;//确定中间位置

    int *left = (int *)malloc(mid * sizeof(int));//分配左数组空间
    int *right = (int *)malloc((len-mid) * sizeof(int));//分配右数组空间

   for(i = 0; i < mid ; i++)//存值到左数组中
   {
       left[i] = arr[i];
   }
   for(i = 0; i < len - mid; i++)//存值到右数组中
   {
       right[i] = arr[mid + i];
   }

   sort(left,mid);//对左右数组再进行拆分
   sort(right,len - mid);

   add(arr,left,mid,right,len - mid);//合并有序数组

   free(left);//回收空间
   free(right);
}
int main(int argc, char *argv[])
{
    srand(time(NULL));
    int a[N];
    int i;

    puts("排序前数组为：");
    for(i = 0; i < N; i++)
    {
        a[i] = rand()%100;//为数组随机赋值
        printf("%d ",a[i]);//输出排序之前数组值
    }
    puts("");

    sort(a,N);//排序

    puts("排序后的数组为：");
    for(i = 0; i < N; i++)
    {
        printf("%d ",a[i]);//输出排序之后的数组值
    }
    puts("");

    return 0;
}