第十三天、归并排序

题目 用归并排序法对一组数据由小到大进行排序,数据分别为695、458、362、789、12、15、163、23、2、986。 1、程序分析     归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。     归并是将两个或多个有序记录序列合并成一个有序序列。归并方法有很多种,一次对两个有序记录进行归并,称为二路归并排序,也有三路归并排序及多路归并排序。本例程采用二路归并排序,基本方法如下:     a、将n个记录看成n个长度为1的有序子表。     b、将两两相邻的有序子表进行归并。     c、重复执行b,直到归并成一个长度为n的有序表。 2、程序实现

/******************************************************************
 * Topic     :    用归并排序法对一组数据由小到大进行排序,数据分别为
 *                 695、458、362、789、12、15、163、23、2、986
 * File Name :    MergeSort
 * Author    :    Jack Cui
 * Created   :    4 April 2016
 * ****************************************************************/
#include <stdio.h>
/*归并排序函数声明*/
void MergeSort(int iSourceArr[],int iTempArr[],int iStartIndex,int iEndIndex);
void Merge(int iSourceArr[],int iTempArr[],int iStartIndex,int iMidIndex,int iEndIndex);

int main(void)
{
    int i,iArr_b[10],iArr_a[10];
    printf("请输入10个数:\n");
    for(i = 0;i < 10;i++)
        scanf("%d",&iArr_a[i]);
    MergeSort(iArr_a,iArr_b,0,9);
    printf("快速排序后的顺序为:\n");
    for(i = 0;i < 10;i++)
        printf("%5d",iArr_a[i]);
    printf("\n");
    return 0;
}
/**********************************
*函数名称:MergeSort
*参数说明:iSourceArr[]  原始数组
*         iTempArr[]    临时数组
*          iStartIndex  起始位置索引值
*          iEndIndex    结束位置索引值
*说明:    二路归并排序
***********************************/
void MergeSort(int iSourceArr[],int iTempArr[],int iStartIndex,int iEndIndex)
{
    int iMidIndex;
    if(iStartIndex < iEndIndex)
    {
        iMidIndex = (iStartIndex + iEndIndex) / 2;
        /*递归调用将iSourceArr[iStartIndex]~iSourceArr[iMidIndex]归并成有序的*/
        MergeSort(iSourceArr,iTempArr,iStartIndex,iMidIndex);
        /*递归调用将iSourceArr[iMidIndex+1]~iSourceArr[iEndIndex]归并成有序的*/
        MergeSort(iSourceArr,iTempArr,iMidIndex+1,iEndIndex);
        /*调用函数将前两部分归并到iSourceArr[iStartIndex]~iSourceArr[iEndIndex]*/
        Merge(iSourceArr,iTempArr,iStartIndex,iMidIndex,iEndIndex);
    }
}
/**********************************
*函数名称:Merge
*参数说明:iSourceArr[]   原始数组
*         iTempArr[]    临时数组
*         iStartIndex   起始位置索引值
*         iMidIndex     中间位置索引值
*         iEndIndex     结束位置索引值
*说明:    归并排序
***********************************/
void Merge(int iSourceArr[],int iTempArr[],int iStartIndex,int iMidIndex,int iEndIndex)
{
    int i = iStartIndex,j = iMidIndex + 1,k = iStartIndex;
    while((i <= iMidIndex) && (j <= iEndIndex))        //当i和j都在要合并的部分中成立
    {
        if(iSourceArr[i] >= iSourceArr[j])
            iTempArr[k++] = iSourceArr[j++];
        else
            iTempArr[k++] = iSourceArr[i++];
    }
    while(i <= iMidIndex)                //将iStartIndex~iMidIndex内,未比较的数组顺次加到iTempArr数组中
        iTempArr[k++] = iSourceArr[i++];
    while(j <= iEndIndex)                //将iMidIndex+1~iStartIndex内,未比较的数组顺次加到iTempArr数组中
        iTempArr[k++] = iSourceArr[j++];
    for(i = iStartIndex; i <= iEndIndex; i++)
        iSourceArr[i] = iTempArr[i];
}

3、结果显示

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java 源码分析

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 首先考虑下如何将将二个有序数列...

2565
来自专栏算法与数据结构

归并排序详解 和逆序数计算

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序...

1805
来自专栏深度学习思考者

Python学习(三) 八大排序算法的实现(下)

本文Python实现了插入排序、基数排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序的后面四种。 上篇:Python学习(三) 八大排序算...

23610
来自专栏芋道源码1024

排序算法总结(多图)

不稳定的排序: 稳定性一个形象的比喻,本来有两个并列第三,一排序把原来并列的顺序给变了。 比如:选择排序、快速排序、堆排序、希尔排序; 参考链接

543
来自专栏我是东东强

常见算法之排序

各类排序算法,不仅是算法基本功,也是面试中永恒的考题,关于每种算法思想、实现(递归与非递归)以及时空复杂度分析是必须牢牢把握的送分题。本文先将排序算法按不同标准...

872
来自专栏数据结构与算法

1009 产生数 2002年NOIP全国联赛普及组

009 产生数 2002年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 De...

2464
来自专栏静默虚空的博客

排序一 冒泡排序

要点 冒泡排序是一种交换排序。 什么是交换排序呢? 交换排序:两两比较待排序的关键字,并交换不满足次序要求的那对数,直到整个表都满足次序要求为止。 算法思想 它...

2025
来自专栏云霄雨霁

排序----插入排序

1300
来自专栏菩提树下的杨过

数据结构与算法C#版笔记--排序(Sort)-上

这里讨论的仅限于内部排序(即全部数据都在内存中,通过CPU运算处理元素排序),而且仅限顺序表排序(即不讨论链表,树状结构等结构的排序) 注:排序后的结果可以从小...

20110
来自专栏和蔼的张星的图像处理专栏

39. 恢复旋转排序数组找分界点+翻转数组

给定一个旋转排序数组,在原地恢复其排序。 说明: 什么是旋转数组? 比如,原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3...

902

扫码关注云+社区