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

归并排序算法

news 2024/11/2 14:11:44

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++];elsearr[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;
}