yyz notes
YiZhang-You
2023-05-17
目录

算法笔记(1)

# 本节内容

  • 算法概念
  • 算法复杂度
    • 时间复杂度：执行算法所需要的时间
    • 空间复杂度：执行算法所需要的内存
  • 复习：递归

# 1、算法

# 1.1 概念

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

程序 = 数据结构 + 算法

1

算法复杂度 (opens new window)分为时间复杂度 (opens new window)和空间复杂度 (opens new window)。其作用： 时间复杂度 (opens new window)是指执行算法所需要的计算工作量；而空间复杂度 (opens new window)是指执行这个算法所需要的内存 (opens new window)空间。（算法的复杂性体运行该算法时的计算机所需资源的多少上，计算机 (opens new window)资源最重要的是时间和空间（即寄存器 (opens new window)）资源，因此复杂度分为时间和空间复杂度。）

# 1.2 时间复杂度

在计算机科学 (opens new window)中，时间复杂性，又称时间复杂度，算法 (opens new window)的时间复杂度是一个函数 (opens new window)，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串 (opens new window)的长度 (opens new window)的函数。时间复杂度常用大O符号 (opens new window)表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近 (opens new window)的，亦即考察输入值大小趋近无穷 (opens new window)时的情况。

1

时间复杂度常用大O符号表述

  • O表示一个估集
  • n表示可能执行的次数

1

用logn表示算法过程循环折半的情况

1

时间复杂度总结

1

如何简单快速地判断算法复杂度

  • 快速判断算法复杂度
    • 确定问题规模n
    • 循环减半过程-->logn
    • k层关于n的循环-->n的k次方
  • 复杂情况：根据算法执行过程判断

1

# 1.3 空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序 (opens new window)的时间复杂度 (opens new window)是O(n^2),空间复杂度是O(1) 。而一般的递归算法 (opens new window)就要有O(n)的空间复杂度了，因为每次递归都要存储 (opens new window)返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量 (opens new window)。1

# 2、递归

程序调用自身的编程技巧称为递归（ recursion）

递归的两个特点：

  • 调用自身
  • 结束条件

1

# 注意点

递归注意点:
    1.函数里面有递归的话不能加装饰器。
        解决方法：写一个函数嵌套
            @ExecutionTime.cal_time
            def quick_sort(li):
                _quick_sort(li, 0, len(li) - 1)
    2.递归的最大深度是999,如何修改递归的最大深度
        解决方法：
            import sys
            sys.setrecursionlimit(100000)  # 自定义的递归最大深度
1
2
3
4
5
6
7
8
9
10

# 2.1 普通递归

"""
递归的两个特点：

- 调用自身
- 结束条件
"""


# 普通递归01

def func(x):
    if x > 0:
        print(x)
        func(x - 1)


func(3)  # 3，2，1


# 普通递归02  ！这种情况千万注意，最后一个递归执行完后才开始从最里面输出，所有才是-1，-2，-3
def func2(x):
    if x < 0:
        func2(x + 1)
        print(x)


func2(-3)  # -1，-2，-3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 2.2 汉诺塔实例

所以我们假设有A,B,C三根柱子，现在要把A柱子上的n个圆盘移动到C柱子上。我们可以先考虑A柱子上的n-1个圆盘，将他们先借用C柱子移动到B柱子上，假设用时T(n-1)，然后我们把A柱子上剩下的哪一个圆盘直接移动到C柱子上，最后在将B柱子上n-1个圆盘通过A柱子移动到C柱子上，用时T(n-1)。我们假设移动n个圆盘用时T(n)，则由推导显然有T(n)=2*T(n-1)+1。当问题缩减至A柱子上只有一个圆盘时，将它移动到C柱子耗时T(1) = 1，则根据上述推导可以得出汉诺塔问题递归算法的时间复杂度为O(2^n)。
1

规则

1

解析

把最下面和最下面一层的上面看成二个整体

1

总结

1

"""
汉诺塔
    n:
所以我们假设有A,B,C三根柱子，现在要把A柱子上的n个圆盘移动到C柱子上。我们可以先考虑A柱子上的n-1个圆盘，
将他们先借用C柱子移动到B柱子上，假设用时T(n-1)，然后我们把A柱子上剩下的哪一个圆盘直接移动到C柱子上，
最后在将B柱子上n-1个圆盘通过A柱子移动到C柱子上，用时T(n-1)。我们假设移动n个圆盘用时T(n)，则由推导显然有T(n)=2*T(n-1)+1。
当问题缩减至A柱子上只有一个圆盘时，将它移动到C柱子耗时T(1) = 1，则根据上述推导可以得出汉诺塔问题递归算法的时间复杂度为O(2^n)。
"""


def hanoi(n, a, b, c):
    """
    分成3个步骤
    :param n: 圆盘的个数
    :param a: 柱子A
    :param b: 柱子B
    :param c: 柱子C
    :return:
    """
    if n > 0:
        hanoi(n - 1, a, c, b)  # 第一步，上面的整体a经过c在到b
        print("%s-到-%s" % (a, c))  # 第二步，直接到c
        hanoi(n - 1, b, a, c)  # 第三步，b经过a在到c


hanoi(30, "A", "B", "C")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 3、列表查找

  • 什么是列表查找
  • 顺序查找
  • 二分查找

# 3.1 查找概念

  • 查找：在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程。
  • 列表查找（线性表查找）：从列表中查找指定元素
    • 输入：列表、待查找元素
    • 输出：元素下标（未找到元素时一般返回None或-1）
  • python内置列表查找函数：index()

# 注意

​ **index:是用的顺序查找， 虽然二分查找快很多，但是使用的前提是要先排序。排序的时间复杂度就是O(n) , **

# 3.2 顺序查找

  • 顺序查找：也叫线性查找，从列表第一个元素开始，顺序进行搜索，直到找到元素或搜索到列表最后一个元素为止。
  • 时间复杂度：O(n)
"""
顺序查找：也叫线性查找，从列表第一个元素开始，顺序进行搜索，直到找到元素或搜索到列表最后一个元素为止。

- 输入：列表、待查找元素
- 输出：元素下标（未找到元素时一般返回None或-1）
"""


# 方法一:
def search(li, ind):
    for index, value in enumerate(li):
        if value == ind:
            return index
    else:
        return None


print(search([1, 2, 3], 3))


# 方法二:
def search2(li, ind):
    for index, value in enumerate(li):
        if li[index] == ind:
            return index
    else:
        return None


print(search2([1, 2, 3], 3))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 3.3 二分查找

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

1

  • 时间复杂度是logn
"""
1、首先，假设表中元素是按升序排列。
2、记录表中间位置的关键字(mid=(最左边的索引+最右边的索引)//2)与查找关键字比较，
3、如果两者相等，则查找成功；
4、否则利用中间位置记录将表分成前、后两个子表，
5、如果中间位置记录的关键字mid的值大于查找关键字，则候选区(表示元素有可能在的地方)left = mid+1(索引)，
否则中间位置记录的关键字mid的值小于查找关键字，则候选区right = mid-1(索引)，
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

[1,2,3,4,5,6,7,8,9]  查找的元素=2

第一步
left = 0  索引
right = 8
mid = (0+8)//2 = 4（索引） 值就为5
mid 5 > 3 候选区在左边 ，所以right=mid索引-1  right=3 索引

第二步
left = 0
right = 3
mid = 1  值为2
mid 2<3 候选区在右边，所以left=mid索引+1  left=2 索引

第三步
left = 2
right = 3
mid = (2+3)//2 2
mid 3 == 3 所以就找到了

如果找到后面没有值的话就返回None
"""


from ExecutionTime import cal_time


@cal_time
def binary_search(li, val):
    li.sort()
    left = 0
    right = len(li) - 1
    while left <= right:  # 当right小于left的时候就表示没有找到
        mid = (left + right) // 2
        if li[mid] == val:
            return mid  # 找到了返回索引
        elif li[mid] > val:  # 带查找的值在mid的左侧
            right = mid - 1
        else:  # li[mid] < val 带查找的值在mid的右侧
            left = mid + 1
    else:  # 没有找到的情况，就是right小于left的时候
        return None


print(binary_search(list(range(1000000)), 4))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

# 4、列表排序

  • 什么是列表排序
  • 常见排序算法介绍
  • 排序算法分析

# 4.1 排序概念

  • 排序：将一组“无序”的记录序列调整为“有序”的记录序列
  • 列表排序：将无序列表变为有序列表
    • 输入：列表
    • 输出：有序列表
  • 升序与降序
  • 内置排序函数：sort() 等

常见排序算法

先大致分为三类

  • LOW B三人组

    • 冒泡排序

    • 选择排序

    • 插入排序

      这三种排序都在原地排序，
时间复杂度都是O(n^2)

计算机，差不多每秒执行10000000一千万次运算(循环一个就表示一次运算)
      1
      2
      3
      4

1

# 4.2 排序Low B三人组

# 4.2.1 冒泡排序

  • 列表每两个相邻的数，如果前面比后面大，则交换这两个数。
  • 上趟排序完成后，则无序区减少一个数，有序区增加一个数。
  • 排好的叫有序区， 没有排好的叫无序区。
  • 代码关键点：趟、无序区范围。
  • 时间复杂度：O(n^2) 因为列表长度为n，有二层循环，所以是n的平方

1

1

"""
冒泡排序算法的原理如下：
    比较相邻的元素。如果第一个比第二个大，就交换他们两个。(从索引为0的开始)
    对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数，(排好了一个也叫做一趟)。
    针对所有的元素重复以上的步骤，除了最后一个。
    持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法分析：
    (1)由此可见：N个数字要排序完成，总共进行（N-1）趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数
　　(2)冒泡排序的优点：每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。
    如：第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，
    同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，
    以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。

比如列表长度为6，就要进行5趟排序
每i趟的排序次数为(N-i)次
排序好的叫有序区，还没有排序好的叫无效区

1 3 2
    1 2 3
    1 2 3
"""
import random


# 普通版
def bubble_sort(li):
    """
        i:是趟数
        j:每趟的元素
    """
    for i in range(len(li) - 1):  # 第一层控制循环多少趟，n-1  列表长度减一
        for j in range(len(li) - i - 1):  # 第二层控制每一趟循环的次数(要在减一，因为最后一个不会在进行变化),
            if li[j] > li[j + 1]:  # 判断前面的数是否大于后面的数，大于就交换位置，否则不交换
                li[j], li[j + 1] = li[j + 1], li[j]
        print(li)


li = [random.randint(0, 100000) for i in range(0, 10)]  # 表示从0-100000随机10个整数
bubble_sort(li)


# 优化版
"""
没有进行优化的时候，如果给的列表已经排序好了，它还是会继续进行循环排序。
所以我们可以添加判断，如果下次循环没有发生变化就不用进行循环直接退出
[8, 7, 1, 2, 3, 4, 5, 6, 9]
[7, 1, 2, 3, 4, 5, 6, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
"""


def man_bubble_sort(li):
    """
        i:是趟数
        j:每趟的元素
    """
    for i in range(len(li) - 1):  # 第一层控制循环多少趟，n-1  列表长度减一
        exchange = False
        for j in range(len(li) - i - 1):  # 第二层控制每一趟循环的次数(要在减一，因为最后一个不会在进行变化),
            if li[j] > li[j + 1]:  # 判断前面的数是否大于后面的数，大于就交换位置，否则不交换
                li[j], li[j + 1] = li[j + 1], li[j]
                exchange = True  # 进入判断了就表示发生了二个元素的交换，如果没有进入判断，已经没有交换的元素了可以退出了
        print(li)
        if not exchange: # 已经没有交换的元素了可以退出了
            return


li = [9, 8, 7, 1, 2, 3, 4, 5, 6]
man_bubble_sort(li)
"""
这样就提供了效率
[8, 7, 1, 2, 3, 4, 5, 6, 9]
[7, 1, 2, 3, 4, 5, 6, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
"""
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

# 4.2.2 选择排序

  • 一趟排序记录最小的数，放到第一个位置
  • 再一趟排序记录列表无序区最小的数，放到第二个位置
  • ...
  • 算法关键点：有序区和无序区、无序区最小数的位置
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕
1

1

"""
选择排序是一种简单直观的排序算法，工作原理为：在未排序的序列中找出最小(大)元素与第一个位置的元素交换位置

注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；
                           而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

然后在剩下的元素中再找最小(大)元素与第二个元素的位置交换，依此类推，直到所有元素排序排序完成。
根据上述描述，一共进行n-1趟比较后，就能完成整个排队过程。我们可以知道，第k趟比较需要进行的数组元素的两两比较的次数为n-k次，
所以共需要的比较次数为n*(n-1) / 2，因此选择排序算法的时间复杂度与冒泡排序一样，也为O(n^2)。

算法简介：

     1.初始状态：序列为无序状态。

     2.第1次排序：从n个元素中找出最小(大)元素与第1个记录交换

     3.第2次排序：从n-1个元素中找出最小(大)元素与第2个记录交换

     4.第i次排序：从n-i+1个元素中找出最小(大)元素与第i个记录交换

    5.以此类推直到排序完成
"""


def select_sort_simple(li):  # 简单版的选择排序
    """
    这个简单版，是创建一个新的列表，通过每一趟的循环，用min函数获取到列表的最小值，然后把最小值放入新的列表，然后用remove在原列表删除这个最小值
    缺点：
        1.在使用min的时候也遍历了一遍列表，用remove删除的时候也改变了删除元素的后面元素的所有位置(因为如果把全面的元素删了，后面的元素，要依次的向前面补位)
        2.重新创建了一个列表，占用内存空间
    """
    li_new = []
    for i in range(len(li)):  
        min_li = min(li)
        li_new.append(min_li)
        li.remove(min_li)
    return li_new


li = [3, 4, 2, 1, 7, 8, 6, 9, 5]
print(select_sort_simple(li))


def select_sort(li):  # 推荐
    """
        从小到大
        假设列表的第一个元素是最小值，通过这个元素和后面的元素进行比较
    """
    for i in range(len(li) - 1):  # i表示执行多少趟 n-1
        min_ind = i
        for j in range(i + 1, len(li)):  # i+1 这里要注意，1.因为每执行一趟就排好了一个元素所以这里是i 2.因为我们是从第二个元素开始交换，所有可以i+1
            if li[j] < li[min_ind]:
                min_ind = j  # 如果给定的最小值大于后面的元素的话，就拿到这个新的下标(其实就是新的最小值，在拿这个最小值去对比)
        if min_ind != i:  # 等于i就表示改元素已经是最小的
            li[i], li[min_ind] = li[min_ind], li[i]  # 元素进行交换
        print(li)
    # return li


li = [3, 4, 2, 1, 7, 8, 6, 9, 5]
print(select_sort(li))


def select_sort02(li):  # 推荐
    """
        从大到小
        假设列表的第一个元素是最大值，通过这个元素和后面的元素进行比较
    """
    for i in range(len(li) - 1):  # i表示执行多少趟 n-1
        max_ind = i
        for j in range(i + 1, len(li)):
            if li[j] > li[max_ind]:
                max_ind = j
        if max_ind != i:
            li[i], li[max_ind] = li[max_ind], li[i]  # 元素进行交换
        print(li)
    # return li


li = [3, 4, 2, 1, 7, 8, 6, 9, 5]
select_sort02(li)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

# 4.2.3 插入排序

  • 初始时手里(有序区)只有一张牌，就在最左边的
  • 每次(从无序区)摸一张牌，插入到手里有序区的位置
  • 时间复杂度O(n^2)
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法
1

实现思路

1.从数组的第二个数据开始往前比较，即一开始用第二个数和他前面的一个比较，如果 符合条件（比前面的大或者小，自定义），则让他们交换位置。

2.然后再用第三个数和第二个比较，符合则交换，但是此处还得继续往前比较，比如有 5个数`8，15，20，45, 17`,17比45小，需要交换，但是17也比20小，也要交换，当不需 要和15交换以后，说明也不需要和15前面的数据比较了，肯定不需要交换，因为前 面的数据都是有序的。

3.重复步骤二，一直到数据全都排完。
1
2
3
4
5

1

"""

1.从数组的第二个数据开始往前比较，即一开始用第二个数和他前面的一个比较，如果 符合条件（比前面的大或者小，自定义），则让他们交换位置。

2.然后再用第三个数和第二个比较，符合则交换，但是此处还得继续往前比较，比如有 5个数`8，15，20，45, 17`,17比45小，
需要交换，但是17也比20小，也要交换，当不需 要和15交换以后，说明也不需要和15前面的数据比较了，肯定不需要交换，因为前 面的数据都是有序的。

3.重复步骤二，一直到数据全都排完。

和打牌一样，[3,2,1,5] 第一张牌3是有序区，拿起后面的一张牌2和前面的作比较，小于就交换，
如果左边没有值的时候就表示是最小的，还有就是左边的值比拿起的牌小的话就不交换

也是n-1趟 因为从第二张牌开始
"""


def insert_sort(li):
    """
    从小到大，
        第一张牌3是有序区，拿起后面的一张牌2和前面的作比较，如果左边比右边大的话，将左边的元素移到右边。并j-1比下面的元素
        没有可以交换的元素的话，就把拿起的牌放到有序区对应的位置，
        如果左边没有值的时候就表示是最小的，还有就是左边的值比拿起的牌小的话就不交换
    """
    for i in range(1, len(li)):  # 从第二张牌开始，
        temp = li[i]  # 拿起的一张牌
        j = i - 1  # 第一张牌,有序区的有几张牌的下标
        while j >= 0 and li[j] > temp:  # 左边没有元素的情况j(表示下标)小于0，有序区的牌大于拿起的牌，如果不大于就不用交换
            li[j + 1] = li[j]  # 如果左边比右边大的话，将左边的元素移到右边。并j-1比下面的元素
            j -= 1
        li[j + 1] = temp  # 交换位置
        print(li)


li = [3, 2, 1, 5, 6, 4, 7, 9, 8]
insert_sort(li)


def insert02_sort(li):
    """
    大到小
    """
    for i in range(1, len(li)):
        temp = li[i]
        j = i - 1
        while j >= 0 and li[j] < temp:
            li[j + 1] = li[j]
            j -= 1
        li[j + 1] = temp
        print(li)


li = [3, 2, 1, 5, 6, 4, 7, 9, 8]
insert02_sort(li)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# 4.3 排序NB三人组

# 4.3.1 快速排序

  • 快速排序的效率：快

    • 时间复杂度：nlogn

  • 快速排序的问题

    • 最坏情况

      @ExecutionTime.cal_time
def quick_sort(li):
    _quick_sort(li, 0, len(li) - 1)

"""
[9,8,7,6,5,4,3,2,1] 第一次交换9
[,8,7,6,5,4,3,2,9]  temp=1
[1,8,7,6,5,4,3,2,9]  1
[1,8,7,6,5,4,3,8,9]
[1,2,7,6,5,4,3,8,9]
就是每次交换，要么右边部分没有，要么左边部分没有，这样就是快速排序最坏情况
"""
li = list(range(10000,0,-1))  # 创建[10000,...,1]的列表，每次就是交换最大最小值，时间复杂度就变成了O(n^2)了
quick_sort(li)
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14

      • 解决方法

        重新现在第一个数，让这个p值不在是第一个，先随机选择一个
比如
	temp = li[5]  # 自定义p的元素
        1
        2
        3

    • 递归

      1.函数里面有递归的话不能加装饰器。
解决方法：写一个函数嵌套
    @ExecutionTime.cal_time
    def quick_sort(li):
    	_quick_sort(li, 0, len(li) - 1)
2.递归的最大深度是999,如何修改递归的最大深度
解决方法：
    import sys
    sys.setrecursionlimit(100000)  # 自定义的递归最大深度
      1
      2
      3
      4
      5
      6
      7
      8
      9

  • 快速排序思路：

    • 取一个元素p(列表的第一个元素)，使元素p归位(怎么归位后面说)
    • 列表被p分成两部分，左边都比p小，右边都比p大
    • 然后递归完成排序

    实现思路

    快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。 
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。 
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
    1
    2
    3
    4
    5

1

1

"""
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
"""
import ExecutionTime
import sys

sys.setrecursionlimit(100000)

def partition(li, left, right):
    """
    取列表第一个元素P，让其归为。格式为左边全部放比P小在，右边全部放比P大或者等于的。 ！（左边有值就向右移一位，右边有值就向左移一位）
    [5,3,6,8,2]  P=5 left=5,right=2
    流程 :
        1.我们先把P放入临时变量temp中,所以现在left=None,right=2   2小于5 放左边 所以left和right交换 left=2,right=None 【2,3,6,8,None】
        2.left有值向右移一位 left=3,right=None 3小于5 放左边 right不变 left=3,right=None  【2,3,6,8,None】
        3.left有值向右移一位 left=6,right=None 6大于5 放右边 交换 left=None,right=6   【2,3,None,8,6】
        4.right有值向左移一位 left=None,right=8 8大于5 right不变 right=8,left=None【2,3,None,8,6】
        5.right有值向左移一位.这个时候 left=right 所以当left=right的时候P就在这里 【2,3,5,8,6】
        右边有值
        2.移过后，
    :param li: 列表
    :param left: 最左边的值
    :param right: 最右边的值
    :return: 返回这个P值
    """
    temp = li[left]  # P 列表第一个元素，申请归位
    while left < right:  # 如果left>right已经没有交换的了
        while left < right and li[right] >= temp:  # （从右边找比temp小的数）右边的值大于p 不交换 right-1
            right -= 1
        li[left] = li[right]  # 把右边的值和左边交换
        while left < right and li[left] <= temp:  # (从左边找比temp大的数)，左边的值小于P,不交换 left+1
            left += 1
        li[right] = li[left]
    li[left] = temp  # left和right重回后就表示找到位置，赋值即可
    return left


def _quick_sort(li, left, right):
    """
    通过P的分解值先把列表拆分成比p大的和比p小的二部分
    :param li: 列表
    :param left: 最左边的值
    :param right: 最右边的值
    :return:
    """
    if left < right:
        mid = partition(li, left, right)  # P值
        _quick_sort(li, left, mid - 1)  # P值左边部分
        _quick_sort(li, mid + 1, right)  # P值右边部分

@ExecutionTime.cal_time
def quick_sort(li):
    _quick_sort(li, 0, len(li) - 1)

"""
[9,8,7,6,5,4,3,2,1] 第一次交换9
[,8,7,6,5,4,3,2,9]  temp=1
[1,8,7,6,5,4,3,2,9]  1
[1,8,7,6,5,4,3,8,9]
[1,2,7,6,5,4,3,8,9]
就是每次交换，要么右边部分没有，要么左边部分没有，这样就是快速排序最坏情况
"""
li = list(range(10000,0,-1))  # 创建[10000,...,1]的列表，每次就是交换最大最小值，时间复杂度就变成了O(n^2)了
print(li)
quick_sort(li)
print(li)
# s = range(10000,0,-1)
# print(s)

"""
递归注意点:
    1.函数里面有递归的话不能加装饰器。
        解决方法：写一个函数嵌套
            @ExecutionTime.cal_time
            def quick_sort(li):
                _quick_sort(li, 0, len(li) - 1)
    2.递归的最大深度是999,如何修改递归的最大深度
        解决方法：
            import sys
            sys.setrecursionlimit(100000)  # 自定义的递归最大深度
"""
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

# 4.3.2 堆排序

# 1、堆排序前传-树与二叉树
# 1. 树的基础知识
  • 树是一种数据结构 比如：目录结构
  • 树是一种可以递归定义的数据结构
  • 树是由n个节点组成的集合
    • 如果n=0，那这是一棵空树；
    • 如果n>0，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树。
  • 一些概念
    • 根节点(树的最上面，最根部)，叶子节点(树叶，没有分支)
    • 树的深度（高度，树有多少层）
    • 树的度（表示一个节点，最多分多少个叉[包括根节点]）
    • 孩子节点(父节点的下面)/父节点(子节点的上面)
    • 子树(从这个树的一个节点挖出来就叫子树)
1
# 2. 二叉树

基本概念

  • 二叉树：度不超过2的数

  • 每个节点最多有两个孩子节点

  • 两个孩子节点被区分位左孩子节点和右孩子节点

    1

二叉数类型

  • 满二叉数：一个二叉树，如果每一层的节点都达到最大值，则这个二叉树就是满二叉树
  • 完全二叉树：叶子节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉数
  • 非完全二叉数
1

二叉数的存储方法（表示方式）

  • 链式存储方式（后面讲）
  • 顺序存储方式

链式存储方式（后面讲）

....

堆排序前传-二叉树的顺序存储方式

  • 父节点和左孩子节点的编号下标有什么关系？
    • 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
1

通过父节点（i）找左孩子节点 i --> 2i+1 通过父节点找右孩子节点 i --> 2i+2

通过子节点（i）找父节点 i -- > (i-1)/2

1.父结点索引：(i-1)/2（这里计算机中的除以2，省略掉小数）
2.左孩子索引：2*i+1
3.右孩子索引：2*i+2

所以上面两个数组可以脑补成堆结构，因为他们满足堆的定义性质： # arr表示列表
    大根堆：arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)
    小根堆：arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)
1
2
3
4
5
6
7
# 2、堆排序
堆排序的时间复杂度O(N*logN),额外空间复杂度O(1)，是一个不稳定性的排序

堆的结构可以分为大根堆和小根堆，是一个完全二叉树，而堆排序是根据堆的这种数据结构设计的一种排序，下面先来看看什么是大根堆和小根堆
1
2
3

推：一种特殊的完全二叉树结构

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

性质：每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆；每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆。

1 
大根堆：arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)
小根堆：arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)
# 1. 堆的向下调整性质
  • 假设根节点的左右子树都是堆，但根节点不满足堆的性质
  • 可以通过一次向下的调整来将其变成一个堆
什么是堆的向下调整?
    把不是堆的二叉树经过一个叫做【向下调整】的操作变为堆
什么样的二叉树可以做向下调整?
    节点的左右子树都是堆，但自身不是堆的二叉树，比如:
1
2
3
4
1

动图：

1

流程：

1

2.堆排序过程：

    1. 建立堆。
    1. 得到堆顶元素，为最大元素。
    1. 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序
    1. 堆顶元素为第二大元素。
    1. 重复步骤3，直到堆变空。
  1. 建立堆 拿以下这个完全二叉树举例:
1

这个完全二叉树没有任何排列规则，现在我们需要通过向下调整函数把该二叉树变为大根堆( 一颗完全二叉树，满足任一节点都比其孩子节点大) 来看看GIF演示吧:

1

  1. 挨个出数 第一步已经建立好堆，那么现在堆的根结点为最大的数，先把根结点取出，放在列表中，再将堆的最后一个放到堆顶，再进行向下调整，调整后，堆的根结点又是最大数，再次将根结点放入列表，再次将堆的最后一个放到堆顶，重复这些步骤，知道所有的数都放入了列表。 再次用我自己做的GIFA进行演示:
1

堆排序具体实现

"""
向下调整函数实现
1、记录临时堆的根节点i，临时左右孩子节点j,临时堆顶节点temp
2、最后一个元素大于等于孩子节点，那么就先去比较父节点的左右孩子节点，如果右孩子节点没有的话就直接指向左孩子节点
3、在拿孩子节点和堆顶节点进行比较，如果孩子节点大于堆顶节点就交换，并重新指向新的i根节点和j孩子节点，否则就直接放到某一级的根节点上

堆排序实现
- 1. 建立堆(看堆是否需要向下调整)
- 2. 得到堆顶元素，为最大元素。
- 3. 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次向下调整重新使堆有序（重复）
- 4. 堆顶元素为第二大元素。
"""
import ExecutionTime


def sift(li, low, high):
    """
    堆向下调整函数
    :param li: 列表
    :param low: 堆的根节点
    :param high: 堆的最后一个元素
    :return:  返回一个调整好的大根堆
    """
    i = low  # 最开始指向根节点
    j = 2 * i + 1  # 左孩子节点
    temp = li[low]  # 把堆顶存起来
    while j <= high:  # 如果堆的最后一个节点没有孩子节点结束循环
        # 1、比较父节点的左右孩子节点，如果右孩子节点没有的话就直接指向左孩子节点
        if j + 1 <= high and li[j + 1] > li[j]:  # 如果有右孩子节点，并且右孩子节点比左孩子节点打的话就交
            j = j + 1  # 然后让j指向右孩子
        if li[j] > temp:  # 如果孩子节点大于堆顶节点，就交换。并重新指向新的i根节点和j孩子节点
            li[i] = li[j]
            i = j  # 下一层
            j = 2 * i + 1
        else:  # 如果孩子节点比根节点小，就把对应的堆顶节点赋值给这个i
            li[i] = temp  # 放到某一级的根节点上
            break
    else:
        li[i] = temp  # 放到叶子节点上

@ExecutionTime.cal_time
def heap_sort(li):
    """
    堆排序
    - 1. 建立堆(看堆是否需要向下调整)
    - 2. 得到堆顶元素，为最大元素。
    - 3. 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序
    - 4. 堆顶元素为第二大元素。
    :param li:
    :return:
    """
    n = len(li)
    # 1、建立堆。 堆是否需要向下调整，i表示建各个堆的下标，建立堆。因为子节点找父节点是(n-1)/2,
    #       最后面的孩子节点是(n-1),如果带入中就是(n-2)/2,这个就表示所有对应堆的根节点。
    #       这里的high我们就一直让它等于最后一个元素(本来一个是对应堆的最小元素[不好算]，但是直接表示最小元素也是可以的)
    for i in range((n - 2) // 2, -1, -1):
        sift(li, i, n - 1)
    # 2、第一步已经建立好堆，得到堆顶元素和最后一个元素进行替换  i就是一个最小的节点
    for i in range(n - 1, -1, -1):
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i - 1)  # 因为替换了所有要减一


li = [i for i in range(100000000)]
import random

random.shuffle(li)
print(li)
heap_sort(li)
print(li)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# 2. 堆排序-python内置模块

python内置模块（heapq）

常用函数

  • heapify(x)
  • heappush(heap,item)
  • heappop(heap)
"""
堆排序-python内置模块

python内置模块（heapq）

常用函数

- heapify(x)  # 构建最小根堆
- heappush(heap,item)
- heappop(heap)  # 每次弹出最小的元素
"""
import heapq

li = [9, 6, 0, 7, 2, 8, 3, 1, 5, 4]
heapq.heapify(li)  # 构建堆，最小根堆
print(li)
n = len(li)
for i in range(n):
    print(heapq.heappop(li), end='')  # 每次弹出最小的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 3. 堆排序-topk问题
  • 现在有n个数，设计算法得到前k大的数。（k<n），其实就是得到排序后列表前多少个
  • 解决思路
    • 排序后切片 O(nlogn) [9,3,1,2][:3]排序后 列表切片
    • 排序LowB三人组 O(kn) #排序比k大的趟
    • 堆排序思路 O(nlogk)

堆排序解决思路

  • 取列表前k个元素建立一个小根堆，堆顶就是目前第k大的数；
  • 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶则将堆顶更换为该元素，并且对堆进行一次调整；
  • 遍历列表所有元素后，倒序弹出堆顶；
"""
实现得到排序好的列表前k个元素

向下调整函数实现
1、记录临时堆的根节点i，临时左右孩子节点j,临时堆顶节点temp
2、最后一个元素大于等于孩子节点，那么就先去比较父节点的左右孩子节点，如果右孩子节点没有的话就直接指向左孩子节点
3、在拿孩子节点和堆顶节点进行比较，如果孩子节点大于堆顶节点就交换，并重新指向新的i根节点和j孩子节点，否则就直接放到某一级的根节点上

堆排序实现
- 取列表前k个元素建立一个小根堆，堆顶就是目前第k大的数；
- 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶则将堆顶更换为该元素，并且对堆进行一次调整；
- 遍历列表所有元素后，倒序弹出堆顶；
"""


def sift(li, low, high):
    """
    堆向下调整函数（大根堆）
    :param li: 列表
    :param low: 堆的根节点
    :param high: 堆的最后一个元素
    :return:  返回一个调整好的大根堆
    """
    i = low
    j = 2 * i + 1
    temp = li[low]
    while j <= high:  # 左孩子节点如果大于最后一个元素则结束循环
        if j + 1 <= high and li[j + 1] > li[j]:  # j+1<=high表示如果有右孩子节点，并且右孩子节点大于左孩子节点就交换
            j = j + 1
        if li[j] > temp:  # 如果左孩子节点大于堆顶节点，就交换。并重新指向新的i根节点和j孩子节点
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:  # 如果左孩子节点比根节点小，就把对应的堆顶节点赋值给这个i（放入堆顶）
            break
        li[i] = temp


def topk(li, k):
    """
    堆排序
    - 取列表前k个元素建立一个小根堆，堆顶就是目前第k大的数；
    - 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶则将堆顶更换为该元素，并且对堆进行一次调整；
    - 遍历列表所有元素后，倒序弹出堆顶；
    :param li:
    :return:
    """
    # 1、先取前k个数建立一个小根堆
    heap = li[0:k]  # 存放遍历好后的前k个元素
    for i in range((k - 2) // 2, -1, -1):  # 从后向前找，孩子节点找父节点是(n-1)/2,最后面一个元素的下标是n-1,所以把n带入中就是(n-2)//2
        sift(heap, i, k - 1)  #

    print("先取前k个数建立一个小根堆：", heap)  # [1, 5, 2, 3, 4]

    # 2、依次遍历后面的元素，如果比heap[0]第一个大，则进行向下排序
    for i in range(k, len(li) - 1):
        if li[i] < heap[0]:
            heap[0] = li[i]
            sift(heap, 0, k - 1)

    print("依次遍历后面的元素，得到一个未排序好的小根堆", heap)

    # 3、把已经得到列表前k个最大的数，从后面进行堆向下调整
    for i in range(k - 1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        sift(heap, 0, i - 1)

    # 4、排序好的前k个数
    return heap


import random

li = list(range(0, 999))
random.shuffle(li)
print(topk(li, 5))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

# 4.3.3 归并排序-归并

http://c.biancheng.net/algorithm/merge-sort.html
1

归并排序算法是在分治算法 (opens new window)基础上设计出来的一种排序算法，它可以对指定序列完成升序（由小到大）或降序（由大到小）排序，对应的时间复杂度为O(nlogn)。看见复杂度是O(n)因为会用到一个临时列表

归并排序算法实现排序的思路是：

  1. 将整个待排序序列划分成多个不可再分的子序列，每个子序列中仅有 1 个元素；
  2. 所有的子序列进行两两合并，合并过程中完成排序操作，最终合并得到的新序列就是有序序列。

示例

举个简单的例子，使用归并排序算法对 {7, 5, 2, 4, 1, 6, 3, 0} 实现升序排序的过程是：

  1. 将 {7, 5, 2, 4, 1, 6, 3, 0} 分割成多个子序列，每个子序列中仅包含 1 个元素，分割过程如下所示：

    1

整个序列不断地被一分为二，最终被分割成 {7}、{5}、{2}、{4}、{1}、{6}、{3}、{0} 这几个序列。

  1. 将 {7}、{5}、{2}、{4}、{1}、{6}、{3}、{0} 以“两两合并”的方式重新整合为一个有序序列，合并的过程如下图所示：

    1
# 1、归并排序，假设二个列表已经排好序的实现（简单版）

  • 假设现在的列表分成二段有序列表，如何将其合成一个有序列表

    1
"""

假设现在的列表分成二段有序列表，如何将其合成一个有序列表

1、将列表拆分成二个列表，[low:mid] [mid+1:high]
    low:表示第一个元素
    mid:表示左边部分中间的一个
    mid+1:右边部分第一个
    high:右边最后一个
[2,3,5,7,1,4,6,8,9]
[2,3,5,7] [1,4,6,8,9]
"""


def merge(li, low, mid, high):
    """
    :param li: 列表
    :param low: 表示左边列表第一个元素
    :param mid: 表示左边列表最后一个      mid+1:右边部分第一个
    :param high: 右边最后一个
    :return:
    """
    # 1、分别记录二个列表的第一个元素
    i = low
    j = mid + 1
    temp = []  # 临时存放列表
    # 2、当二个列表其中一个没有元素了则退出循环，注意左边列表和右边列表的界限条件条件[low:mid] [mid+1:high]
    while i <= mid and j <= high:
        if li[i] < li[j]:  # 如果第一个列表的值大于第二个列表的值，则添加到temp中，并且i指向后一个元素
            temp.append(li[i])
            i = i + 1
        else:
            temp.append(li[j])
            j = j + 1

    # 3、当第一个列表或者第二个列表已经没有元素了，则把列表中剩余的元素全部添加到temp临时列表中
    while i <= mid:
        temp.append(li[i])
        i = i + 1
    while j <= high:
        temp.append(li[j])
        j = j + 1

    # 4、！把临时列表的值，通过回显列表切分，复制回去
    print(temp,1)
    li[low:high + 1] = temp

    return li


li = [2, 3, 5, 7, 1, 4, 6, 8, 9]  # [2,3,5,7] [1,4,6,8,9]
print(merge(li, 0, 3, 8))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# 2、使用递归解决
  • 分解：将列表越分越小，直至分成一个元素
  • 终止条件：一个元素是有序的
  • 将两个有序的列表归并，列表越来越大
"""
实现思路：
    merge_sort() 用于将整个序列分割成多个子序列，merge() 用来合并这些子序列，合并的实现方式为：
        1. 用户递归将列表中的元素拆分成单个的（可能会没有）
        2. 然后通过写的归并方法归并元素
            a.分别记录二个列表的第一个元素
            b.当二个列表其中一个没有元素了则退出循环，注意左边列表和右边列表的界限条件条件[low:mid] [mid+1:high]
            c.当第一个列表或者第二个列表已经没有元素了，则把列表中剩余的元素全部添加到temp临时列表中
            d.！把临时列表的值，通过回显列表切分，复制回去

"""
import random


def merge(li, low, mid, high):
    """
    :param li: 列表
    :param low: 表示左边列表第一个元素
    :param mid: 表示左边列表最后一个      mid+1:右边部分第一个
    :param high: 右边最后一个
    :return:
    """
    # 1、分别记录二个列表的第一个元素
    i = low
    j = mid + 1
    temp = []  # 临时存放列表
    # 2、当二个列表其中一个没有元素了则退出循环，注意左边列表和右边列表的界限条件条件[low:mid] [mid+1:high]
    while i <= mid and j <= high:
        if li[i] < li[j]:  # 如果第一个列表的值大于第二个列表的值，则添加到temp中，并且i指向后一个元素
            temp.append(li[i])
            i = i + 1
        else:
            temp.append(li[j])
            j = j + 1

    # 3、当第一个列表或者第二个列表已经没有元素了，则把列表中剩余的元素全部添加到temp临时列表中
    while i <= mid:
        temp.append(li[i])
        i = i + 1
    while j <= high:
        temp.append(li[j])
        j = j + 1

    # 4、！把临时列表的值，通过回显列表切分，复制回去
    li[low:high + 1] = temp

    return li


def merge_sort(li, low, high):
    """将列表拆分在合并"""
    if low < high:  # 当列表至少有二个元素的时候进行拆分递归
        mid = (low + high) // 2
        merge_sort(li, low, mid)  # 左边部分
        merge_sort(li, mid + 1, high)
        print(li[low:high - 1])
        merge(li, low, mid, high)

    return li


li = list(range(0, 18))
random.shuffle(li)
li_sort = merge_sort(li, 0, len(li) - 1)
print(li_sort)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

# 4.3.4 总结

  • 三种排序算法的时间复杂度都是O(nlogn)
  • 一般情况下，就运行时间而言：
    • 快速排序 < 归并排序 < 堆排序
  • 三种排序算法的缺点：
    • 快速排序：极端情况下排序效率低
    • 归并排序：需要额外的内存开销
    • 堆排序：在快的排序算法中相对较慢
1
# 什么是稳定性
当列表[3,2,1,2,4]，在排序的时候第二个2和第四个2位置位置不发生改变。`第二个2还是在前面`,这个就叫做稳定性
1

# 4.4 希尔排序算法

前面给大家介绍了插入排序算法 (opens new window)，通过将待排序序列中的元素逐个插入到有序的子序列中，最终使整个序列变得有序。（插入排序算法是通过比较元素大小和交换元素存储位置实现排序的，比较大小和移动元素次数越多，算法的效率就越差）

希尔排序算法又叫缩小增量排序算法，是一种更高效的插入排序算法。和普通的插入排序算法相比，希尔排序算法减少了移动元素和比较元素大小的次数，从而提高了排序效率。

实现思路：

  • 希尔排序是一种分组插入排序算法
  • 首先取一个整数d1=n//2，将元素分为d1个组，每组相邻元素之间距离为d1，在各组内进行直接插入排序
  • 取第二个整数d2=d1//2，重复上述分组排序过程，直到d1=1，即所有元素在同一组内进行直接插入排序
  • 希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序，最后一趟排序使得所有数据有序

示例

我们尝试对 {35, 33, 42, 10, 14, 19, 27, 44} 做升序排序，具体的实现流程是：

  1. 间隔 4 个元素，将整个序列划分为 4 个子序列：

    1

    采用插入排序算法分别对 {35, 14}、{33, 19}、{42, 27}、{10, 44} 进行排序，最终生成的新序列为：

    1

  2. 间隔 2 个元素，再次划分整个序列：（进行下一次循环，d2 = d1 //2）

    1

    采用插入排序算法分别对 {14, 27, 35, 42} 和 {19, 10, 33, 44} 进行排序：

    1

  3. 采用插入排序算法对整个序列进行一次排序，过程如下：

    1

希尔排序的时间复杂度和选取的gap序列有关

"""
- 希尔排序是一种分组插入排序算法
- 首先取一个整数d1=n//2，将元素分为d1个组，每组相邻元素之间距离为d1，在各组内进行直接插入排序
- 取第二个整数d2=d1//2，重复上述分组排序过程，直到d1=1，即所有元素在同一组内进行直接插入排序
- **希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序，最后一趟排序使得所有数据有序**

"""


def insert_sort(li, gap):
    for i in range(gap, len(li)):
        temp = li[i]
        j = i - gap
        while j >= 0 and li[j] > temp:  # 如何前面的数大于后面的数则交换
            li[j + gap] = li[j]
            j -= gap

        li[j + gap] = temp


def shell_sort(li):
    d = len(li) // 2
    while d >= 1:
        insert_sort(li, d)
        d = d // 2
    return li


li = [3, 5, 1, 7, 2]
print(shell_sort(li))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 4.5 计数排序

http://c.biancheng.net/algorithm/counting-sort.html

通过统计序列中各个元素出现的次数，完成对整个序列的升序或降序排序，这样的排序算法称为计数排序算法。

缺点：

  • 需要知道排序的范围
"""
通过**统计序列中各个元素出现的次数**，完成对整个序列的升序或降序排序，这样的排序算法称为计数排序算法。

实现思路
    1. 提前拿到元素的最大值，或者提前知道列表中的元素
    2. 通过最大值，创建一个临时列表，每个值使用0代替。
    3. 遍历列表元素，通过下标和值，在临时列表对应位置进行累加（3次就表示这个元素有3个重复的）
    4. 取值遍历临时列表，将值添加到列表中

算法缺点，需要提前知道最大的数(像年纪排序用这个就非常好，比用c底层写的sort()排序都快)
"""


def count_sort(li, max_value):
    # 1. 创建临时列表
    temp = [0 for _ in range(max_value + 1)]
    # 2. 把遍历值通过下标，给对应的地方加一
    for val in li:
        temp[val] = temp[val] + 1
    li.clear()
    # 3.从临时列表取值 ind:值 val:有多少个这样的值
    for ind, val in enumerate(temp):
        for _ in range(val):
            li.append(ind)

    return li


import random

li = [random.randint(0, 100) for _ in range(1000)]
random.shuffle(li)
print(count_sort(li, 100))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 4.6 桶排序

http://c.biancheng.net/algorithm/bucket-sort.html

桶排序（又称箱排序）是一种基于分治思想、效率很高的排序算法，理想情况下对应的时间复杂度为 O(n)。

  • 桶排序的表现取决于数据的分布。也就是需要对不同数据排序是采用不同的分桶策略
  • 平均情况时间复杂度：O（n+k） k:表示桶
  • 最坏情况时间复杂度：O（n2k）
  • 空间复杂度：O（nk）

假设一种场景，对 {29，25，3，49，9，37，21，43} 进行升序排序，桶排序算法的实现思路是：

  • 准备 5 个桶，每个桶都有对应元素的编号；
  • 将待排序序列的各个元素放置到相同编号的桶中；
  • 从 1 号桶开始，依次获取桶中放置的元素，得到的就是一个升序序列。
1

桶排序：首先将元素分在不同的桶中，在对桶中的元素排序

"""
假设一种场景，对 {29，25，3，49，9，37，21，43} 进行升序排序，桶排序算法的实现思路是：

- 准备 5 个桶，每个桶都有对应元素的编号；
- 将待排序序列的各个元素放置到相同编号的桶中；
- 从 1 号桶开始，依次获取桶中放置的元素，得到的就是一个升序序列。
"""


def bucket_sort(li, n, max_num):
    """
    :param li: 列表
    :param n:  桶的个数
    :param max_num: 列表中最大的元素
    :return:
    """
    # 1. 创建空桶: 根据桶的个数创建一个二维列表 bucket_list:元素用列表存放
    bucket_list = [[] for _ in range(n)]

    for val in li:
        # 2.根据规则将所有元素分散到各个桶中: 根据最大元素max_num去均分桶存放的区间 比如: max_num=100 n=10 这样就10个数为一个桶
        # 2.1 为什么使用min? 因为当val=100的时候，python列表有是从0开始的100会没有地方存，所有使用min，当bucket=10的时候 n-1等于9 ，这样就可以成功存入桶中
        bucket = min(max_num // n, n - 1)
        bucket_list[bucket].append(val)

    # 3.合并桶：先进行排序，在进行合并
    li.clear()
    for buc in bucket_list:
        buc.sort()
        li.extend(buc)

    return li


import random

li = [random.randint(0, 100) for _ in range(1000)]
random.shuffle(li)
print(bucket_sort(li, 10, 100))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# 4.7 基数排序

http://c.biancheng.net/algorithm/radix-sort.html

引入示例：

  • 多关键字排序：假如现在有一个员工表，要求按照薪资进行排序，薪资相同的员工按照年纪排序

基数排序算法适用于对多个整数或者多个字符串进行升序或降序排序，例如：

121, 432, 564, 23, 1, 45, 788
"zhangsan"、"lisi"、"wangwu"
1
2

一个整数由多个数字组成，例如 123 由 1、2、3 这 3 个数字组成；

一个字符串由多个字符组成，例如 "lisi" 由 "l"、"i"、"s"、"i" 这 4 个字符组成。

基数排序算法的实现思路是：对于待排序序列中的各个元素，依次比较它们包含的各个数字或字符，根据比较结果调整各个元素的位置，最终就可以得到一个有序序列（先对个位数排序、依次十位、百位..）。

  • 对于待排序的整数序列，依次比较各个整数的个位数、十位数、百位数......，数位不够的用 0 表示；

  • 对于待排序的字符串序列，依次比较各个字符串的第一个字符、第二个字符、第三个字符......，位数不够的用 NULL 表示。

举个例子，使用基数排序算法对 {121, 432, 564, 23, 1, 45, 788} 进行升序排序，需要经历下图所示的三个过程：

1

优点：

  • 当位数比较小时 比如100以内，会非常快(比快速排序更快)

缺点：

  • 当位数多时，比如99999999,比较慢
"""
**基数排序算法的实现思路是：对于待排序序列中的各个元素，依次比较它们包含的各个数字或字符，根据比较结果调整各个元素的位置，最终就可以得到一个有序序列（先对个位数排序、依次十位、百位..）。**

- 对于待排序的整数序列，依次比较各个整数的个位数、十位数、百位数......，数位不够的用 0
- 对于待排序的字符串序列，依次比较各个字符串的第一个字符、第二个字符、第三个字符......，位数不够的用在字符串后面添加0代替

实现思路：借助桶的概率实现
    重复执行123步骤
    1. 得到列表最大的元素，通过最大的元素判断需要执行多少次`位的排序`
    2. 创建空桶: 0-9共10个桶，通过得到个位十位百位的值分别存入对应的桶中，对值取余(val // 10 ** it) % 10
    3. 分桶完成：把通过位数排序好的桶取出来，重新赋值给li,进行下一位的排序
"""


def radix_sort(li):
    """
    :param li: 列表
    :return:
    """
    max_num = max(li)
    # 1. 通过最大的元素判断需要执行几次while循环
    it = 0  # 表示现在正在比较第几位 比如: 131 0:表示比较个位1 1:表示比较十位2 2表示比较百位1
    while 10 ** it <= max_num:  # 比如最大的数是999，就会先从(0,10,100)依次从个位比较
        # 2. 创建空桶: 通过最大的数创建空桶，0-9共10个桶，通过个位十位百位的值分别存入对应的桶中
        bucket_list = [[] for _ in range(10)]

        # 3. 得到对应位数的值，分别存入桶中 bit表示存入对应的桶中
        for val in li:
            bit = (val // 10 ** it) % 10  # 得到对应位数的值 比如 18: 个位18//0%10=8 十位18//10%10=1
            bucket_list[bit].append(val)

        # 4.分桶完成: 把通过位数排序好的桶取出来，重新赋值给li,进行下一位的排序
        li.clear()
        for buc in bucket_list:
            li.extend(buc)
        it = it + 1


import random

li = [random.randint(0, 100) for _ in range(1000)]
# li = list(range(1000))
random.shuffle(li)
radix_sort(li)
print(li)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
编辑 (opens new window)
数据结构笔记(2)
算法笔记(2)

← 算法笔记(2)→

最近更新
01
配置yun源
05-24
02
linux-配置python虚拟环境
05-24
03
linux文件目录管理
05-24
更多文章>
Theme by Vdoing | Copyright © 2023-2023 yizhang | MIT License