第十三天、归并排序

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

相关文章

来自专栏李智的专栏

leetcode(1)Two Sum

Given an array of integers, return indices of the two numbers such that they add...

541
来自专栏算法修养

LeetCode 102. Binary Tree Level Order Traversal

1324
来自专栏Python小屋

Python实现单链表

class Node: '''节点结构''' def __init__(self, data, nextNode=None): #设置当前节点的值和指向下...

3275
来自专栏章鱼的慢慢技术路

数据结构与算法笔试面试题整理

b.对每一对相邻的元素做同样的工作,从开始的第一对一致到结尾的最后一对,经过这一步,最后的元素将是最大值;

943
来自专栏yl 成长笔记

链表

链表定义:一种递归的数据结构, 它是在集合类的抽象数据,它或者为空, 或者是指向一个节点 (node) 的引用, 该结点含有一个泛型的元素和一个指向另一条链表的...

541
来自专栏爱撒谎的男孩

二叉树

1094
来自专栏武培轩的专栏

剑指Offer-二叉树中和为某一值的路径

题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 思路 回...

2854
来自专栏武培轩的专栏

剑指Offer-和为S的两个数字

题目描述 输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。 输出描述: 对应每...

3034
来自专栏顶级程序员

判断链表是否有环

判断一个单向链表是否有环。(指向表头结点的指针为head) 方法一: (1)用两个指针p1和p2分别指向表头结点,即p1=p2=head (2)p1和p2分别...

4437
来自专栏我是业余自学C/C++的

二叉树 原

对高度为h的满二叉树的元素,从第一层到最后一层,在每一次中从左至右,顺序编号,从1到2^h-1.假设从满二叉树中删除k个其编号为2^h-i元素,1<=i<=k<...

732

扫码关注云+社区