排序算法(javascript版与ruby版)

排序算法(javascript版与ruby版)


合并排序
javascript版本：

function merge(left, right){
  var result = [];
  while (left.length > 0 && right.length > 0){
    if (left[0] < right[0]){
      result.push(left.shift());//把最小的最先取出，放到结果集中
    } else {
      result.push(right.shift());
    }
  } return result.concat(left).concat(right);//剩下的就是合并，这样就排好序了
}
function mergeSort(array){
  if (array.length == 1) {
    return array;
  }
  var middle = Math.floor(array.length / 2),//求出中点
  left = array.slice(0, middle),//分割数组
  right = array.slice(middle);
  return merge(mergeSort(left), mergeSort(right));//递归合并与排序
}

ruby版本：

def merge(left, right)
  final = []
  until left.empty? or right.empty?
    final << ( left.first < right.first ? left.shift : right.shift )
  end
  final + left + right
end
def mergeSort(array)
  return array if array.size < 2
  left = array.first(array.size/2)
  right = array.last(array.size - array.size/2)
  merge(mergeSort(left), mergeSort(right))
end

快速排序
javascript版

function quicksort(arr)
{
    if (arr.length == 0)
        return [];
 
    var left = new Array();
    var right = new Array();
    var pivot = arr[0];
 
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
           left.push(arr[i]);
        } else {
           right.push(arr[i]);
        }
    }
 
    return quicksort(left).concat(pivot, quicksort(right));
}

ruby版

def quicksort(v)
   return v if v.nil? or v.length <= 1
   less, more = v[1..-1].partition { |i| i < v[0] }
   quicksort(less) + [v[0]] + quicksort(more)
end