算法

一.时间复杂度

#在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。
    时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。
     
#时间复杂度是用来估计算法运行时间的一个式子(单位)
 
#如何一眼判断时间复杂度?
    - 循环减半的过程->O(logn)
    - 几次循环就是n的几次方的复杂度

#时间复杂度
 
    - 最优时间复杂度
    - 最坏时间复杂度
    - 平均时间复杂度
 
#时间复杂度的几条计算规则
 
    - 基本操作 即只有常数项,认为其时间复杂度为O(1)
    - 顺序结构 时间复杂度按加法进行计算
    - 循环结构 时间复杂度按乘法进行计算
    - 分支结构 时间复杂度取最大值
    - 判断一个算法的效率时, 往往只需要关注操作数量的最高次项, 其它次要项和常数项可以忽略
    - 在没有特殊说明时,我们分析的算法的时间复杂度都是指最坏时间复杂度

 a.测试

def t1():
    li = []
    for i in range(10000):
        li.append(i)

def t2():
    li = []
    for i in range(10000):
        li.insert(0, i)


timer1 = Timer("t1()", "from __main__ import t1")
print("append", timer6.timeit(1000))

timer2 = Timer("t2()", "from __main__ import t2")
print("insert(0)", timer2.timeit(1000))

####################
append    1.1599015080137178
insert(0) 23.26370093098376

b.二分法

import random

n = 10000
li = list(range(n))



def bin_search(li,val):
    low = 0
    high = len(li) - 1
    while low <= high:
        mid = (low + high) // 2
        if li[mid] == val:
            return mid
        elif li[mid] < val:
            low = mid + 1
        else:
            high = mid - 1
    return None


obj = bin_search(li,5550)
print(obj)

c.排序

#排序low B二人组
 
    - 冒泡排序　　　　　　　　比较相邻的元素。如果第一个比第二个大，就交换他们两个。依次进行排序。
    - 选择排序　　　　　　　　一趟遍历记录最小的数，放到第一个位置。再一趟遍历剩余

    - 插入排序　　　　　　　　摸牌插入，将牌从无序区放到手中有序区，最开始手中有序区只有一张，后面抽牌放入手中有序区。
 
#排序NB三人组
　　 - 快速排序   取第一个位置的数，剩下列表中左右元素分别与取出的数比较，如果数比取出的数小，则放到列表的左边；如果数比取出的大，则放在列表右边
    - 堆排序
    - 归并排序
 
#么人用的排序
    - 基数排序
    - 希尔排序
    - 桶排序

#冒泡排序
    - 列表每相邻的数,如果前边的比后边的大,那么交换这两个数
    - 算法复杂度 n^2


import random

def bubble_sort(li):
    for i in range(len(li) - 1):                # i 趟
        for j in range(len(li) - i -1):         # j 指针
            if li[j] > li[j+1]:
                li[j],li[j+1] = li[j+1],li[j]
    return li

li = list(range(10))
random.shuffle(li)
obj = bubble_sort(li)
print(obj)

# 选择排序
    - 一趟遍历记录最小的数,放到第一个位置;再一趟遍历记录剩余列表中最小的数,继续放置...
    - 时间复杂度 O(n^2)


def select_sort(li):
    for i in range(len(li) - 1):    #i 趟
        min_loc = i
        # 找i+1位置到最后面位置内最小的数
        for j in range(i+1,len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
        # 和无序区第一个数作交换
        li[min_loc],li[i] = li[i],li[min_loc]
    return li

obj = select_sort([1,8,6,2,5,3])
print(obj)

#插入排序
    - 列表被分为有序区和无序区 最初有序区只有一个元素
    - 每次从无序区选择一个元素 插入到有序区的位置 直到无序区变空


#方式一:

def insert_sort(li):
    for i in range(1,len(li)):  # i 代表每次摸到牌的下标
        tmp = li[i]
        j = i-1   # j代表手里最后一张牌的下标
        while True:
            if j<0 or tmp>=li[j]:
                break
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp
    return li

obj = insert_sort([1,8,6,2,5,3])
print(obj)


#方式二:

def insert_sort(li):
    for i in range(1,len(li)):  # i 代表每次摸到牌的下标
        tmp = li[i]
        j = i-1   # j代表手里最后一张牌的下标
        while j>=0 and tmp<li[j]:
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp
    return li

obj = insert_sort([1,8,6,2,5,3])
print(obj)

def partition(data,left,right):

    tmp = data[left]
    while left < right:
        # right 左移动
        while left < right and data[right] >= tmp:   #如果low和high没有相遇且后面的数一直大于第一个数 就循环
            right -=1
        data[left] = data[right]
        # left 右移动
        while left < right and data[left] <= tmp:   #如果low和high没有相遇且后面的数一直大于第一个数 就循环
            left +=1
        data[right] = data[left]
    data[left] = tmp
    return left


def quick_sork(data,left,right):

    if left <right:
        mid = partition(data,left,right)
        quick_sork(data,left,mid-1)
        quick_sork(data,mid+1,right)
    return data


alist = [33,22,11,55,33,666,55,44,33,22,980]

obj = quick_sork(alist,0,len(alist)-1)
print(ob

def _sift(li, low, high):
    """

    :param li:
    :param low: 堆根节点的位置
    :param high: 堆最有一个节点的位置
    :return:
    """
    i = low  # 父亲的位置
    j = 2 * i + 1  # 孩子的位置
    tmp = li[low]  # 原省长
    while j <= high:
        if j + 1 <= high and li[j + 1] > li[j]:  # 如果右孩子存在并且右孩子更大
            j += 1
        if tmp < li[j]:  # 如果原省长比孩子小
            li[i] = li[j]  # 把孩子向上移动一层
            i = j
            j = 2 * i + 1
        else:
            li[i] = tmp  # 省长放到对应的位置上(干部)
            break
    else:
        li[i] = tmp  # 省长放到对应的位置上(村民/叶子节点)


def sift(li, low, high):
    """
    :param li:
    :param low: 堆根节点的位置
    :param high: 堆最有一个节点的位置
    :return:
    """
    i = low         # 父亲的位置
    j = 2 * i + 1   # 孩子的位置
    tmp = li[low]   # 原省长
    while j <= high:
        if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子存在并且右孩子更大
            j += 1
        if tmp < li[j]: # 如果原省长比孩子小
            li[i] = li[j]  # 把孩子向上移动一层
            i = j
            j = 2 * i + 1
        else:
            break
    li[i] = t

def partition(data,left,right):

    tmp = data[left]
    while left < right:
        #right 左移动
        while left < right and data[right] >= tmp:
            right -= 1
        data[left] = data[right]

        #left 右移动
        while left < right and data[left] <= tmp:
            left += 1
        data[right] = data[left]
    data[left] = tmp
    return left

def quick_sork(data,left,right):

    if left < right:
        mid = partition(data,left,right)
        quick_sork(data,left,mid-1)
        quick_sork(data,mid+1,right)
    return data

list = [33,22,11,55,33,666,55,44,33,22,980]
obj = quick_sork(list,0,len(list)-1)
print(obj)

#方式一
def insert_sort(li):
    for i in range(1,len(li)):
        tmp = li[i]
        j = i - 1
        while True:
            if j < 0 or tmp >= li[j]:
                break
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp
    return li

obj = insert_sort([1,8,6,2,5,3])
print(obj)



#方式二
def insert_sort(li):
    for i in range(1,len(li)):
        tmp = li[i]
        j = i - 1
        while j >= 0 and tmp < li[j]:
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp
    return li

obj = insert_sort([1,8,6,2,5,3])
print(obj)

import time


def cal_time(func):
    def wrapper(*args, **kwargs):
        t1 = time.time()
        result = func(*args, **kwargs)
        t2 = time.time()
        print("%s running time: %s secs." % (func.__name__, t2-t1))
        return result
    return wrapper

from timewrap import *
import random

def _sift(li, low, high):
    """
    :param li:
    :param low: 堆根节点的位置
    :param high: 堆最有一个节点的位置
    :return:
    """
    i = low  # 父亲的位置
    j = 2 * i + 1  # 孩子的位置
    tmp = li[low]  # 原省长
    while j <= high:
        if j + 1 <= high and li[j + 1] > li[j]:  # 如果右孩子存在并且右孩子更大
            j += 1
        if tmp < li[j]:  # 如果原省长比孩子小
            li[i] = li[j]  # 把孩子向上移动一层
            i = j
            j = 2 * i + 1
        else:
            li[i] = tmp  # 省长放到对应的位置上(干部)
            break
    else:
        li[i] = tmp  # 省长放到对应的位置上(村民/叶子节点)


def sift(li, low, high):
    """
    :param li:
    :param low: 堆根节点的位置
    :param high: 堆最有一个节点的位置
    :return:
    """
    i = low         # 父亲的位置
    j = 2 * i + 1   # 孩子的位置
    tmp = li[low]   # 原省长
    while j <= high:
        if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子存在并且右孩子更大
            j += 1
        if tmp < li[j]: # 如果原省长比孩子小
            li[i] = li[j]  # 把孩子向上移动一层
            i = j
            j = 2 * i + 1
        else:
            break
    li[i] = tmp


@cal_time
def heap_sort(li):
    n = len(li)
    # 1. 建堆
    for i in range(n//2-1, -1, -1):
        sift(li, i, n-1)
    # 2. 挨个出数
    for j in range(n-1, -1, -1):    # j表示堆最后一个元素的位置
        li[0], li[j] = li[j], li[0]
        # 堆的大小少了一个元素 （j-1）
        sift(li, 0, j-1)


li = list(range(10000))
random.shuffle(li)
heap_sort(li)
print(li)

import random
from timewrap import *
import copy
import sys


def merge(li, low, mid, high):
    i = low
    j = mid + 1
    ltmp = []
    while i <= mid and j <= high:
        if li[i] < li[j]:
            ltmp.append(li[i])
            i += 1
        else:
            ltmp.append(li[j])
            j += 1
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high+1] = ltmp


def _merge_sort(li, low, high):
    if low < high:  # 至少两个元素
        mid = (low + high) // 2
        _merge_sort(li, low, mid)
        _merge_sort(li, mid+1, high)
        merge(li, low, mid, high)
        print(li[low:high+1])


def merge_sort(li):
    return _merge_sort(li, 0, len(li)-1)


li = list(range(16))
random.shuffle(li)
print(li)
merge_sort(li)

print(li)

NB三人组小结

三种排序算法的时间复杂度都是  O(nlogn)

一般情况下，就运行时间而言：
快速排序 < 归并排序 < 堆排序

三种排序算法的缺点：
    快速排序：极端情况下排序效率低
    归并排序：需要额外的内存开销
    堆排序：在快的排序算法中相对较慢