问题描述

对一个数组进行排序

解法

背景知识是,如果让我们两个单调不递减的数组合并起来,然后保证合并后的数据是单调不递减的,这是一件比较容易的事情,可以想象成两个队比身高,身高低的算输(打我呀), 然后两个队都是从低到高派出选手,低的那个出局,站在旁边,我们称之为失败序列,这个时候输的那一队会派出第二个, 输掉的就去失败序列, 依次类推,当一方队伍耗尽的时候,另外一方也依序进入失败队列,最后失败队列就是一个单调不递减的序列,我们就完成了排序, 这个方法我称之为 merge

所以我们就想,如果可以构造两个有序队列就好了。

于是把一个数组分成两两半, 然后分别对他们排序,怎么排序呢,再把他分成两半,一直到就剩下两个元素,直接比较就可了,然后在一层一层的 merge 回来,最后就是结果了

SMTC(show me the code)

def merge_sort(arr)
  return arr if arr.length <= 1
  if arr.length == 2
    if arr[0] > arr[1]
      [arr[1], arr[0]]
    else arr
    end
  else
    midlle = arr.length / 2
    merge merge_sort(arr[0..midlle]), merge_sort(arr[(midlle + 1)..(arr.length)])
  end
end

def merge(first, second)
  result = []
  a, b = first, second
  while true
    if a.length == 0 and b.length == 0
      break
    elsif a.length == 0
      result.push(b.shift())
    elsif b.length == 0
      result.push(a.shift())
    elsif a[0] > b[0]
      result.push(b.shift())
    else
      result.push(a.shift())
    end
  end
  result
end