不学不知道的数据结构算法之----冒泡排序+选择排序

@TOC

冒泡排序知识

无序表初始数据项的排列状况对冒泡排序没有影响
算法过程总需要经过n-1趟，随着趟数的增加，，对比次数逐步从n-1减少到1，并包括可能发生的数据项交换。
对比次数是1~n-1的累加：
1/2n的平方-1/2n
对比时间复杂度是O(n的平方)

对于每次交换而言时间复杂度也是O（n的平方），通常每次交换包括三次赋值。
最好的情况是0次，最坏是每次都交换。
冒泡排序作为时间效率最差的排序算法，来作为其它算法的对比基准。
有一点优势：无需任何额外的存储空间开销。

冒泡排序代码

def maopao(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                temp = alist[i]
                alist[i]=alist[i+1]
                alist[i+1]=temp
    return alist
alist=[5,8,99,56,2,8,7]
print(maopao(alist))
# maopao(alist)
# print(alist)

选择排序

选择排序对冒泡排序进行了改进，保留了其基本多趟对比思路，每趟都是当前最大项就位。
但选择排序对交换进行了削减，相比起冒泡排序进行多次交换，每趟仅进行1次交换，记录最大项所在的位置，最后再跟本趟最后一项进项交换，
选择排序的时间复杂度比冒泡排序稍优：
对比次数不变，还是O（n的平方）
交换次数则减少为O（n）

选择排序代码

def xuanze(alist):
    for fillslot in range(len(alist)-1,0,-1):
        Max=0
        for i in range(1,fillslot+1):
            if alist[i]>alist[Max]:
                Max=i
        temp=alist[fillslot]
        alist[fillslot]=alist[Max]
        alist[Max]=temp
alist=[5,8,99,56,2,8,7]
xuanze(alist)
print(alist)

不学不知道的数据结构算法之----递归

@TOC

什么是递归

递归：将问题分解为更小规模的问题
特征：在算法流程中调用本身
巧妙地利用递归方法可以将复杂问题优雅化。

初识递归：数列求和

给定一个列表，返回所有数的和：

def listsum(numlist):
    theSum=0
    for i in numlist:
        theSum=theSum+i
    return theSum
print(listsum([1,3,5,7,9]))

这是最简单最普遍的一种方法，大家想一下，如果不用for或者while这种循环结构，只用递归结构，能不能解决呢？答案是能！

递归可以简单的说成就是：数列的和=‘首个数’ + ‘余下数列’ 的和
so：

def listsum(numlist):
    if len(numlist)==1:
        return numlist[0]
    else:
        return numlist[0]+listsum(numlist[1:])
print(listsum([1,3,5,7,9]))

要素：将其分解为最小规模，表现为调用自身

递归三定律

1.必须有一个基本结束条件
2.必须改变状态向基本结束条件演进，减小问题规模
3.递归算法必须调用本身

注意：递归的真谛就是将问题分解为规模更小的相同问题！