基本排序算法ruby实现

1.时间复杂度O(N**2)，空间复杂度O(1)

冒泡排序

冒泡排序的基本思想就是最大的元素像气泡一样往上冒，所以从头遍历，把最大的放最后。

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+1] < a[j] 
      end 
   end
  return a
end

选择排序

选择排序，顾名思义就是选择最小的元素放在最前面。

  def select_sort(a)
    (0..a.size-1).each do |i|
      min = a[i]
      k = i
     (i+1..a.size-1) do |j|
       if a[j] < min
         min = a[j]
         k = j ##记住最小元素的位置，便于交换。
       end   
     end
     a[k],a[i] = a[i],min
  end
  return a
end

插入排序

插入排序，就是从当前元素开始，所有元素往后移动一位，然后将当前元素插在第一个小于它的数后面，如果所有元素都比当前元素大，则将它插在首位。其关键因素就是找到当前元素的位置，然后插入，故命名为插入排序。

def insert_sort(a)
  a.each_with_index do  |e,i|
    j = i -1
    while j >= 0 do
      break if a[j] <= e
      a[j+1] = a[j]
      j     -= 1
    end
    a[j+1]  = e
  end
  return a
end

希尔排序

希尔排序：希尔排序是插入排序的一种改进排序。加入一个增量元素形成新的增量序列。

def shell_sort(a)
  gap = a.size / 2
  while( gap > 0) do
    (gap..a.size-1).each do |i|
      tmp = a[i]
      j = i -gap
      while j >= 0 do
        break if a[j] <= tmp
        a[j+gap]  = a[j]
        j = j -gap
      end
      a[j+gap] = tmp
    end
    gap  = gap / 2
  end
  return a
end

2.时间复杂度O(nlogn)

快速排序

快速排序的核心思想是分治，即分而治之。取出一个基准元素，将小于基准元素的元素放在它的左边，大于基准元素的的放在它的右边，然后递归下去，就能得到排序后的结果。用ruby实现及其简单优美。

def quick_sort(a)
   (x  = a.pop) ? quick_sort(a.select{|y| y <= x}) + [x] +  quick_sort(a.select{|z| z >= x }) : []
end

归并排序

归并排序的思想，简而言之，将数组一分为二，分别排序后合并。

def merge_sort(a)
  return a if a.size <= 1
  middle = a.size / 2
  left  = merge_sort(a[0,middle])
  right = merge_sort(a[middle,a.size-1])
  merge(left,right)
end

def merge(l,r)
  result = []
  while l.size > 0 && r.size > 0 do
    if l.first < r.first
      result << l.shift
    else
      result << r.shift
    end
  end
  if l.size  > 0
    result += l
  end
  if r.size > 0 
    result += r
  end
  result
end

Test

require 'test/unit'
class SortTest < Test::Unit::TestCase
  def setup
    @a = [3,2,7,4,9,1]
    @b = [9,4,10,16,7,3,2,8,19]
  end

  def test_bubble_sort
     assert_equal(bubble_sort(@a),[1,2,3,4,7,9])
     assert_equal(bubble_sort(@b,[2,3,4,7,8,9,10,16,19])
  end
  def test_select_sort
     assert_equal(select_sort(@a),[1,2,3,4,7,9])
     assert_equal(select_sort(@b,[2,3,4,7,8,9,10,16,19])
  end
  def test_insert_sort   
    assert_equal(insert_sort(@a),[1,2,3,4,7,9])
    assert_equal(insert_sort(@b,[2,3,4,7,8,9,10,16,19])
  end
  def test_shell_sort   
    assert_equal(shell_sort(@a),[1,2,3,4,7,9])
    assert_equal(shell_sort(@b,[2,3,4,7,8,9,10,16,19])
  end
  def test_merge_sort
    assert_equal(merge_sort(@a),[1,2,3,4,7,9])
    assert_equal(merge_sort(@b,[2,3,4,7,8,9,10,16,19])
  end
  def test_quick_sort   
    assert_equal(quick_sort(@a),[1,2,3,4,7,9])
    assert_equal(quick_sort(@b,[2,3,4,7,8,9,10,16,19])
  end
end