排序算法(一)---快速插入排序

因为对算法这一项实在是弱爆了，对自己从零开始学习，慢慢记录过程，加油哦
再因为最近在学习python和lua，就分别用两种语言都实现了

快速插入排序

基本思想：（假设是：从小到大，升序）
每次选择一个元素K插入已排好序的L[1...i]部分，如果L[x]>K，则K插入到L[x]前面，
要对L[x]后面的元素进行后移

时间复杂度：
最好情况：正序有序（从小到大）只需比较n次，不需要移动，复杂度O(n)
最坏情况：逆序有序（从大到小），插入第2个元素需要考察前1个元素，插入第3个元素需要考察前2个元素...插入第n个元素需要考察前n-1个元素，等差数列求和得n^2/2,
所以，复杂度为O(n^2)

稳定性：
稳定性，就是有两个相同的元素，排序先后的相对位置是否变化，
插入排序中，K如果和L[x]相等，直接插入L[x]后面，这样不用后移元素，所以插入排序是稳定的排序

代码示例1：python代码:quick_insert_sort.py

def quick_insert_sort(l):
    for i in range(1, len(l)):  #python数组下标是从0开始的
        tmp = l[i]
        j = i - 1
        while(j >= 0 and tmp < l[j]): #进行元素后移操作
            l[j+1] = l[j]
            j -= 1
        l[j+1] = tmp                  #将待插入元素放到j+1位置
    print('result:' + str(l))

if __name__ == '__main__':
    quick_insert_sort([74,62,97,88,8,75,49,16,9]) 

代码示例2：lua代码quick_insert_sort.lua

function quick_insert_sort(t)
    len = table.getn(t)
    for i=2,len do                 --lua table下标是1开始的
        tmp = t[i]
        j = i - 1
        while(j > 0 and tmp < t[j]) do --元素后移
            t[j+1] = t[j]
            j = j - 1
        end
    end
end

t = {65,71,21,13,84,49,106,56,98}
quick_insert_sort(t)
for _,v in ipairs(t) do
    print(v)
end