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

归并排序（非递归）超详细解答！！

news 来源：原创 2024/5/17 17:56:43

首先归并排序采取了分治的思想，其次在数据存储的过程中，需要开辟一个辅助数组进行两个数组按序插入，最后再将辅助数组中数据返回。

代码详细解答如下：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n,j,i;

    scanf("%d",&n);
    int num[n],num1[n];//num1为辅助存储数组

    for( i=0; i<n; i++)
        scanf("%d",&num[i]);

    int leftstart,leftend;
    int rightstart,rightend;

    for( i=1; i<n; i*=2)//一开始数组长度单位为1，从1开始逐渐乘2直到等于n大小
    {
        for (leftstart=0; leftstart<n-i; leftstart=rightend)//leftstart=rightend意思为从左边逐渐过渡到右边的一个又一个数组，因为被分成了间隔为i的多个数组，都要归并排序
        {
            leftend = leftstart + i;//左边的结束就是右边的开始，左边数组的开始与结束的间隔为i那么长
            rightstart = leftstart + i;
            rightend = rightstart + i;

            if(rightend>n)
            {
                rightend = n;//rightend在循环时可能发生越界，拉回来
            }
            j=0;
            while (leftstart<leftend && rightstart<rightend)//不能等于，因为从0开始存储，leftend-1是最后一个了，等于时已经是右边那个数组的开始了
            {
                if(num[leftstart]<num[rightstart])//将一个数组从中分为两边，即归并排序分为两个更小数组，然后将这两个数组中的数按大小插入num1数组
                    num1[j++] = num[leftstart++];
                else
                    num1[j++] = num[rightstart++];
            }

            if(leftstart<leftend)//左边那部分还没全部归并入辅助数组
            {
                while (leftstart <leftend)
                {
                    num1[j++] = num[leftstart++];
                }
            }
            else if(rightstart<rightend)//右边那部分还没全部归并入辅助数组
            {
                while (rightstart <rightend)
                {
                    num1[j++] = num[rightstart++];
                }
            }

            while(j>0)
            {
                num[--rightstart] = num1[--j];//再将num1的数放回去，num1作为两个数组按大小合并后的数组数据返回给num数组
            }
        }

        //for(int l=0; l<n; l++)
        //    printf("%d ",num[l]);
        //printf("\n");

    }
    
    printf("归并排序后:");
    for(int l=0; l<n; l++)
            printf("%d ",num[l]);

}

欢迎大家评论区留言

觉得该篇文章有用的请不要忘记忘记点击右下角的大拇指~

欢迎大家关注我的公众号：Smooth前端成长记录
公众号同步更新CSDN博客内容，想方便阅读博客的C友可以来关注我的公众号以便获得更优良的阅读体验~