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;
}
4、时间复杂度和空间复杂度
平均时间复杂度:O(nlogn)
空间复杂度:O(n)
稳定性:稳定
5、适用情况
1、处理大规模数据排序:其时间复杂度为O(nlogn),处理大规模数据时,能够在相对较短的时间内完成排序任务。
2、有稳定排序的需求时:归并排序是一个稳定的排序算法,当有相等元素进行排序时,相等元素的相对顺序不会改变。