归并排序的递归实现与非递归实现代码

归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。值得注意的是归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述
归并操作的工作原理如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

时间复杂度：
时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。
空间复杂度为 O(n)
比较操作的次数介于(nlogn) / 2和nlogn - n + 1。
赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n)
归并排序比较占用内存，但却效率高且稳定的算法。
(以上摘抄自百度百科)

代码实现
自顶向上实现：
//使用辅助数组实现归并的过程


代码如下:

void MergeSort(int *aux, int *data, int l, int m, int h)
{
 int k=0, i=l, j=m+1;

for(k=l; k<=h; k++)
 {
  if(i>m)     aux[k]=data[j++];
  else if(j>h)    aux[k]=data[i++];
  else if(data[i]<data[j])        aux[k]=data[i++];
  else    aux[k]=data[j++];
 }
 for(k=l; k<=h; k++)
  data[k]=aux[k];
}

用递归实现排序的过程(自顶向下归并)


代码如下:

void Sort(int *aux, int *data, int l, int h)
{
 if(l<h)
 {
  int m=l+(h-l)/2;
  Sort(aux, data, l, m);
  Sort(aux, data, m+1, h);
  MergeSort(aux,data, l, m, h);
 }
}

用非递归实现排序的过程(自底向上归并)


代码如下:

void NonRerMerSort(int *aux, int *data, int l, int h)
{
 int i=l, j;
 for(i=l; i<=h; i=2*i)
 {
  for(j=l; j<=h-i; j+=2*i)
   MergeSort(aux, data, j, i+j-1, Min(j+2*i-1,h));
 }
}

赞 (0)

相关推荐

  • C#递归算法之归并排序

    C#递归算法之归并排序

    归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为: 1)划分子表 2)合并半子表 首先我们来讨论归并算法,归并算法将一系列数据放到一个向量中,索引范围为[first,last],这个序列由两个排好序的子表构成,以索引终点(mid)为分界线,以下面一个序列为例 7,10,19,25,12,17,21,30,48 这样的一个序列中,分为两个子序列 7,10,19,25  和

  • 老生常谈比较排序之归并排序(递归)

    老生常谈比较排序之归并排序(递归)

    归并排序里运用到算法里很重要的一个思想--分治法:将原问题分解为几个规模较小但类似于原问题的子问题--<算法导论>. 在每一层递归中都有3个步骤: 1.分解问题 2.解决问题 3.合并问题的解 举例待排序数组:{6, 5, 3, 1, 7, 2, 4},将它原始序列做分解. 可以经过不断的递归分解可以看到已经把原始数组序列不断分解为最小单位,接下来不妨将它们看做是二叉树的叶子节点. 将他们进行两两归并排序形成二叉树(也称为2路归并算法),可见二叉树的根节点即为最终序列.在这个过程中我们完成了剩

  • C#归并排序的实现方法(递归,非递归,自然归并)

    C#归并排序的实现方法(递归,非递归,自然归并)

    //Main: 复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Merge{    class Program    {        static void Main(string[] args)        {            while (true)            {                Console.W

  • 递归形式与非递归形式的斐波那契数列的用法分析

    复制代码 代码如下: <SPAN style="FONT-SIZE: 32px">采用递归形式和非递归形式实现斐波那契数列</SPAN> 复制代码 代码如下: #include "stdafx.h"#include <iostream>using namespace std;//递归形式的斐波那契数列int fibonacciRecursion(int n){ if (n == 1 || n ==2) {  return 1; }

  • JAVA实现遍历文件夹下的所有文件(递归调用和非递归调用)

    JAVA 遍历文件夹下的所有文件(递归调用和非递归调用) 1.不使用递归的方法调用. public void traverseFolder1(String path) { int fileNum = 0, folderNum = 0; File file = new File(path); if (file.exists()) { LinkedList<File> list = new LinkedList<File>(); File[] files = file.listFile

  • JavaScript实现多叉树的递归遍历和非递归遍历算法操作示例

    本文实例讲述了JavaScript实现多叉树的递归遍历和非递归遍历算法操作.分享给大家供大家参考,具体如下: 演示之前的准备工作 演示项目的文件结构: index.html jsonData.js recurrenceTree.js noRecurrenceTree.js 解释一下各个文件: index.html 是用来演示的 HTML 文件. jsonData.js 里面存储着多叉树的JSON数据. recurrenceTree.js 递归算法遍历树. noRecurrenceTree.js

  • 归并排序的递归实现与非递归实现代码

    归并排序归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.值得注意的是归并排序是一种稳定的排序方法.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为2-路归并.算法描述归并操作的工作原理如下:第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置第三步:比较两个指针

  • 先序遍历二叉树的递归实现与非递归实现深入解析

    1.先序遍历二叉树  递归实现思想:若二叉树为空,返回.否则 1)遍历根节点:2)先序遍历左子树:3)先序遍历右子树: 代码: 复制代码 代码如下: template<typename elemType> void PreOrder(nodeType<elemType> *root)  {      if(root==NULL)          return ;      visit(root->data); // visit the data    PreOrder(ro

  • java 汉诺塔Hanoi递归、非递归(仿系统递归)和非递归规律 实现代码

    程序如下: 复制代码 代码如下: View Code  /*  * Hanoi塔游戏 问题描述:  * 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具.  * 大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照  * 大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小  * 顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在  * 三根柱子之间一次只能移动一个圆盘.  *   * fuction:实现 hanoi塔  *       

  • Java二叉树的四种遍历（递归与非递归）

    目录 一.先序遍历与后序遍历 二.中序遍历 三.层序遍历 一.先序遍历与后序遍历 先序遍历根节点,再遍历左子树,再遍历右子树. 后序遍历先遍历左子树,再遍历右子树,再遍历根节点. 先序遍历递归实现: public static void preOrderByRecursion(TreeNode root) { // 打印节点值 System.out.println(root.value); preOrder(root.left); preOrder(root.right); } 先序遍历的非递归

  • Java排序算法三之归并排序的递归与非递归的实现示例解析

    归并有递归和非递归两种. 归并的思想是: 1.将原数组首先进行两个元素为一组的排序,然后合并为四个一组,八个一组,直至合并整个数组: 2.合并两个子数组的时候,需要借助一个临时数组,用来存放当前的归并后的两个数组: 3.将临时数组复制回原数组对应的位置. 非递归的代码如下: package mergesort; import java.util.Arrays; import java.util.Random; import java.util.Scanner; //归并排序的非递归算法 publ

  • c语言排序之归并排序(递归和非递归)

    目录 递归代码流程 非递归代码流程 两者比较 时间复杂度 代码(递归) 代码(非递归) 递归代码流程 归并就是把两个或多个序列合并,这里只介绍二路归并,就是不断的把序列分为2组,直到每个组有一个元素为止,然后再比较合并,直到合为1个序列,完成. 非递归代码流程 与递归不断分解数组相反,非递归直接从长度为1的子序列开始合并,直到全并为1个整个序列,复用了merge函数 两者比较 代码用非递归的方式效率更高一些: ​ 空间复杂度:从O(log2n)变为1个临时数组O(n) ​ 时间复杂度:少了递归的

随机推荐