`

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

阅读更多
因为对算法这一项实在是弱爆了,对自己从零开始学习,慢慢记录过程,加油哦
再因为最近在学习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
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics