Module: CodeCook::Sort

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

Overview

第七章 排序 wiki

Defined Under Namespace

Modules: MergeSort

Class Method Summary (collapse)

Class Method Details

+ (Array) bubble_sort(array)

7.2.1 冒泡排序 wiki

Parameters:

  • array (Array) —

    需要排序的数组

Returns:

  • (Array) —

    经过排序之后的数组



357
358
359
360
361
362
363
364
365
 
# File '手写代码必备手册(Ruby版).rb', line 357

def bubble_sort(array)
    return array if array.size <2
    (array.size - 2).downto(0) do |i|
        (0..i).each do |j|
            array[j],array[j+1]=array[j+1],array[j] if array[j]>=array[j+1]
        end
    end
    return array
end

+ (Array) quick_sort(array = [])

7.2.2 快速排序 wiki

Parameters:

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

    需要排序的数组

Returns:

  • (Array) —

    经过排序之后的数组



372
373
374
375
376
 
# File '手写代码必备手册(Ruby版).rb', line 372

def quick_sort(array=[])
      return array if array.size < 2
      left, right = array[1..-1].partition { |y| y <= array.first }
      sort(left) + [ array.first ] + sort(right)
end

+ (Array) shell_sort(array = [])

7.1.3 希尔排序 wiki

Parameters:

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

    需要排序的数组

Returns:

  • (Array) —

    经过排序之后的数组



325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
 
# File '手写代码必备手册(Ruby版).rb', line 325

def shell_sort(array=[])
    n = array.size

    gap = 0
    while (gap <= n)
        gap = gap * 3 + 1;
    end

    i = 0
    while gap > 0
        i = gap
        while i < n
            j = i - gap
            temp = array[i]
            while (j >= 0) and (array[j] > temp)
                array[j+gap] = array[j]
                j = j- gap
            end
            array[j + gap] = temp
            i += 1
        end
        gap = ( gap - 1 ) / 3
    end

    array
end

+ (Array) simple_selection_sort(array = [])

7.3.1 简单选择排序 wiki

Parameters:

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

    需要排序的数组

Returns:

  • (Array) —

    经过排序之后的数组



383
384
385
386
387
388
389
390
391
392
393
 
# File '手写代码必备手册(Ruby版).rb', line 383

def simple_selection_sort(array=[])
    n = array.size - 1
    (0..n).each do |i|
        min = i
        (i..n).each do |j|
            min = j if array[min] > array[j]
        end
        array[i], array[min] = array[min], array[i]
    end
    array
end

+ (Array) straight_insertion_sort(array = [])

7.1.1 直接插入排序 wiki

举个例子：

2.0.0-p247 :141 > a=[3,5,2,6,6,2,11,5,8,17]
=> [3, 5, 2, 6, 6, 2, 11, 5, 8, 17] 
2.0.0-p247 :142 > straight_insertion_sort a
[3, 5, 2, 6, 6, 2, 11, 5, 8, 17]
[2, 3, 5, 6, 6, 2, 11, 5, 8, 17]
[2, 3, 5, 6, 6, 2, 11, 5, 8, 17]
[2, 3, 5, 6, 6, 2, 11, 5, 8, 17]
[2, 2, 3, 5, 6, 6, 11, 5, 8, 17]
[2, 2, 3, 5, 6, 6, 11, 5, 8, 17]
[2, 2, 3, 5, 5, 6, 6, 11, 8, 17]
[2, 2, 3, 5, 5, 6, 6, 8, 11, 17]
[2, 2, 3, 5, 5, 6, 6, 8, 11, 17]
=> [2, 2, 3, 5, 5, 6, 6, 8, 11, 17]

Parameters:

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

    需要排序的数组

Returns:

  • (Array) —

    经过排序之后的数组



304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
 
# File '手写代码必备手册(Ruby版).rb', line 304

def straight_insertion_sort(array=[])
    i = 1
    while i < array.size
        tmp = array[i]
        j = i - 1
        while (tmp < array[j]) and (j >= 0)
            array[j + 1] = array[j]
            j -= 1
        end
        array[j + 1] = tmp
        i += 1
        p array
    end
    array
end