Module: CodeCook::Sort::MergeSort

Defined in:
手写代码必备手册(Ruby版).rb

Overview

7.4 归并排序

Class Method Summary (collapse)

Class Method Details

+ (Array) merge_array(left, right)

归并两个有序数组

Parameters:

  • left (Array) —

    左侧有序数组

  • right (Array) —

    右侧有序数组

Returns:

  • (Array) —

    合并后的有序数组



404
405
406
407
408
409
410
 
# File '手写代码必备手册(Ruby版).rb', line 404

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

+ (Array) merge_sort(array = [])

归并排序 wiki

Parameters:

  • array (Array) (defaults to: []) —

    需要排序的数组

Returns:

  • (Array) —

    经过排序之后的数组



417
418
419
420
421
422
423
424
425
426
 
# File '手写代码必备手册(Ruby版).rb', line 417

def merge_sort(array=[])
    if array.size > 1
        mid = array.size/2
        left = array.slice(0, mid)
        right = array.slice(mid, array.size)
        merge_array(merge_sort(left), merge_sort(right))
    else
        array
    end
end