数据结构-Python实现「插入类排序」

释放双眼,带上耳机,听听看~!

运行环境:python 2.7.12
学习课程来源:算法与数据结构C++精解


插入类排序

在一个已经有序的序列中,插入一个新的记录。
例子A:好比军训排队,已经排好了一个纵队。这时,有人要临时加入到这个队伍里来,于是教官大声喊道:“新来的,迅速找到你的位置,入队!”。于是,新来的从前向后走去,直到发现身高刚好的位置,就插入这个队伍了。
例子B:玩扑克牌。抽牌是一张张插入到原先有序的牌列中,直到抽牌结束

分类:

  • 1.直接插入排序
  • 2.折半插入排序
  • 3.希尔排序

1. 直接插入排序

def insertion_sort(arr, n):
    for i in xrange(n):
        # j选取[i,0)的范围,从i开始到1截止。
        # 如果arr[j]比arr[j-1]小则互换,依次往复,直到arr[1]与arr[1-1]比较为止。
        for j in xrange(i, 0, -1):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
            else:
                break
    return arr

改进后的插入排序

def insertion_sort_advance(arr, n):
    for i in xrange(1, n):
        e = arr[i]
        for j in xrange(i, 0, -1):
            if arr[j-1] < e:
                break
            arr[j] = arr[j-1]
        else:
            j = 0
        arr[j] = e
    return arr

2.折半插入排序

def binary_insertion_sort(arr, n):
    for i in xrange(1, n):
        l, r, t = 0, i - 1, arr[i]
        while l <= r:
            m = (l + r) / 2
            if t < arr[m]:
                r = m - 1
            else:
                l = m + 1

        for j in xrange(i - 1, l - 1, -1):
            arr[j + 1] = arr[j]

        arr[l] = t
    return arr

3.希尔排序

希尔排序的增量取法:1.增量序列中的值没有除1以外的公因子(例8、4、2、1就不要取);2.增量序列最后一个值是1。

继续修改和添加:
1.为什么要修改。
2.改进前后的性能对比
n=10,100,…10^5级别

补充

生成测试用例

python可以用random模块的shuffle方法,对原来列表进行随机洗牌,但是此随机的程度无法控制。
10位级别的[0,1,3,2,4,5,6,7,8,9]与[9,0,5,2,4,7,1,3,6,8],这2组的随机分布程度是不一样的,且算法甚至要研究百万位级以上的随机分布序列。

from random import shuffle,randint
#生成随机的方法1:(可以控制范围和数量)
arr1  = [randint(-100, 100) for _ in xrange(100)]
#生成随机的方法2:
arr2 = range(100)
shuffle(arr2)

len_arr = len(arr1)

算法性能测试

顺序、逆序、乱序等对于同一种算法的性能,可能会相差一个平方级,即O(n)与O(n^2)。

如何生成可控随机程度的测试用例,和算法的性能测试,具体可参考顶部「学习课程来源」

【转自慕课】https://www.imooc.com

Python

python配置文件练习操作

2022-3-3 17:40:19

Python

学习python的基础语法集合

2022-3-3 17:50:34

搜索