1.循环不变式

Fig1.png

但循环不变式和数学归纳法是有区别的，区别在于终止。

2.插入排序

插入排序
def insertionSort(a:list):
    for i in range(1,len(a)):
        value = a[i]
        insert_index = -1

        for j in range(i-1,-1,-1):
            if  value< a[j]:
                a[j+1] = a[j]
                insert_index = j
            else:
                break
        if insert_index !=-1:
            a[insert_index] = value
    
    return a

# -*- coding: utf-8 -*-
# @Time : 2020/11/17 21:21
# @File : insert_sort.py
# @Author: LZP
# 插入排序


def insertionSort(a):
    for i in range(1, len(a)):
        # value是待排序元素
        value = a[i]
        insert_index = -1
        for j in range(i-1, -1, -1):
            if value < a[j]:
                # 如果待排序元素小于已排序元素j，那么已排序元素j就要后移一位
                # 表现则是已排序元素j的索引加1
                # 待排序元素的索引变成j
                # 待排序元素和所有已排序元素比较完一轮后，已排序元素索引该增加的都增加了
                # 同时得到一个最终的插入索引j
                a[j+1] = a[j]
                insert_index = j
            else:
                break
        if insert_index != -1:
            # 把待排序元素赋值到最新得到的插入索引
            a[insert_index] = value
    return a


a = [4, 5, 6, 1, 3, 2]
print(insertionSort(a))

Fig2.png

Fig3.png

Fig4.png

Fig5.png

练习2.1-2（降序）
for i in range(len(a)):
    key = a[i]
    insert_index = -1
    for j in range(i-1,-1,-1):
        if key > a[j]:
            a[j+1]=a[j]
            insert_index = j
        else:
            break
    if insert_index != -1:
        a[insert_index] = key
print(a)

练习2.1-3
v = 5
a = [1,2,3,4,5,6,7,8,9,10]
for i in range(len(a)):
    if v == a[i]:
        print(i)
    else:
        continue
在这里最后else后面我用了break，会直接跳出循环不再运行

练习2.1-4

Fig6.png

Fig7.png

3.归并排序

一.原理：
1.将一个序列从中间位置分成两个序列；
2.在将这两个子序列按照第一步继续二分下去；
3.直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。

Fig8

Fig9

def merge(a, b):
    c = []
    h = j = 0
    while j < len(a) and h < len(b):
        if a[j] < b[h]:
            c.append(a[j])
            j += 1
        else:
            c.append(b[h])
            h += 1
    if j == len(a):
        for i in b[h:]:
            c.append(i)
    else:
        for i in a[j:]:
            c.append(i)
    return c

def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    middle = len(lists)//2
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
    return merge(left, right)

if __name__ == '__main__':
    a = [14, 2, 34, 43, 21, 19]
    print (merge_sort(a))

*归并排序*
最优时间复杂度：O(nlongn)
最坏时间复杂度 ：O(nlongn)
稳定性：稳定

Fig10

Fig11.png

import random

def ConfiationAlgorithm(str):
    if len(str) <= 1: #子序列
        return str
    mid = (len(str) / 2)
    left = ConfiationAlgorithm(str[:mid])#递归的切片操作
    right = ConfiationAlgorithm(str[mid:len(str)]) 
    result = []
    #i,j = 0,0

    while len(left) > 0 and len(right) > 0:
        if (left[0] <= right[0]):
            #result.append(left[0])
            result.append(left.pop(0))
            #i+= 1
        else:
            #result.append(right[0])
            result.append(right.pop(0))
            #j+= 1

    if (len(left) > 0):
        result.extend(ConfiationAlgorithm(left))
    else:
        result.extend(ConfiationAlgorithm(right))
    return result   
if __name__ == '__main__':
    a = [20,30,64,16,8,0,99,24,75,100,69]
    print ConfiationAlgorithm(a)
    b = [random.randint(1,1000) for i in range(10)]
    print ConfiationAlgorithm(b)

第一个部分切片操作，
第二个部分比较操作，
第三个操作针对子序列多出来的数将追加到合并序列中。
但是一开始在第二部分比较的时候犯了很严重的错误就是一开始的时候条件没有写明白，导致我在循环体重填充代码的时候出现了各种各样的错误，这种情况下只能断点中断来排查。
注释的语句段就是我直接对切片的子序列做操作，然后没有弹出比较完的数，导致第一遍循环直接死循环然后报错。其实设i,j来比较子序列的数可以不可以，答案当然是可以的，当时问题就在于我这是一个方法。
要按照注释里面来写的话其实我的循环条件是有问题的。在代码片中首先用left来切片包含两个元素的子序列出来然后left,right最初都只有一个数通过比较之后完成了子序列的有序性。
然后我觉得非常有意思的就是两个return的作用。