第十三天、归并排序

题目 用归并排序法对一组数据由小到大进行排序,数据分别为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 条评论
登录 后参与评论

相关文章

来自专栏Python疯子

数据分析之numpy

ndarray概述 创建n维数组 接收的是列表类型,所有元素类型必须相同 shape表示各维度大小的元组 dtype表示数组数据类型对象

991
来自专栏尾尾部落

普林斯顿大学算法公开课笔记——插入排序

现有一组数组 arr = [5, 6, 3, 1, 8, 7, 2, 4],共有八个记录,排序过程如下:

981
来自专栏老秦求学

位运算及其编程妙用

位操作符通常用来对操作数进行位级的操作运算。首先将运算符转换为位级,然后对操作数执行计算。可以在比特级执行诸如加法,减法,乘法等的数学运算以便更快地处理。

1583
来自专栏Java帮帮-微信公众号-技术文章全总结

第六天 知识点练习与回顾【悟空教程】

1496
来自专栏浪淘沙

Python学习总结5--有序列表list和tuple

    2. 用len()函数可以获得list元素的个数     3. 用索引来访问list中每一个位置的元素,记得索引是从0开始的 如...

633
来自专栏mathor

波兰表达式

834
来自专栏爱撒谎的男孩

冒泡排序算法

1413
来自专栏尾尾部落

[LeetCode]Reverse Integer题解 [LeetCode]Reverse Integer题解

要点 本题考查的是整数相加的溢出处理,检查溢出有这么几种办法: – 两个正数数相加得到负数,或者两个负数相加得到正数,但某些编译器溢出或优化的方式不一样 ...

812
来自专栏Bingo的深度学习杂货店

Q190 Reverse Bits

Reverse bits of a given 32 bits unsigned integer. For example: given input 43261...

3335
来自专栏互联网大杂烩

合并排序

合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法 的一个非常典型的应用。 合并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待...

942

扫码关注云+社区