1.算法介绍
归并算法是一种由冯·诺伊曼发明的分治算法，相较于普通排序算法时间复杂度较低，运行效率高。通常情况下，归并算法的时间复杂度为 O(nlogn)。
2.算法思想以及大致步骤
归并算法主要运用到了分治以及归并的思想，主要步骤如下：首先将一个无序数组分为n个有序的单个数组，然后将两个有序的单个数组合并为一个有序的序列，排序过程需要比较两个元素的大小，并按顺序填入心得数组中，不断重复，直到最后得到完全排序后的数组。
3.算法详细步骤以及代码演示
step1:
假设我们有以下数组[1,5,3,7,4,9,2,8,6,10]，第一步，使用递归算法将该数组不断地由数组中间一分为二，直到得到只有单个元素的数组[1],[5],[3],[7],[4],[9],[2],[8],[6],[10]，要注意，理解归并算法的核心就是：在此时，所有单个元素的数组都是有序的。递归分解算法如下：
void mergesoft(int arr[],int left,int right){
if (right-left<=1)//判断是否为单个元素数组
{
return 0 ;
}
int mid = (left+right)/2;//将数组一分为二
mergesoft(arr,left,mid);//对数组左半部分进行递归分解
mergesoft(arr,mid,right);//对数组右半部分进行递归分解
merge(arr,left,mid,right);//归并排序函数
}step2:
开始进行归并排序，将两个单个有序数组进行按照数值大小进行排序，按照从小到大的顺序放入一个新数组中，以此类推，我们以归并到两个有序数组后为例：此时经过前面的归并排序，我们可以得到两个有序数组a[1,3,6,8,10]，b[2,4,5,7,9]，下一步需要将两个数组合并为一个有序数组。首先，我们先创建一个新数组temp，用于临时存放排好序的新数组的元素，现在就可以对两个数组进行排序了，我们定义指向a数组最左边元素的指针为left，指向b数组最左边元素的指针为mid，最右边元素的指针为right，指向临时数组的指针为index。比较left和mid指针所指向的元素，此时left指针指向的元素为1，mid指针指向的元素为2，left指向的元素较小，将a[left]赋予temp[index]，注意，由于将left指向的元素赋予给了index，所以我们需要将left和index指针向右移动一位才能进行继续比较下一个元素，否则新的元素无法存放入新数组中。现在left指针指向3，mid指针依然指向2，mid指向的元素小于left指向的元素，所以将b[mid]赋予temp[index]，注意，赋值后，right和index指针同样需要向右移动一位。以此类推，直到所有的元素按顺序存放入临时数组temp中，排序完成，但是我们的任务还没有完成，我们需要将临时数组的值赋予我们需要排序的数组中，并将临时数组进行释放，避免占用过多内存，影响代码的性能。归并排序代码如下：
void merge(int arr[],int left,int mid,int right){//left,right,mid分别为数组的左右边界和中间元素
int i =left;
int j =mid;
int*temp = (int*)malloc((right-left)*sizeof(int));//定义一个临时数组
int index = 0;//将临时数组的索引指向0
while (i<mid && j <right)//判断指针是否越过边界
{
if (arr[i]<arr[j])//如果左边数组的元素小于右边
{
temp[index]=arr[i];//将左边数组元素赋予临时数组
i++;//指针右移一位
}else{
temp[index]= arr[j];//将右边数组元素赋予临时数组
j++;//指针右移一位
}
index++;//临时数组指针同时右移一位
}
while (i<mid)//将排序完剩余的元素全部写入临时数组中
{
temp[index]=arr[i];
index++;
i++;
}
while (j<right)
{
temp[index]=arr[j];
index++;
j++;
}
for ( int i = 0; i < index; i++)//将临时数组中的所以元素写入原来数组中
{
arr[left+i] = temp[i];
}
free(temp);//释放内存
}完成归并排序
4.完整代码演示：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void merge(int arr[],int left,int mid,int right){
int i =left;
int j =mid;
int*temp = (int*)malloc((right-left)*sizeof(int));
int index = 0;
while (i<mid && j <right)
{
if (arr[i]<arr[j])
{
temp[index]=arr[i];
i++;
}else{
temp[index]= arr[j];
j++;
}
index++;
}
while (i<mid)
{
temp[index]=arr[i];
index++;
i++;
}
while (j<right)
{
temp[index]=arr[j];
index++;
j++;
}
for ( int i = 0; i < index; i++)
{
arr[left+i] = temp[i];
}
free(temp);
}
void mergesoft(int arr[],int left,int right){
if (right-left<=1)
{
return 0 ;
}
int mid = (left+right)/2;
mergesoft(arr,left,mid);
mergesoft(arr,mid,right);
merge(arr,left,mid,right);
}
void printfarray(int *arr,int size){
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main(){
clock_t start, end;
double cpu_time_used;
start = clock();
srand((unsigned int)time(NULL));
int array5[5];
int array10[10];
int array100[100];
int i,j,k;
printf("array5:\n");
for(i=0;i<5;i++){
array5[i] = rand()%1000000000;
printf("%d ", array5[i]);
printf("\n");
}
printf("array10:\n");
for(j=0;j<10;j++){
array10[j]=rand()%100000000;
printf("%d ", array10[j]);
printf("\n");
}
printf("array100:\n");
for(k=0;k<100;k++){
array100[k]=rand()%1000000000;
printf("%d ", array100[k]);
printf("\n");
}
printf("newarray5");
printf("\n");
mergesoft(array5,0,6);
printfarray(array5,5);
printf("newarray10");
printf("\n");
mergesoft(array10,0,11);
printfarray(array10,10);
printf("newarray100");
printf("\n");
mergesoft(array100,0,101);
printfarray(array100,100);
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("The code took %f seconds to execute \n", cpu_time_used);
}交流学习可联系：[email protected]
标签：归并,int,元素,mid,算法,数组,排序,left From： https://blog.csdn.net/weixin_74390075/article/details/143684628