排序算法Ruby Part1

1、Bubble sort 冒泡排序

  # Bubble sort 冒泡排序
  # 每次扫描，比较和交换相邻元素，保证一次扫描后，最大元素在最后一个
  # 每次扫描后，扫描队列长度减一
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  def bubble_sort(container)
    swap=true
    while(swap)
      swap=false
      for i in 0..(container.size-1) do
        for j in 0..i do
          if(container[i]<container[j])
            r=container[j]
            container[j]=container[i]
            container[i]=r
            swap=true
          end
        end
      end
    end

    return container
  end

2、Selection sort 选择排序

  # Selection sort 选择排序
  # 从头扫描到尾，每次将最小元素放到第一个
  # 每次扫描后，队列长度减一
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  def selection_sort(container)
    for i in 0..container.size-1 do
      min = i
      for j in i..container.size-1 do
        if(container[min]>container[j])
          min=j
        end
      end

      r=container[i]
      container[i]=container[min]
      container[min]=r

    end

    return container

  end

3、Insertion sort 插入排序

  # Insertion sort 插入排序
  # 起始队列长度为1，每次向队列增加1个数字
  # 通过元素移动，将队列调整为有序状态
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  def insertion_sort(container)
    if container.size <2
      return container
    end

    for i in 1..container.size-1 do
      val = container[i]
      j=i-1
      while(j>=0 and container[j]>val) do
        container[j+1]=container[j]
        j=j-1
      end

      container[j+1] = val
    end

    return container
  end

4、Shell Sort 希尔排序

  # Shell Sort 希尔排序
  # 指定一个步长，将需要排序的数字，按序号%步长分组
  # 对每组进行插入排序，然后减小步长，再次分组，排序
  # 直到步长为1结束
  # Time Complexity: О(n^2)
  # Space Complexity: О(n) total, O(1) auxiliary
  # Stable: Yes
  def shell_sort(container)
    step = container.size/2
    while step>0 do
      for i in step..container.size-1 do
        val= container[i]
        j=i-step
        while(j>=0 and container[j]>val) do
          container[j+step] = container[j]
          j=j-step
        end
        container[j+step]=val
      end

      #puts(">>")
      #puts(container)

      step = step/2
    end

    return container
  end

5、Merge sort 归并排序

  # Merge sort 归并排序
  # 二路归并首先将归并长度定为2，在归并集内进行排序
  # 然后归并长度×2，将有序集合进行归并
  # Time Complexity: О(nlogn) average and worst-case
  # Space Complexity: О(n) auxiliary
  # Stable: Yes
  def mergesort(container)
    return container if container.size <= 1

    mid = container.size / 2
    left = container[0...mid]
    right = container[mid...container.size]

    merge(mergesort(left), mergesort(right))
  end

  private

  def merge(left, right)
    sorted = []
    until left.empty? or right.empty?
      left.first <= right.first ? sorted << left.shift : sorted << right.shift
    end
    sorted + left + right
  end