1、概念

一个计算过程，解决问题的方法

2、时间复杂度和空间复杂度

时间复杂度：用来表示算法的运行效率

》》》一般来说，时间复杂度高的算法比时间复杂度低的算法运行效率高，，但这不是绝对的

》》》常见的时间复杂度（按效率排序） O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)

》》》判断时间复杂度的方法：1）先要找到n；2）如果有循环减半的过程就是logn；3）几次循环就是n的几次方

空间复杂度：用来表示算法占用内存大小

3、列表查找

》》》顺序查找：从列表第一个元素开始，顺序进行搜索，直到找到为止

》》》二分法查找：从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。

二分查找：

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

递归的二分查找：

def bin_search_rec(data_set, value, low, high):        if low <= high:                mid = (low + high) // 2                if data_set[mid] == value:                        return mid                elif data_set[mid] > value:                        return bin_search_rec(data_set, value, low, mid - 1)                else:                        return bin_search_rec(data_set, value, mid + 1, high)       else:                return

 

 

 

 

4、列表排序

关键点：有序区，无序区

一、冒泡排序

1、思路：列表每两个相邻的数，如果前边的比后边的大，那么交换这两个数

2、代码：关键点趟和无序区

import randomfrom timewrap import *@cal_timedef bubble_sort(li):    for i in range(len(li) - 1):        # i 表示趟数        # 第 i 趟时： 无序区：(0，len(li) - i)        for j in range(0, len(li) - i - 1):            if li[j] > li[j+1]:                li[j], li[j+1] = li[j+1], li[j]#如果冒泡排序中执行一趟而没有交换，则列表已经是有序状态，可以直接结束算法@cal_timedef bubble_sort_2(li):    for i in range(len(li) - 1):        # i 表示趟数        # 第 i 趟时： 无序区：(0，len(li) - i)        change = False        for j in range(0, len(li) - i - 1):            if li[j] > li[j+1]:                li[j], li[j+1] = li[j+1], li[j]                change = True        if not change:            returnli = list(range(10000))# random.shuffle(li)# print(li)bubble_sort_2(li)print(li)

3、时间复杂度：n的平方，得走n-1趟

 

二、选择排序

1、思路：一趟遍历记录最小的数，放到第一个位置； 再一趟遍历记录剩余列表中最小的数，继续放置；以此类推

2、代码：关键点无序区和最小数的位置

import randomfrom timewrap import *@cal_time    #这是自己写的用于计算算法运行时间的装饰器def select_sort(li):    for i in range(len(li) - 1):        # i 表示趟数，也表示无序区开始的位置        min_loc = i   # 最小数的位置        for j in range(i + 1, len(li) - 1):            if li[j] < li[min_loc]:                min_loc = j        li[i], li[min_loc] = li[min_loc], li[i]li = list(range(10000))random.shuffle(li)print(li)select_sort(li)print(li)

3、时间复杂度：n的平方

 

三、插入排序

1、思路：列表被分为有序区和无序区两个部分。最初有序区只有一个元素。 每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。

2、代码：关键点摸到的牌和手里的牌，也就是无序区的元素怎么插入到有序区合适的位置

import randomfrom timewrap import *@cal_timedef insert_sort(li):    for i in range(1, len(li)):        # i 表示无序区第一个数        tmp = li[i] # 摸到的牌        j = i - 1 # j 指向有序区最后位置        while li[j] > tmp and j >= 0:            #循环终止条件： 1. li[j] <= tmp; 2. j == -1            li[j+1] = li[j]            j -= 1        li[j+1] = tmpli = list(range(10000))random.shuffle(li)print(li)insert_sort(li)print(li)

3、时间复杂度：n的平方

 

LOWB三人组就是以上排序，必须会默认代码，冒泡，选择，插入，时间复杂度都是n的平方，空间复杂度都是1

 

 

四、快速排序

1、思路：取一个元素p（第一个元素），使元素p归位； 列表被p分成两部分，左边都比p小，右边都比p大； 递归完成排序。

归位的意思是左边都比它小，右边的都比它大

2、代码：

import randomfrom timewrap import *import copyimport syssys.setrecursionlimit(100000)def partition(li, left, right):    # ri = random.randint(left, right)    # li[left], li[ri] = li[ri], li[left]    tmp = li[left]    while left < right:        while left < right and li[right] >= tmp:            right -= 1        li[left] = li[right]        while left < right and li[left] <= tmp:            left += 1        li[right] = li[left]    li[left] = tmp    return leftdef _quick_sort(li, left, right):    if left < right:    # 至少有两个元素        mid = partition(li, left, right)        _quick_sort(li, left, mid-1)        _quick_sort(li, mid+1, right)@cal_timedef quick_sort(li):    return _quick_sort(li, 0, len(li)-1)@cal_timedef sys_sort(li):    li.sort()li = list(range(10000))random.shuffle(li)#sys_sort(li1)quick_sort(li)

》》》注意：最坏的情况就是9 8 7 6 5 4 3 2 1 这种序列，复杂度就变为n的平方

 

五、堆排序

1、树与二叉树

》》》树：树是一种数据结构 比如：目录结构 树是一种可以递归定义的数据结构

》》》树是由n个节点组成的集合： 如果n=0，那这是一棵空树； 如果n>0，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树

》》》几个概念：

 

根节点、叶子节点：根就是A，叶子就是A的分支

树的深度（高度）：就是层数

树的度：就是每个父节点的分支节点数就是度，这其中最大的就是树的度

孩子节点/父节点

子树

 

》》》二叉树：树的特殊结构，指的是所有节点的度最大为2的树

》》》两种特殊的二叉树

满二叉树：度全为2，一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树

完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

 

》》》二叉树的存储方式

链式

顺序

父节点和左孩子节点的编号下标有什么关系？ 0-1 1-3 2-5 3-7 4-9

i --> 2i+1

父节点和右孩子节点的编号下标有什么关系？ 0-2 1-4 2-6 3-8 4-10

i --> 2i+2

 

》》》小结：（完全）二叉树可以用列表来存储，通过规律可以从父亲找到孩子或从孩子找到父亲。

 

2、堆排序

（1）两个概念

大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大

小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小

大根堆：

小根堆：

（2）堆的向下调整性质

当根节点的左右子树都是堆时，可以通过一次向下的调整来将其变换成一个堆。

（3）堆排序过程

》建立堆

》得到堆顶元素，为最大元素

》去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序

》堆顶元素为第二大元素

》重复步骤3，直到堆变空

（4）代码

from timewrap import *import randomdef _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_timedef 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)# li=[2,9,7,8,5,0,1,6,4,3]# sift(li, 0, len(li)-1)# print(li)

（5）内置模块

优先队列：一些元素的集合，POP操作每次执行都会从优先队列中弹出最大（或最小）的元素。

堆——优先队列

Python内置模块——heapq heapify(x) heappush(heap, item) heappop(heap)

利用heapq模块实现堆排序：

def heapsort(li):         h = []        for value in li:                 heappush(h, value)        return [heappop(h) for i in range(len(h))]

 

六、归并排序

假设现在的列表分两段有序，如何将其合成为一个有序列表，这种操作称为一次归并

import randomfrom timewrap import *import copyimport sysdef 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] = ltmpdef _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)

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

》三种排序算法的缺点：

快速排序：极端情况下排序效率低

归并排序：需要额外的内存开销

堆排序：在快的排序算法中相对较慢

 

 

 

七、希尔排序

希尔排序是一种分组插入排序算法。

首先取一个整数d1=n/2，将元素分为d1个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序；

取第二个整数d2=d1/2，重复上述分组排序过程，直到di=1，即所有元素在同一组内进行直接插入排序。

希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。

def insert_sort(li):    for i in range(1, len(li)):        # i 表示无序区第一个数        tmp = li[i] # 摸到的牌        j = i - 1 # j 指向有序区最后位置        while li[j] > tmp and j >= 0:            #循环终止条件： 1. li[j] <= tmp; 2. j == -1            li[j+1] = li[j]            j -= 1        li[j+1] = tmpdef shell_sort(li):    d = len(li) // 2    while d > 0:        for i in range(d, len(li)):            tmp = li[i]            j = i - d            while li[j] > tmp and j >= 0:                li[j+d] = li[j]                j -= d            li[j+d] = tmp        d = d >> 1

 

八、计数排序

# 0 0 1 1 2 4 3 3 1 4 5 5import randomimport copyfrom timewrap import *@cal_timedef count_sort(li, max_num = 100):    count = [0 for i in range(max_num+1)]    for num in li:        count[num]+=1    li.clear()    for i, val in enumerate(count):        for _ in range(val):            li.append(i)@cal_timedef sys_sort(li):    li.sort()li = [random.randint(0,100) for i in range(100000)]li1 = copy.deepcopy(li)count_sort(li)sys_sort(li1)