16.python算法基础

1. 算法定义

算法（Algorithm）是指解决问题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

1.1 一个好的算法应该具有以下七个重要的特征：

• 1. 有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
• 2. 确切性(Definiteness)：算法的每一步骤必须有确切的定义；
• 3. 输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身指定了初始条件；
• 4. 输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果，没有输出的算法是毫无意义的；
• 5. 可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）；
• 6. 高效性(High efficiency)：执行速度快，占用资源少；
• 7. 健壮性(Robustness)：对数据响应正确。

---

2. 时间复杂度

计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间,时间复杂度常用大O符号（大O符号（Big O notation）是用于描述函数渐进行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，它在分析算法复杂性的方面非常有用。）表述，使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。

大O，简而言之可以认为它的含义是“order of”（大约是）。
无穷大渐近
大O符号在分析算法效率的时候非常有用。举个例子，解决一个规模为 n 的问题所花费的时间（或者所需步骤的数目）可以被求得：T(n) = 4n^2 - 2n + 2。当 n 增大时，n^2; 项将开始占主导地位，而其他各项可以被忽略——举例说明：当 n = 500，4n^2; 项是 2n 项的1000倍大，因此在大多数场合下，省略后者对表达式的值的影响将是可以忽略不计的。
数学表示扫盲贴 http://www.cnblogs.com/alex3714/articles/5910253.html

---

3. 常见排序算法

image.png

3.1 冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

data_set = [ 9,1,22,31,45,3,6,2,11 ]
 
loop_count = 0
for j in range(len(data_set)):
    """
    # -1 是因为每次比对的都 是i 与i +1,不减1的话,最后一次对比会超出
    list 获取范围,-j是因为,每一次大loop就代表排序好了一个最大值,放在了列表最后面,
    下次loop就不用再运算已经排序好了的值 了
    """
    for i in range(len(data_set) - j- 1): 
        if data_set[i] > data_set[i+1]: #switch
            tmp = data_set[i]
            data_set[i] = data_set[i+1]
            data_set[i+1] = tmp
        loop_count +=1
    print(data_set)
print(data_set)
print("loop times", loop_count)

3.2 选择排序

选择排序比较好理解，好像是在一堆大小不一的球中进行选择（以从小到大，先选最小球为例）：
　　1. 选择一个基准球
　　2. 将基准球和余下的球进行一一比较，如果比基准球小，则进行交换
　　3. 第一轮过后获得最小的球
　　4. 在挑一个基准球，执行相同的动作得到次小的球
　　5. 继续执行4，直到排序好
时间复杂度：O(n^2). 需要进行的比较次数为第一轮 n-1，n-2....1, 总的比较次数为 n*(n-1)/2

def selectedSort(myList):
    #获取list的长度
    length = len(myList)
    #一共进行多少轮比较
    for i in range(0,length-1):
        #默认设置最小值得index为当前值
        smallest = i
        #用当先最小index的值分别与后面的值进行比较,以便获取最小index
        for j in range(i+1,length):
            #如果找到比当前值小的index,则进行两值交换
            if myList[j]<myList[smallest]:
                tmp = myList[j]
                myList[j] = myList[smallest]
                myList[smallest]=tmp
        #打印每一轮比较好的列表
        print("Round ",i,": ",myList)
myList = [1,4,5,0,6]
print("Selected Sort: ")
selectedSort(myList)

3.3 插入排序(Insertion Sort)

插入排序(Insertion Sort)的基本思想是：将列表分为2部分，左边为排序好的部分，右边为未排序的部分，循环整个列表，每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
插入排序非常类似于整扑克牌：
在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。
也许你没有意识到，但其实你的思考过程是这样的：现在抓到一张7，把它和手里的牌从右到左依次比较，7比10小，应该再往左插，7比5大，好，就插这里。为什么比较了10和5就可以确定7的位置？为什么不用再比较左边的4和2呢？因为这里有一个重要的前提：手里的牌已经是排好序的。现在我插了7之后，手里的牌仍然是排好序的，下次再抓到的牌还可以用这个方法插入。编程对一个数组进行插入排序也是同样道理，但和插入扑克牌有一点不同，不可能在两个相邻的存储单元之间再插入一个单元，因此要将插入点之后的数据依次往后移动一个单元。

source = [92, 77, 67, 8, 6, 84, 55, 85, 43, 67]
for index in range(1,len(source)):
    current_val = source[index] #先记下来每次大循环走到的第几个元素的值
    position = index
    """
    #当前元素的左边的紧靠的元素比它大,要把左边的元素一个一个的右  移一位,
  给当前这个值插入到左边挪一个位置出来
    """
    while position > 0 and source[position-1] > current_val: 
        source[position] = source[position-1] #把左边的一个元素往右移一位
        #只一次左移只能把当前元素一个位置 ,还得继续左移只到此元素放到排序好的列表的适当位置 为止
        position -= 1 
     #已经找到了左边排序好的列表里不小于current_val的元素的位置,把current_val放在这里
    source[position] = current_val
    print(source)

3.4 快速排序（quick sort）

快排的思想：首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。
一趟快速排序的算法是：

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

def QuickSort(myList,start,end):
    #判断low是否小于high,如果为false,直接返回
    if start < end:
        i,j = start,end
        #设置基准数
        base = myList[i]

        while i < j:
            #如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现
            while (i < j) and (myList[j] >= base):
                j = j - 1

            #如找到,则把第j个元素赋值给第个元素i,此时表中i,j个元素相等
            myList[i] = myList[j]

            #同样的方式比较前半区
            while (i < j) and (myList[i] <= base):
                i = i + 1
            myList[j] = myList[i]
        #做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回base
        myList[i] = base

        #递归前后半区
        QuickSort(myList, start, i - 1)
        QuickSort(myList, j + 1, end)
    return myList


myList = [49,38,65,97,76,13,27,49]
print("Quick Sort: ")
QuickSort(myList,0,len(myList)-1)
print(myList)