基础算法：冒泡排序、选择排序、插入排序、快速排序、堆排序、归并排序

1. 算法概念

1）算法就是一个计算过程，解决问题的方法

 

2）时间复杂度小结

（1）时间复杂度：用来评估算法运行时间的一个式子

（2）一般来说，时间复杂度高的算法比复杂度低的算法慢

（3）常见的时间复杂度（按效率排序）

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n2 * logn) < O(n3)

（4）不常见的时间复杂度

O(n!)   O(2n)   O(nn)

（5）如何判断时间复杂度

循环减半的过程为O(logn)

几次循环就是n的几次方的复杂度

# O(1) print('Hello World')

# O(n) for i in range(n): print('Hello World')

# O(n2) for i in range(n): for j in range(n): print('Hello World')

# O(n3) for i in range(n): for j in range(n): for k in range(n): print('Hello World')

# O(1) print('Hello World') print('Hello World') print('Hello World')

# O(n2) for i in range(n): print('Hello World') for j in range(n): print('Hello World')

# O(n2) for i in range(n): for j in range(i): print('Hello World')

# O(logn) while n > 1: print(n) n = n / 2

 

3）空间复杂度小结

空间复杂度用来评估算法内存占用的大小

一般用空间换取时间

 

 

 

2. 列表

1）列表查找：从列表中查找指定元素

• 输入：列表、待查找元素
• 输出：元素下标或未查找到元素

 

顺序查找

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

 

二分查找

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

 

# O(n)
def linear_search(data_set, value):
    for i in range(len(data_set)):
        if data_set[i] == value:
            return i
    return


# O(logn)
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

 

2）列表排序：将无序列表变为有序列表

应用场景：

• 各种榜单
• 各种表格
• 给二分查找用
• 给其他算法用

 

 

 

3. 冒泡排序

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

1）代码关键点：

• 趟
• 无序区

# 时间复杂度：O(n2)
# 空间复杂度：O(1)
def bubble_sort(li):
    for i in range(len(li) - 1):
        for j in range(len(li) - 1 - i):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]

 

2）冒泡排序优化：

如果冒泡排序中执行一趟而没有发生交换，则列表已经是有序状态，可以直接结束算法

# 时间复杂度：O(n2)
# 空间复杂度：O(1)
def bubble_sort_optimised(li):
    for i in range(len(li) - 1):
        exchange = False
        for j in range(len(li) - 1 - i):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
                exchange = True
        if not exchange:
            return

 

 

 

4. 选择排序

• 一趟遍历记录最小的数，放到第一个位置
• 再一趟遍历记录剩余列表中最小的数，继续放置；
• 重复以上过程直到结束

 

1）代码关键点：

• 无序区
• 最小数的位置

# 时间复杂度：O(n2)
# 空间复杂度：O(1)
def select_sort(li):
    for i in range(len(li) - 1):
        min_index = i
        for j in range(i + 1, len(li)):
            if li[min_index] > li[j]:
                min_index = j
        li[min_index], li[i] = li[i], li[min_index]

 

 

 

5. 插入排序

1）插入排序思路：

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

# 时间复杂度：O(n2)
# 空间复杂度：O(1)
def insert_sort(li):
    for i in range(1, len(li)):
        j = i - 1
        tmp = li[i]
        while j >= 0 and li[j] > tmp:
            li[j + 1] = li[j]
            j -= 1
        li[j + 1] = tmp

 

2）优化空间：应用二分查找来寻找插入点

 

 

 

6. 快速排序

1）快速排序思路：

• 取一个元素p（第一个元素），使元素p归位
• 列表被p分成两部分，左边都比p小，右边都比p大
• 递归完成排序

# O(nlogn)
def quick_sort(li, left, right):
    if left < right:
        mid = partitiion(li, left, right)
        quick_sort(li, left, mid - 1)
        quick_sort(li, mid + 1, right)

def partition(li, left, right):
    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 left

 

2）效率：快速排序的时间复杂度较小

 

3）快速排序的问题

• 最坏情况：时间复杂度从O(nlogn)升级为O(n2)
• 递归

 

 

 

7. 堆排序

1）树的简介

（1）树是一种数据结构，比如：目录结构

（2）树是一种可以递归定义的数据结构

（3）树是由n个节点组成的集合：

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

（4）一些概念：

根节点、叶子结点

树的深度（高度）

树的度

孩子节点/父节点

子树

（5）特殊且常用的树--二叉树

二叉树：度不超过2的树（节点最多有两个叉）

（6）满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树

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

（8）二叉树的存储方式：

链式存储方式

顺序存储方式

父节点和左孩子节点的编号下标的关系：i(父节点) -> 2i + 1(子节点)

父节点和右孩子节点的编号下标的关系：i(父节点) -> 2i + 2(子节点)

 

2）堆

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

 

（1）堆的向下调整性质

假设：节点的左右子树都是堆，但自身不是

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

 

（2）堆排序过程

• 建立堆
• 得到堆顶元素，为最大元素
• 去掉对顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序
• 堆顶元素为第二大元素
• 重复以上步骤，直到堆变空

def shift(li, low, high):
    tmp = li[low]
    i = low
    j = 2 * i + 1
    
    while j <= high: # 第二种跳出条件，j > high
        if j < 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


def heap_sort(li):
    n = len(li)
    # 1. 建堆的过程
    for i in range(n // 2 - 1, -1, -1):
        shift(li, i, n - 1)
    # 2. 挨个出数
    for i in range(n - 1, -1, -1): # i表示此时堆的high位置
        li[0], li[i] = li[i], li[0]
        shift(li, 0, i - 1)

 

（3）堆排序--内置模块

优先队列：一些元素的集合，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))]

 

 

 

8. 归并排序

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

# 时间复杂度O(nlogn)
# 空间复杂度O(n)
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)

归并的应用：

• 分解：将列表越分越小，直至分成一个元素
• 终止条件：一个元素是有序的
• 合并：将两个有序列表归并，列表越来越大

 

 

快速排序、堆排序、归并排序小结：

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

 

一般情况下，就运行时间而言：

快速排序 < 归并排序 < 堆排序

 

三种排序算法的缺点：

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

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

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