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 =

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

算法原理: 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 实现 假设有这样一个数组: [4, 1, 3, 2] 冒泡排序为从第一个数开始,吧这个数与后面的数比较,如果这个数比后面的大,就交换他们的位置. 比如,第一次比较4和1,发现4比1大,交换 -> [1, 4, 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

算法课的作业,利用分治法,合并排序. #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

基础 将一个记录插入到一个已经排序好的表中,以得到一个记录增一的有序表.并且最关键的一点就是它把比当前元素大的记录都往后移动,用以空出"自己"该插入的位置.当n-1趟插入完成后该记录就是有序序列. def insertSort(tarray) i=1 while(i < tarray.size) do if tarray[i] < tarray[i-1] j=i-1 x=tarray[i] #puts x.class #puts tarray[i].class tarray

复制代码 代码如下: def quick_sort(a) return a if a.size < 2 (x = a.pop) ?  quick_sort(a.select{|i| i <=x }) + [x] + quick_sort(a.select{|i| i > x}) : [] end array = [72,6,57,88,60,42,83,73,42,48,85] p quick_sort(array)    #=> [6, 42, 42, 48, 57, 60, 7

今天将单独为大家介绍一下快速排序! 一.算法介绍 排序算法(Sorting algorithm)是计算机科学最古老.最基本的课题之一.要想成为合格的程序员,就必须理解和掌握各种排序算法.其中"快速排序"(Quicksort)使用得最广泛,速度也较快.它是图灵奖得主C. A. R. Hoare(托尼·霍尔)于1960时提出来的. 二.算法原理 快排的实现方式多种多样,猪哥给大家写一种容易理解的:分治+迭代,只需要三步: 在数列之中,选择一个元素作为"基准"(pivot

先来看基本的方法: 复制代码 代码如下: chomp(@strings=<STDIN>);  @strings=sort @strings;  print "@strings\n."; 上面的三行代码解决的是输入,然后排序,最后将排序后的结果输出的作用. 只用一行代码即完成的写法: 复制代码 代码如下: print sort<STDIN>; 得到相同的结果,相当给力哦.

本文实例讲述了php一行代码获取文件后缀名的方法.分享给大家供大家参考.具体方法分析如下: php中一行代码获取文件后缀名的方法要结合很多的函数了,我们这个有点像asp中的函数了,下面来一起看看吧. 实例: 复制代码 代码如下: $filename  = 'D:/wamp/www/sparkphp/rar'; $rs =  strtolower(trim(substr(strrchr($filename, "."), 1))); 详解: strrchr()函数查找字符串在另一个字符串中