C++实现合并排序的方法

本文实例讲述了C++实现合并排序的方法。分享给大家供大家参考。具体如下：

//合并排序
#include<iostream>
#include<cmath>
using namespace std;
int num[100];
void print(int num[],int len)
{
  for(int i=0;i<len;i++)
  {
    cout<<num[i]<<" ";
  }
  cout<<endl;
}
void merge(int num[],int beg,int mid,int end)
{
  int temp[100];
  int t=beg;
  int i=beg,j=mid+1;
  while(i<=mid&&j<=end)
  {
    if(num[i]<num[j])
      temp[t++]=num[i++];
    else
      temp[t++]=num[j++];
  }
  while(i<=mid)
    temp[t++]=num[i++];
  while(j<=end)
    temp[t++]=num[j++];
  for(int i=beg;i<=end;i++)
    num[i]=temp[i];
}
void mergeSort(int num[],int beg,int end)
{
  if(beg==end)
    return;
  int mid=(beg+end)/2;
  mergeSort(num,beg,mid);
  mergeSort(num,mid+1,end);
  merge(num,beg,mid,end);
}
int main()
{
  int len;
  while(cin>>len)
  {
    for(int i=0;i<len;i++)
    cin>>num[i];
    mergeSort(num,0,len-1);
    print(num,len);
  }
  return 0;
}

希望本文所述对大家的C++程序设计有所帮助。

赞 (0)

相关推荐

  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:

  • C语言合并排序及实例代码

    C语言合并排序及实例代码

    归并排序也称合并排序,其算法思想是将待排序序列分为两部分,依次对分得的两个部分再次使用归并排序,之后再对其进行合并.仅从算法思想上了解归并排序会觉得很抽象,接下来就以对序列A[0], A[l]-, A[n-1]进行升序排列来进行讲解,在此采用自顶向下的实现方法. 操作步骤如下: (1)将所要进行的排序序列分为左右两个部分,如果要进行排序的序列的起始元素下标为first,最后一个元素的下标为last,那么左右两部分之间的临界点下标mid=(first+last)/2,这两部分分别是A[first

  • Ruby实现的合并排序算法

    算法课的作业,利用分治法,合并排序. #encoding: utf-8 #author: xu jin, 4100213 #date: Oct 27, 2012 #MergeSort #to sort an array by using MergeSort algorithm #example output: #The original array is:[4, 32, 84, 58, 49, 40, 75, 29, 82, 21, 70, 37, 70] #The sorted array i

  • Javascript排序算法之合并排序（归并排序）的2个例子

    归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个

  • 合并排序(C语言实现)

    合并排序(C语言实现)

    其基本模式如下: 分解:把一个问题分解成与原问题相似的子问题 解决:递归的解各个子问题 合并:合并子问题的结果得到了原问题的解. 现在就用递归算法,采用上面的分治思想来解合并排序. 合并排序(非降序) 分解:把合并排序分解成与两个子问题 伪代码: 复制代码 代码如下: MERGE_SORT(A, begin, end) if begin < end then mid<- int((begin + end)/2) MERGE_SORT(A, begin, mid) MERGE_SORT(A, m

  • Python选择排序、冒泡排序、合并排序代码实例

    前两天刚装了python 3.1.1, 禁不住技痒写点code. 1.选择排序 复制代码 代码如下: >>> def SelSort(L):     length=len(L)     for i in range(length-1):         minIdx=i         minVal=L[i]         j=i+1         while j<length:             if minVal>L[j]:                 mi

  • C++实现合并排序的方法

    本文实例讲述了C++实现合并排序的方法.分享给大家供大家参考.具体如下: //合并排序 #include<iostream> #include<cmath> using namespace std; int num[100]; void print(int num[],int len) { for(int i=0;i<len;i++) { cout<<num[i]<<" "; } cout<<endl; } void m

  • java交换排序之奇偶排序实现方法

    java交换排序之奇偶排序实现方法

    本文实例讲述了java交换排序之奇偶排序实现方法.分享给大家供大家参考.具体如下: 奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算.这是与冒泡排序特点类似的一种比较排序. 该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换.下一步重复该操作,但针对所有的(偶-奇)位置数字对.如此交替进行下去. 处理器数组的排序 在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连.所有处理器可

  • Python实现针对中文排序的方法

    本文实例讲述了Python实现针对中文排序的方法.分享给大家供大家参考,具体如下: Python比较字符串大小时,根据的是ord函数得到的编码值.基于它的排序函数sort可以很容易为数字和英文字母排序,因为它们在编码表中就是顺序排列的. >> print ','< '1'<'A'<'a'<'阿' True 但要很处理中文就没那么容易了.中文通常有拼音和笔画两种排序方式,在最常用中文标准字符集GB2312中,3755个一级中文汉字是按照拼音序进行编码的,而3008个二级汉

  • C++归并法+快速排序实现链表排序的方法

    C++归并法+快速排序实现链表排序的方法

    本文主要介绍了C++归并法+快速排序实现链表排序的方法,分享给大家,具体如下: 我们可以试用归并排序解决: 对链表归并排序的过程如下. 找到链表的中点,以中点为分界,将链表拆分成两个子链表.寻找链表的中点可以使用快慢指针的做法,快指针每次移动 2 步,慢指针每次移动 1步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点. 对两个子链表分别排序. 将两个排序后的子链表合并,得到完整的排序后的链表 上述过程可以通过递归实现.递归的终止条件是链表的节点个数小于或等于 1,即当链表为空或者链

  • python排序的方法实例总结

    1.冒泡排序 它反复访问要排序的元素列,并依次比较两个相邻的元素.如果顺序(如从大到小)错了,就交换它们.访问元素的工作是反复进行,直到没有相邻元素需要交换,也就是说元素列已经排序完成. 2.选择排序 首次从待排序的数据元素中选择最小(或最大)的元素,存储在序列的开始位置,然后从剩余的未排序元素中找到最小(大)元素,然后放在已排序的末尾.直到所有元素都被排序. 3.插入排序 对于未排序的数据,通过构建有序的序列,在已排序的序列中从后向前扫描,找到相应的位置并插入.插入式排序在实现上,在从后向前扫

  • Java实现两个随机数组合并进行排序的方法

    Java实现两个随机数组合并进行排序的方法

    目录 前言: 一.什么是线性表 二.ArrayList集合 三.用线性表的思想排序数组间排序 四.冒泡排序: 前言: ​ 小Du猿结束"996ICP"CRUD开发工作生活,重新进入了校园学习生活.本周开始了第二周数据结构的基础知识学习,大爱向宇老师的上课方式,用生动形象的方式讲解抽象概念,但一开口就是LSP.O(∩_∩)O,向向宇大佬致敬,菜鸡小Du猿投来膜拜的眼光. ​ 此博客用Java实现线性表的思想,实现数组的排序和序列化.序列化的排序方式采用冒泡排序的方式,但小Du猿正在优化该

  • Hadoop对文本文件的快速全局排序实现方法及分析

    一.背景 Hadoop中实现了用于全局排序的InputSampler类和TotalOrderPartitioner类,调用示例是org.apache.hadoop.examples.Sort. 但是当我们以Text文件作为输入时,结果并非按Text中的string列排序,而且输出结果是SequenceFile. 原因: 1) hadoop在处理Text文件时,key是行号LongWritable类型,InputSampler抽样的是key,TotalOrderPartitioner也是用key去

随机推荐