首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

用Ruby实现从输入数组中剔除元素的merge_sort算法

merge_sort算法是一种经典的排序算法,它采用分治法的思想,将一个数组分成两个子数组,然后分别对子数组进行排序,最后将两个有序的子数组合并成一个有序的数组。

Ruby是一种动态、面向对象的编程语言,具有简洁、优雅的语法和丰富的内置函数库,非常适合用于实现merge_sort算法。

下面是用Ruby实现从输入数组中剔除元素的merge_sort算法的代码示例:

代码语言:txt
复制
def merge_sort(arr)
  return arr if arr.length <= 1

  mid = arr.length / 2
  left = merge_sort(arr[0...mid])
  right = merge_sort(arr[mid..-1])

  merge(left, right)
end

def merge(left, right)
  result = []
  i = j = 0

  while i < left.length && j < right.length
    if left[i] < right[j]
      result << left[i]
      i += 1
    else
      result << right[j]
      j += 1
    end
  end

  result.concat(left[i..-1]) if i < left.length
  result.concat(right[j..-1]) if j < right.length

  result
end

# 示例用法
input = [5, 2, 8, 3, 1, 9, 4, 7, 6]
output = merge_sort(input)
puts output.inspect

这段代码实现了一个名为merge_sort的方法,它接受一个数组作为输入,并返回一个经过排序的新数组。merge_sort方法使用递归的方式将输入数组分成两个子数组,然后分别对子数组调用merge_sort方法进行排序。最后,调用merge方法将两个有序的子数组合并成一个有序的数组。

这个算法的时间复杂度为O(nlogn),其中n是输入数组的长度。它在处理大规模数据时表现良好,并且具有稳定性,即相等元素的相对顺序不会改变。

推荐的腾讯云相关产品:腾讯云云服务器(CVM)和腾讯云对象存储(COS)。

  • 腾讯云云服务器(CVM):提供可扩展的云服务器实例,可满足各种计算需求。详情请参考腾讯云云服务器
  • 腾讯云对象存储(COS):提供安全、稳定、低成本的对象存储服务,适用于存储和处理各种类型的数据。详情请参考腾讯云对象存储

以上是关于用Ruby实现从输入数组中剔除元素的merge_sort算法的完善且全面的答案。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

算法基础-基础算法

这里可以运用我们性价比最高,代码最好写,效率特高的归并排序算法 归并排序中的左数组和右数组在内部都是有序且相对原数组中的位置都是从左到右的,我们可以利用这一性质当我们判断左数组中的某一个元素(下标为i)...大于右数组时, 则该元素往后的数都与右数组中的该数构成逆序对即会产生mid - i + 1个逆序对 核心代码 if(q[i] <= q[j]) temp[k ++ ] = q[i ++ ]; else...对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 如果数组中不存在该元素,则返回 -1 -1。 输入格式 第一行包含整数 n 和 q,表示数组长度和询问个数。...输出格式 共 q 行,每行包含两个整数,表示所求元素的起始位置和终止位置。 如果数组中不存在该元素,则返回 -1 -1。...和r必定相等而且满足 check(l) 且 check(r); 当然本题用c++的算法库的二分查找函数 lower_bound 和upper_bound做是更快的 lower_bound(array +

1.5K40

数据结构与算法之三 深入学习排序

在快速排序算法中,你: 从名为​枢轴 的列表处选择元素 。...通常,选择第一个元素作为枢轴,但是其会导致 O(n2) 的最糟用例效率。 如果您选择所有值的中间值作为枢轴 ,则效率将是 O(n log n) 。 什么是快速排序算法的平均用例的比较总次数。...将排序的数组 B 中的所有元素复制到原始数组 arr 中 若要排序此列表,您需要按递归方式将列表划分为两个几乎完全相等的子列表,直 到每个子列表仅包含一个元素。  ...归并列表的最佳、平均和最糟用例效率之间没有差异 ,因为所有这些效率均需要相 同的时间量。 哪个算法使用以下步骤来排序给出的元素列表?        1.     ...*/ using System; using System.Text; class Merge_Sort { private int[]arr=new int[20]; //定义数组,你输入数字,

10910
  • 算法之-归并排序算法,插入排序算法「建议收藏」

    这个思想在实际工作中的作用很大,特别是处理大数据和做复杂运算的时候。 归并排序的基础是归并操作merge,即将两个有序数组合并为一个有序数组。...归并排序的算法思路为: 第一次扫描数组,将数组中相邻的两个元素merge为有序数组 第二次扫描,将相邻的有序数组再合并为更大的一个有序数组 再进行n次扫描,不断合并数组,直到排序完毕 当中的归并操作...它的工作原理是通过构建有序序列。对于未排序数据。在已排序序列中从后向前扫描,找到对应位置并插入。 插入排序在实现上。通常採用in-place排序(即仅仅需用到O(1)的额外空间的排序)。...因而在从后向前扫描过程中,须要重复把已排序元素逐步向后挪位,为最新元素提供插入空间。 一般来说,插入排序都採用in-place在数组上实现。...详细算法描写叙述例如以下: 从第一个元素開始,该元素能够觉得已经被排序 取出下一个元素,在已经排序的元素序列中从后向前扫描 假设该元素(已排序)大于新元素,将该元素移到下一位置 反复步骤3,直到找到已排序的元素小于或者等于新元素的位置

    38830

    面试官:手写归并排序、快排能做到吗?我:小case!

    递归这一思想至关重要,因为很多算法都是基于递归展开的。其中最经典的就是分治算法,应该算是递归这一思想最经典的应用,也是面试中的常客。...我们举个例子,假设我们有两个数组a和b,我们要把它们当中的元素都放入数组c当中,并且还要保证数组c中的元素依然是有序的。...所以我们直接把数组一分为二,然后分别调用merge_sort就得到了两个有序的子数组了。 得到两个有序的子数组之后,我们要做的就剩下很简单的归并操作了。...如果还不明白的同学可以看一下下面这张动图: 如果用C++写过快排的同学肯定对于快排的代码印象深刻,它是属于典型的原理不难,但是写起来很麻烦的算法。...当然对于快速排序算法来说,如果数组是倒序的,我们默认取最后一个元素作为标杆的话,我们是无法均分数组的,因为除标杆之外所有的元素都比它大。在这种情况下算法的复杂度会退化到 。

    60520

    每日一题计算右侧小于当前元素的个数

    ---- 题目描述 给定一个整数数组nums,按要求返回一个新数组counts。数组counts有该性质:counts[i]的值是nums[i]右侧小于nums[i]的元素的数量。...示例输入 [5,2,6,1] 示例输出 [2,1,1,0] 示例解释 5的右侧有2个更小的元素2和1。2的右侧仅有1个更小的元素1。6的右侧有1个更小的元素1。1的右侧有0个更小的元素。...树状数组是一个数组,有两种操作。一个是对某个位置的元素加值或减值,一个是查询第一个位置到某个位置的元素之和。暴力的话每次查询操作复杂度都是 ? ,而树状数组可以做到 ? 。...归并排序 归并排序算法想必大家应该很熟悉了。就是将数组划分为左右两个长度相等的子数组,然后分别递归排序,得到左右两个有序的子数组。...然后把这些数依次放入临时数组中,并得到结论:右半部分子数组中比a[i]小的数有j - m - 1个。然后把a[i]也推进临时数组里,重复进行上述过程,直到i>m。

    1.2K10

    AcWing 505. 火柴排队(每日一题)

    现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为: 其中 ai 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度。 ...第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。 第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。...数据范围 1≤n≤10^5, 0≤火柴高度≤2^31−1, 输入样例: 4 2 3 1 4 3 2 1 4 输出样例: 1 解题思路: 离散化+归并排序求逆序对(或者树状数组求逆序对) 树状数组比较抽象...根据结论,一个数组b中的元素移动到另一个数组a使其位置相同,最少需要移动b的逆序对数(前提是排好序),那么我们如何求逆序对呢,想一想归并排序的实现,可以利用前面数组l的数l[i]大于后面数组r的数r[j...离散化: 离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。 通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。

    7310

    再看一次吧,保证你学会归并排序

    在大型数据上的表现依然很差,所以计算学家们又马不停蹄地继续研究起了新的排序算法。 当尝试着将分而治之的思想应用在排序上之后,人们惊人地发现算法的复杂度相比于从前有了一个质的提升。...我们举个例子: a = [1, 4, 6] b = [2, 4, 5] c = [] 我们用i和j分别表示a和b两个数组的下标,c表示归并之后的数组,显然一开始的时候i, j = 0, 0。...因为我们在插入元素的时候还需要考虑数组越界的问题。...表面上看的确如此,但数组有序性这个概念里面有一个bug,就是当数组当中只有一个元素的时候,它就是天然有序的。 所以我们可以将数组一直往下拆分,直到数组当中只有一个元素为止。...接着一层一层地归并回来,当所有元素归并结束的时候,数组就完成了排序。这也就是归并排序的全部过程。 如果还不理解,还可以参考一下下面的动图。 ‍最后,我们完整地将整个算法用代码实现一遍。

    40730

    【聊聊开发中十分重要的“必抓!”算法】

    一:前言 算法在计算机科学和软件开发中具有重要的地位,它们是解决问题和优化过程的关键工具。...2.递归排序 递归排序其实就是上面说的两种:快速和归并 快速排序(Quick Sort): 选择一个基准元素,通常是数组中的一个元素。...将数组分区为两个子数组:小于基准元素的元素放在左边,大于基准元素的元素放在右边。 对左右子数组分别递归地应用快速排序算法。 终止条件是子数组的长度为 0 或 1,此时它们已经有序。...在此案例中,通过递归调用 merge_sort 函数对原始数组进行拆分和排序,并通过辅助函数 merge 将两个有序的子数组合并为一个有序数组。...哈希算法的主要特点是: 确定性:对于相同输入,哈希算法始终产生相同的哈希值。 效率:计算哈希值的过程应该快速且高效。

    16620

    重学数据结构和算法(五)之归并排序、快速排序

    目录 归并排序(Merge Sort) 归并排序的原理:分治法 如何用递归代码来实现归并排序 快速排序(Quicksort) 代码实现快速排序 O(n) 时间复杂度内求无序数组中的第 K 大元素 最近学习了极客时间的...归并排序的原理:分治法 归并排序和快速排序都用到了分治思想,非常巧妙。我们可以借鉴这个思想,来解决非排序的问题,比如:如何在 O(n) 的时间复杂度内查找一个无序数组中的第 K 大元素?...递归地解这些子问题,然后将这些子问题的解组合为原问题的解。 分治思想跟我们前面讲的递归思想很像。是的,分治算法一般都是用递归来实现的。...while (rightStart <= right) { tmpArray[temp++] = a[rightStart++]; } //将temp中的元素全部拷贝到原数组中...return low; } } O(n) 时间复杂度内求无序数组中的第 K 大元素 快排核心思想就是分治和分区,我们可以利用分区的思想,来解答开篇的问题:O(n) 时间复杂度内求无序数组中的第

    1.3K20

    算法导论:分治法,python实现合并排序MERGE-SORT

    合并排序元素个数为2的幂数的列表 思想:将原始列表中的元素,拆分为个数为2的子列表,将每个子列表进行合并排序,加以整合变为左右两部分都排好序的元素个数为4的子列表..........,4个2个元素的子列表 LR1, RR1 = dividelist(R1) MERGE_SORT(LL1) MERGE_SORT(RL1)             # 调用合并排序函数,把元素个数为2的...合并为一个元素个数为8的即包含原始列表所有元素的左右两部分都排好序的完整列表 MERGE_SORT(B1)         # 调用合并排序函数,得到最终结果 print(B1)存在的问题,拆分和整合部分由于自己目前能力不足...但根据分治法的原理,整个算法的运行速度比普通排序要快,时间复杂度为O(n*lgn),插入排序法时间复杂度为O(n^2)。 3....用Python实现任意排列数组的合并排序 """Python实现合并排序""" def MERGE(A, p, q, r):     """定义合并函数"""     n1 = q - p     n2

    55500

    归并排序 详解「建议收藏」

    nlogn的优势将会比n^2越来越大,当n=10^5的时候,nlogn的算法要比n^2的算法快6000倍,那么6000倍是什么概念呢,就是如果我们要处理一个数据集,用nlogn的算法要处理一天的话,用...如图: 归并到上一个层级之后继续归并,归并到更高的层级,如图: 直至最后归并完成。 那么如何归并呢?我们是否可以用O(n)的算法将两个数组归并到一起形成一个数组呢?...如果可以的话,我们将可以用递归的过程来实现整个归并。这是你想起来很简单但是操作起来并不是那么简单的问题。 归并细节: 比如有两个已经排序好的数组,如何将他归并成一个数组?...只不过现在计算机中时间的效率要比空间的效率重要的多。无论是内存也好还是硬盘也好可以存储的数据越来越多,所以设计一个算法,时间复杂度是要优先考虑的。 整体来讲我们要使用三个索引来在数组内进行追踪。...蓝色的箭头表示最终选择的位置,而红色的箭头表示两个数组当前要比较的元素,比如当前是2与1比较,1比2小,所以1放到蓝色的箭头中,蓝色的箭头后移,1的箭头后移。

    39820

    快排查找数组中的第K个最大元素

    因为分治算法一般都是用递归实现: 分治是一种解决问题的处理思想 递归是一种编程技巧 二者不冲突。 写递归代码的技巧就是,分析得出递推公式,然后找到终止条件,最后将递推公式翻译成递归代码。...,再把另一数组中的数据依次加到临时数组的末尾,这时,临时数组中存储的就是两个子数组合并后结果。...最后再把临时数组tmp中的数据拷贝到原数组A[p…r]中。...合并过程中,若A[p…q]和A[q+1…r]之间有值相同的元素,则可像伪代码中那样,先把A[p…q]中的元素放入tmp数组。这就保证值相同的元素,在合并前后的先后顺序不变。...那我每次取数组中的最小值,将其移动到数组最前,然后在剩下的数组中继续找最小值,以此类推,执行K次,找到的数据不就是第K大元素了吗?

    4.1K10

    Python算法——归并排序

    归并排序(Merge Sort)是一种分治排序算法,它将数组分成两个子数组,分别对子数组进行排序,然后合并两个有序子数组以得到一个有序数组。归并排序是一种高效的排序算法,具有稳定性和适用性广泛的特点。...分治的关键在于如何合并两个有序子数组。归并排序的工作过程如下: 将数组分成两半,直到每个子数组只包含一个元素。 递归地将子数组排序。 合并两个有序子数组,得到一个更大的有序数组。...10, 27, 38, 43, 82] Python实现归并排序 下面是Python中的归并排序实现: def merge_sort(arr): if len(arr) 的排序算法,不仅适用于大型数据集,还具有稳定性。 总之,归并排序是一种高效的分治排序算法,通过将数组分成两半,递归地排序子数组,然后合并有序子数组,实现了对数组的归并排序。...了解归并排序有助于理解分治算法的思想,并为排序大型数据集提供了一个强大的工具。

    47810

    归并排序模板

    归并排序属于分治算法 分治法在每一层递归上都有三个步骤: step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题; step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题...; step3 合并:将各个子问题的解合并为原问题的解; 归并排序模板 void mergeSort(int q[], int l, int r) { //递归终止的条件 if(l >=...r) return; //第一步:分解成子问题 int mid = l + r >> 1; //第二步:递归处理子问题 merge_sort(q, l, mid )...IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //创建数组并设置数组长度...int n = Integer.parseInt(br.readLine()); int[] arr = new int[n]; //输入数组元素

    19820

    详解排序算法(Python实现)

    它的名称来自算法的工作方式:每经过一次便利,列表中最大的元素就会“冒泡”至正确位置。 冒泡排序包括:遍历一个列表,一次比较元素,以及交换不规则的相邻项。...) 快速排序 就像合并排序一样,快速排序算法采用分而治之的原理将输入数组分为两个列表,第一个包含小项目,第二个包含大项目。然后,该算法将对两个列表进行递归排序,直到对结果列表进行完全排序为止。...划分输入列表称为对列表进行分区。Quicksort首先选择一个枢轴元素,然后将列表围绕该枢轴进行分区,将每个较小的元素放入一个低数组,将每个较大的元素放入一个高数组。...将每个元素从低位列表放置到数据透视表的左侧,将每个元素从高位列表放置在数据透视表的右侧,将其精确定位在最终排序列表中需要的位置。...Timsort的主要特征是它利用了大多数现实数据集中存在的已排序元素。这些称为自然运行。然后,该算法会遍历列表,将元素收集到运行中,然后将它们合并到一个排序的列表中。

    49931

    算法导论中的四种基本排序

    最大堆的定义:在最大堆中,最大堆特性是指除了根以外的每个结点i,有A[PARENT(i)] >= A[i]。这样,堆的最大元素就存放在根结点中。...原址排序的定义:在排序输入数组时,只有常数个元素被存放到数组以外的空间中去。就是说不需要花数组那样大的空间来缓存数据,大部分排序都在数组内部进行!...步骤为: 从数组中挑出一個元素,称为 "基准"(pivot), 重新排序数组,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。...在这个分割之后,该基准是它的最后位置。这个称之为分割(partition)操作。 递归地(recursive)把小于基准值元素的子数组和大于基准值元素的子数组排序。  如下图所示 ?...实际应用中,快排用的较多,它一般快于堆排序。

    57320

    二路归并排序算法

    二路归并排序算法简单理解就是两两进行比较,然后把他们合并到一起。 通俗理解就是去买衣服的时候,经常会货比三家,看了一个店选两件衣服,然后又去另外一个店选了同款的两件衣服。...二路归并排序关键点: 相邻的两两进行比较,然后把他们合并在一起。相邻的两两最开始是单个元素,合并之后就会翻倍。 二路归并排序的过程,需要先拆分元素,然后再合并。...二路归并排序是不稳定的排序,时间复杂度o(n^2), 空间复杂度o(n) 举一个例子看一下二路归并排序的过程: 以数组 5,3,2,1 为例子 先拆分数组, 分成两组,5,3 和 2,1 继续拆分,两组变成四组..., 5,3,2,1各自都是一组 两两进行合并,合并成两组, 3,5和1,2 再两两合并,合并成一组, 1,2,3,5 看一下用python是如何实现的 def merge_list(elements,..., low, mid) merge_sort(elements, mid + 1, high) merge_list(elements, low, mid, high)

    83420

    分治算法之归并排序

    分治算法: 将一个规模为N的问题分解为K个规模较小的子问题,这些子问题互相独立且与原问题性质相同。求出子问题的解后进行合并,就可得到原问题的解。...一般步骤: 1.分解,将要解决的问题划分成若干规模较小的同类问题; 2.求解,当子问题划分得足够小时,用较简单的方法解决; 3.合并,安原问题的要求,将子问题的解逐层合并构成原问题的解。 ?...归并排序复杂度分析 设有n个元素,n个元素归并排序的时 间T(n) 总时间 = 分解时间 + 解决子问题时间 + 合并时间 分解时间: 即对原问题拆解为两个子问 题的时间 复杂度O(n) 解决子问题时间...: 即解决两个子问题 的时间 2T(n/2) 合并时间: 即对两个已排序数组归并 的时间 复杂度O(n) T(n) = 2T(n/2) + 2O(n) = 2T(n/2) + O(n) = O...+n*1) = O(nlogn) 详细推导可以参看算法导论 ?

    33010
    领券