算法:插入排序

插入排序的原理:
1.从第一个元素开始,该元素可以认为是已经被排序
2.取出下一个元素,在已经排序的元素序列中从后向前扫描
3.如果该元素(已排序)大于新元素,将该元素移动到下一个位置
4.重复步骤3,知道找到已排序的元素小于或等于新元素的位置
5.将新元素插入到该位置
6.重复步骤2-5

下面是实现代码:

require 'pry'
#插入排序
def insert_sort(arr)
    i,j = 1,0
    count = arr.length
    while i < count
        point = arr[i]
        j = i - 1
        while j >= 0 && arr[j] > point
            arr[j + 1] = arr[j]
            p arr
            j -= 1
        end
        arr[j + 1] = point
        p arr
        i += 1
    end

end

# binding.pry
insert_sort [66,13,51,76,81,26,57,69,23]

排序过程

[66, 66, 51, 76, 81, 26, 57, 69, 23]
[13, 66, 51, 76, 81, 26, 57, 69, 23]
[13, 66, 66, 76, 81, 26, 57, 69, 23]
[13, 51, 66, 76, 81, 26, 57, 69, 23]
[13, 51, 66, 76, 81, 26, 57, 69, 23]
[13, 51, 66, 76, 81, 26, 57, 69, 23]
[13, 51, 66, 76, 81, 81, 57, 69, 23]
[13, 51, 66, 76, 76, 81, 57, 69, 23]
[13, 51, 66, 66, 76, 81, 57, 69, 23]
[13, 51, 51, 66, 76, 81, 57, 69, 23]
[13, 26, 51, 66, 76, 81, 57, 69, 23]
[13, 26, 51, 66, 76, 81, 81, 69, 23]
[13, 26, 51, 66, 76, 76, 81, 69, 23]
[13, 26, 51, 66, 66, 76, 81, 69, 23]
[13, 26, 51, 57, 66, 76, 81, 69, 23]
[13, 26, 51, 57, 66, 76, 81, 81, 23]
[13, 26, 51, 57, 66, 76, 76, 81, 23]
[13, 26, 51, 57, 66, 69, 76, 81, 23]
[13, 26, 51, 57, 66, 69, 76, 81, 81]
[13, 26, 51, 57, 66, 69, 76, 76, 81]
[13, 26, 51, 57, 66, 69, 69, 76, 81]
[13, 26, 51, 57, 66, 66, 69, 76, 81]
[13, 26, 51, 57, 57, 66, 69, 76, 81]
[13, 26, 51, 51, 57, 66, 69, 76, 81]
[13, 26, 26, 51, 57, 66, 69, 76, 81]
[13, 23, 26, 51, 57, 66, 69, 76, 81]