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 is: [4, 21, 29, 32, 37, 40, 49, 58, 70, 70, 75, 82, 84]

MAX = 100
arrayInt = Array.new
for index in (0..12)
 arrayInt[index] = rand(100) #produce 12 random number
end
puts "The original array is：" + arrayInt.to_s

def merge(arr, left, middle, right)
 arrL ,arrR = Array.new, Array.new
 arrL[0..(middle - left)], arrR[0..(right - middle - 1)] = arr[left..middle], arr[middle + 1.. right]
 arrL[arrL.size] ,arrR[arrR.size]= MAX, MAX
 for k in (left..right)
  arrL.first <= arrR.first ? (arr[k] = arrL.shift) : (arr[k] = arrR.shift)
 end
end

def merge_sort(arr, left, right)
 if left < right then
  middle = (left + right)/2
  merge_sort(arr, left, middle)
  merge_sort(arr, middle + 1, right)
  merge(arr, left, middle, right)
 end
end

merge_sort(arrayInt, 0, arrayInt.length-1)
puts "The sorted array is: " + arrayInt.to_s
赞 (0)

相关推荐

  • Ruby实现的矩阵连乘算法

    动态规划解决矩阵连乘问题,随机产生矩阵序列,输出形如((A1(A2A3))(A4A5))的结果. 代码: #encoding: utf-8 =begin author: xu jin, 4100213 date: Oct 28, 2012 MatrixChain to find an optimum order by using MatrixChain algorithm example output: The given array is:[30, 35, 15, 5, 10, 20, 25]

  • Ruby实现的图片滤镜算法代码

    Ruby实现的图片滤镜算法代码

    原图 一.灰度算法 彩色照片每一个像素的颜色值由红.绿.蓝三种值混合而成,红绿蓝的取值分别由很多种,于是像素的颜色值也可以有很多种颜色值,这就是彩色图片的原理,而灰度照片则只有256种颜色,一般的处理方法是将图片颜色值的RGB三个通道值设为一样,这样图片的显示效果就会是灰色. 灰度处理一般有三种算法: 最大值法:即新的颜色值R＝G＝B＝Max(R,G,B),这种方法处理后的图片看起来亮度值偏高. 平均值法:即新的颜色值R＝G＝B＝(R+G+B)/3,这样处理的图片十分柔和 加权平均值法:即新的颜

  • Ruby实现的各种排序算法

    时间复杂度:Θ(n^2) Bubble sort 复制代码 代码如下: def bubble_sort(a)    (a.size-2).downto(0) do |i|      (0..i).each do |j|        a[j], a[j+1] = a[j+1], a[j] if a[j] > a[j+1]      end    end    return a  end Selection sort 复制代码 代码如下: def selection_sort(a)    b =

  • ruby实现的插入排序和冒泡排序算法

    1.插入排序 复制代码 代码如下: seq = [3,4,9,0,2,5,9,7,1] 1.upto(seq.length-1) do |i|  if seq[i] < seq[i-1]    tmp = seq[i]    j = i-1    while(j>=0 && tmp<seq[j]) do      seq[j+1] = seq[j]      j=j-1    end    seq[j+1]=tmp  endend seq.each {|num| puts

  • Ruby实现的3种快速排序算法

    刚学Ruby,正巧算法老师鼓励用不熟悉的语言来写算法,我就用Ruby吧~~ 话说Ruby可真是超厉害,好多凭直觉的方法都可以用.....无限膜拜中.... 期间我遇到了invalid multibyte char (US-ASCII)的错误,解决办法是在开头加一个#encoding:utf-8 这个错误在stackoverflow上有人问到过,某人给出的回答是 Write # encoding: utf-8 on top of that file. That changes the defaul

  • Ruby实现二分搜索(二分查找)算法的简单示例

    Ruby实现二分搜索(二分查找)算法的简单示例

    在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search).对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法.搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束:如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较.如果在某一步骤数组为空,则代表找不到.这种搜索算法每一次比较都使搜索范围缩小一半

  • Ruby实现的最优二叉查找树算法

    算法导论上的伪码改写而成,加上导论的课后练习第一题的解的构造函数. 复制代码 代码如下: #encoding: utf-8 =begin author: xu jin date: Nov 11, 2012 Optimal Binary Search Tree to find by using EditDistance algorithm refer to <<introduction to algorithms>> example output: "k2 is the r

  • 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

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

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

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

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

  • python 排序算法总结及实例详解

    python 排序算法总结及实例详解

    总结了一下常见集中排序的算法 归并排序 归并排序也称合并排序,是分治法的典型应用.分治思想是将每个问题分解成个个小问题,将每个小问题解决,然后合并. 具体的归并排序就是,将一组无序数按n/2递归分解成只有一个元素的子项,一个元素就是已经排好序的了.然后将这些有序的子元素进行合并. 合并的过程就是 对 两个已经排好序的子序列,先选取两个子序列中最小的元素进行比较,选取两个元素中最小的那个子序列并将其从子序列中 去掉添加到最终的结果集中,直到两个子序列归并完成. 代码如下: #!/usr/bin/p

  • 必须知道的C语言八大排序算法(收藏)

    必须知道的C语言八大排序算法(收藏)

    概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1.插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到

  • python实现八大排序算法（2）

    python实现八大排序算法（2）

    本文接上一篇博客python实现的八大排序算法part1,将继续使用python实现八大排序算法中的剩余四个:快速排序.堆排序.归并排序.基数排序 5.快速排序 快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的. 算法思想: 已知一组无序数据a[1].a[2].--a[n],需将其按升序排列.首先任取数据a[x]作为基准.比较a[x]与其它数据并排序,使a[x]排在数据的第k位,并且使a[1]~a[k-1]中的每一个数据<a[x],a[k+1]~a[n]中的每一个数

  • JS及PHP代码编写八大排序算法

    从学习数据结构开始就接触各种算法基础,但是自从应付完考试之后就再也没有练习过,当在开发的时候也是什么时候使用什么时候去查一下,现在在学习JavaScript,趁这个时间再把各种基础算法整理一遍,分别以JS和PHP语法的方式编写代码. 1.冒泡排序 原理:临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束 时间复杂度:平均情况:O(n2)  最好情况:O(n) 最坏情况:O(n2)

  • python实现八大排序算法（1）

    python实现八大排序算法（1）

    排序 排序是计算机内经常进行的一种操作,其目的是将一组"无序"的记录序列调整为"有序"的记录序列.分内部排序和外部排序.若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序.反之,若参加排序的记录数量很大,整个序列的排序过程不可能完全在内存中完成,需要访问外存,则称此类排序问题为外部排序.内部排序的过程是一个逐步扩大记录的有序序列长度的过程. 看图使理解更清晰深刻: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序

  • 排序算法的Java实现全攻略

    Collections.sort() Java的排序可以用Collections.sort() 排序函数实现. 用Collections.sort方法对list排序有两种方法: 第一种是list中的对象实现Comparable接口,如下: /** * 根据order对User排序 */ public class User implements Comparable<User>{ private String name; private Integer order; public String

随机推荐