NB三人组

# 快速排序

快速排序: 快
快速排序思路:
     1> 取一个元素p (第一个元素), 使元素p 归位 ;
     2> 列表被p分为两部分, 左边都比p小, 右边都比p大.
     3> 递归完成排序.

def partition(li, left, right):
    temp = li[left]
    while left < right:
        # -- 这内层的两个循环 >= <= 是升序; <= >= 是降序.
        while left < right and li[right] >= temp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] <= temp:
            left += 1
        li[right] = li[left]
    li[left] = temp
    return left


def quick_sort(data, left, right):
    if left < right:
        mid = partition(data, left, right)
        quick_sort(data, left, mid - 1)
        quick_sort(data, mid + 1, right)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度: O(nlogn)

# 快排框架

# 注:整个排序过程,data指的都是整个大列表.不切片是因为切片需要耗费时间.
# data是整个列表、left和right可表示整个大列表的一部分,表示范围
def quick_sort(data, left, right):
    # left < right 表明列表这个区域至少有两个元素;left=right 有一个元素;
    # So,对至少有两个元素的列表进行递归!!
    if left < right:
        # 假设"归位"的实现函数是partition
        # 刚开始,left指向下标为0的位置,right指向下标为len(data)-1的位置
        # 返回mid: 归位位置的下标,列表就会被分为左右两部分,每个部分再进行快速排序
        mid = partition(data, left, right)
        # 归位后,left和right指向的是需要递归的列表的头和尾 递归里也会归位,归位后同理.
        quick_sort(data, left, mid - 1)
        quick_sort(data, mid + 1, right)
    return li

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 归位原理

那么问题来啦, partition函数如何实现呢? 下面是归位的过程详解.

`5` 7 4 6 3 1 2 9 8 -- "归位" --> 2 1 4 3 `5` 6 7 9 8  最终得达到`5`左边的数都比5小,`5`右边的数字都比5大的效果!!

先拿一个变量将`5`存储起来
左边就留出了一个位置,左边的位置是留给比5小的数字准备的!
     7  4  6  3  1  2  9  8
⬆️                       ⬆️
left                     right
从哪里开始找呢?从右边开始找. 8 9都比5大,2比5小,2放到了左边的空位上!
右边就留出了一个位置,右边的位置是留给比5大的数字准备的!
 2    7  4  6  3  1     9  8
⬆️                  ⬆️
left               right
从哪里开始找呢?从左边开始找.7比5大,7就放到了右边的空位上!
此时左边又留出了一个位置.以此类推.
 2      4  6  3  1  7  9  8
    ⬆️             ⬆️
   left           right
-- right移到1的位置, 1 需要填补左边空缺
   即right位置上的1放到left位置上的空缺
 2     4  6  3   1  7  9  8   - 移
    ⬆️          ⬆️
   left        right
 2   1  4  6  3     7  9  8   - 补
    ⬆️          ⬆️
   left        right
-- left移到6的位置, 6 需要填补右边空缺
 2   1  4  6  3     7  9  8   - 移
          ⬆️    ⬆️
         left   right
 2   1  4    3   6  7  9  8   - 补
          ⬆️    ⬆️
         left   right
-- right移动到3的位置, 3 需要填补左边空缺
 2   1  4      3  6  7  9  8  - 移
          ⬆️  ⬆️
         left right
 2   1  4  3      6  7  9  8  - 补
          ⬆️  ⬆️
         left right
ok,右边空缺下来了. left需要右移,找比5大的数. 
但left右移,left和right重合啦!!此次"归位"结束,一开始用变量存储的`5`放到left和right重合的位置!!
 2   1  4  3  `5`  6  7  9  8
              ⬆️
             right
             left

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

# 归位代码实现

partition 函数看似有两个while循环, 但实际上时间复杂度为 O(n)

def partition(li, left, right):
    # 注:这里不要写li[0],因为进行归位的列表可能是大列表的一部分.
    temp = li[left]
    print("temp:", temp)
    while left < right:  # 当left=right时,代表归位到了中间位置,循环才会结束.
        # 一旦当li[right] < temp 时跳出循环
        # 临界情况,因为循环体内,每次循环right都要减1,当right减到跟left一样时 也需跳出循环
        # eg: 3 4 7 5 9 10 --> temp等于3,right一开始等于n-1=5
        while left < right and li[right] >= temp:  # 从右边开始找比temp小的数
            right -= 1  # right往左走一步
        li[left] = li[right]  # 把右边的数放到了左边的空位上 left和right碰上了也没关系
        print('在右边找补左:', li)
        # 一旦当li[left] > temp 时跳出循环
        # 此处的left<right有两个作用:
        #    1> 当上面那个循环的left=right后,此处的循环不会执行
        #    2> 此处的循环中,left=right了,退出此处的循环
        while left < right and li[left] <= temp:  # 从左边开始找比temp大的数
            left += 1  # left往右走一步
        li[right] = li[left]  # 把左边的数放到了右边的空位上 left和right碰上了也没关系
        print('在左边找补右:', li)
    # 循环结束,left和right相等,处于归位位置.
    li[left] = temp
    return left


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


if __name__ == '__main__':
    li = [5, 7, 4, 6, 3, 1, 2, 9, 8]
    partition(li, 0, len(li) - 1)
    print('归位结果如下:', li)


"""
temp: 5
# -- "" 移到/赋值/覆盖 `` 的位置.
在右边找补左: [`2`, 7, 4, 6, 3, 1, "2", 9, 8]
在左边找补右: [2, "7", 4, 6, 3, 1, `7`, 9, 8]
在右边找补左: [2, `1`, 4, 6, 3, "1", 7, 9, 8]
在左边找补右: [2, 1, 4, "6", 3, `6`, 7, 9, 8]
在右边找补左: [2, 1, 4, `3`, "3", 6, 7, 9, 8]
在左边找补右: [2, 1, 4, 3, `"3"`, 6, 7, 9, 8]
归位结果如下: [2, 1, 4, 3, 5, 6, 7, 9, 8]    
# -- 然后递归,对5左边的[2,1,4,3]和右边的[6,7,9,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

# 快排代码实现

import random


def partition(li, left, right):
    temp = li[left]
    while left < right:
        # -- 这内层的两个循环 >= <= 是升序; <= >= 是降序.
        while left < right and li[right] >= temp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] <= temp:
            left += 1
        li[right] = li[left]
    li[left] = temp
    return left


def quick_sort(data, left, right):
    if left < right:
        mid = partition(data, left, right)
        quick_sort(data, left, mid - 1)
        quick_sort(data, mid + 1, right)


li = [random.randint(0, 20) for _ in range(10)]
print(li)
quick_sort(li, 0, len(li) - 1)
print(li)

"""
[19, 20, 18, 14, 18, 9, 10, 1, 13, 8]
[1, 8, 9, 10, 13, 14, 18, 18, 19, 20]

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

补充

# 注:若想测试该快排花费的时间 直接在quick_sort上加装饰器会导致打印很多次,因为quick_sort是一个递归函数
# 解决办法:套一个马甲
def _quick_sort(data, left, right):pass

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

1
2
3
4
5
6
7

快排时间复杂度不严谨的数学推导

                            16个数 
              8                                8 
      4               4                4               4
  2       2       2       2        2       2       2       2
1   1   1   1   1   1   1   1    1   1   1   1   1   1   1   1

假设有16个数,归位的时间复杂度为O(n)
第一层 2次归位,为O(8)+O(8)=O(16)
第二层 4次归位,为O(4)+O(4)+O(4)+O(4)=O(16)
第三层、第四层同理,每层的时间复杂度都为O(n)
一共有多少层呢?2^x=16 x为4 --> O(logn)

即层数的时间复杂度*每一层归位的时间复杂度 = O(n)*O(logn)=O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13

# 快排的问题

1> 快排是递归的,会消耗相当一部分系统资源
2> 快排有一个最坏情况的出现
eg: li=[9,8,7,6,5,4,3,2,1]
 9   8  7  6  5  4  3  2  1
⬆️                       ⬆️
left                     right  
9拿出来,从right指针开始,1<9,会变成 1 8 7 6 5 4 3 2 1,然后从left指针开始,8、7、6、5、4、3、2都比9小..left和right碰到了一次
So,此次归位的结果是 1 8 7 6 5 4 3 2 9
9右边没有值,那就对9左边的 1 8 7 6 5 4 3 2 进行归位
1拿出来,right往左移,发现所经过的数都比1大,left和right重合,1又被写回来啦
So,此次归位的结果是 1 8 7 6 5 4 3 2
1左边边没有值,那就对1右边的 8 7 6 5 4 3 2 进行归位
... ...
以此类推


可以发现,快排的最坏情况, 每次归位的结果只会 少一个数/排好一个数, 所以快排的最坏情况 时间复杂度为O(n^2)
但这种最坏情况,出现的概率很小.
有种不是优化的优化方法 -- 随机化的快排:
  在上述的讲解中,快排取一个元素进行归位,都是取的第一个数
  那是否可以随机找一个值?
  那么我们添加一步,将随机找的数跟第一个数交换一下..其余的步骤不变.
  只能说该优化减少了最坏情况的出现.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 堆排序

def sift(li, low, high):
    i = low
    j = 2 * i + 1
    temp = li[low]
    while j <= high:
        # 若将sift()中while循环里 li[j + 1] > li[j] 、li[j] > temp 都改成小于,建立的就是小根堆.
        # 小根堆进行堆排序后是降序;大根堆进行堆排序后是升序.
        if j + 1 <= high and li[j + 1] > li[j]:
            j = j + 1
        if li[j] > temp:
            li[i] = li[j]
            i = j
            j = i * 2 + 1
        else:
            break
    li[i] = temp


def heap_sort(li):
    n = len(li)
    for i in range((n - 2) // 2, -1, -1):
        sift(li, i, n - 1)
    for i in range(n - 1, -1, -1):
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i - 1)

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

时间复杂度: O(nlogn)
Ps: 快排和堆排的时间复杂度一样, 但真实情况下,快排要比堆排快一点..

# 基础知识

堆排序前传 -- 树与二叉树

# 树的概念

树是一种数据结构比如:目录结构
树是一种可以递归定义的数据结构
树是由n个节点组成的集合:
如果n=0, 那这是一棵空树;
如果n>0, 那存在一个节点作为树的根节点,其它节点可以分为m个集合,每个集合的本身又是一棵树.

根节点  -- A
叶子结点  -- B C H I P Q K L M N
树的深度/高度  -- 4 即看最深有多少层
节点的度  -- E节点往下分了两个叉,其度为2;F节点往下分了三个叉,其度为3
树的度  --  6 A节点的度为6,是该树中节点的度的最大值
孩子节点/父节点  --  E是I的父节点,I是E的孩子节点
子树  --  整体是一棵树;B是一棵树;E I J P Q是一棵树;I是一棵树;J P Q是一棵树.

1
2
3
4
5
6
7

# 完全二叉树

注: 堆是一个特殊的完全二叉树.

二叉树: 度不超过2的树
每个节点最多有两个孩子节点
两个孩子节点被区分为左孩子节点和右孩子节点

满二叉树: 一个二叉树,若每一层的节点数都达到最大值2, 则这个二叉树就是满二叉树..

完全二叉树: 叶子节点只能出现在最下层和次下层, 并且最下面一层的节点都集中在该层最左边的若干位置的二叉树..
说人话,(◐‿◑) 就是最下面一层可以不满,但必须从左到右依次排过来!!

# 父子互找

即计算机如何存储二叉树. 有两种方式.
1> 链式存储方式
2> 顺序存储方式 -- 用列表来存

Ps: 这里我们重点关注顺序存储方式, 链式存储在后续讲述链表相关知识点会详细阐述!!

图中将一颗完全二叉树按顺序存储到了一个列表中..

Q: 父节点与左孩子节点的编号下标有什么关系?
A: 若i表示父节点的下标,那么该父节点的左孩子节点的下标是 --> 2i+1

父节点&左孩子节点   9&8  8&6  7&0  6&2  5&3
在列表中对应下标    0-1  1-3  2-5  3-7  3-9

1
2

Q: 父节点与右孩子节点的编号下标有什么关系?
A: 若i表示父节点的下标,那么该父节点的右孩子节点的下标是 --> 2i+2

父节点&右孩子节点   9&7  8&5  7&1  6&4
在列表中对应下标    0-2  1-4  2-6  3-8

1
2

若知道任意子节点(不管是左孩子节点还是右孩子节点)在列表中的下标,那么该子节点的父节点的下标为 (i-1)//2 注: 整除

# 大小堆

堆: 堆的逻辑结构为一颗完全二叉树, 是一种特殊的完全二叉树结构.

大根堆: 一颗完全二叉树, 满足任意节点都比其孩子节点大; -- 父亲比孩子都大
小根堆: 一颗完全二叉树, 满足任意节点都比其孩子节点小. -- 父亲比孩子都小

注: 堆排序使用大根堆排出来的是增序的!!

# 堆的向下调整性

假设根节点的左右子树都是堆, 但根节点不满足堆的性质! 可以通过一次向下的调整来将其变成一个堆.

这棵树的是完全二叉树,但不满足堆的性质.不是大根堆、也不是小根堆.
抛开2这个根节点,它的左子树 9 8 5 6 4 3 是大根堆,右子树 7 0 1 也是大根堆.
那么可通过向下调整将这整颗树变成一个大根堆.

2<9 2<7 9>7  9作为根节点
2<8 2<5 8>5  8顶上去
2<6 2<4 6>4  6顶上去
最后,2放上去了,此处成为了一个叶子结点.


举一反三:
  若根节点是数字7,不是数字2. 那么向下调整后的大根堆 9 8 7 7 5 0 1 6 4 3, 根节点向下调整到的位置是倒数第二层.

1
2
3
4
5
6
7
8
9
10
11
12

# 堆排序过程

step1: "农村包围城市" - 建立堆.
step2: 开始挨个排序.
     1> 得到堆顶元素, 为最大元素.
     2> 去掉堆顶, 将堆最后一个元素放到堆顶, 通过一次 堆的向下调整 重新使堆有序.
     3> 堆顶元素为第二大元素.
     4> 重复 2>, 直到堆变空.

# -- 向下调整的过程!sift函数的时间复杂度为O(logn),它最多走树的高度那么多层,是折半的过程.
# 回顾下哦,堆的向下调整是根节点的左右子树都是堆,但根节点不满足堆的性质
def sift(li, low, high):
    """参数
    li: 列表
    low: 堆的根节点/堆顶元素的位置
    high: 堆最后一个元素的下标 - ★用于判断有没有越界!
    """
    i = low  # i初始化为根节点的位置
    j = 2 * i + 1  # j初始化为左孩子的位置
    temp = li[low]  # 把堆顶元素存起来
    # 简单阐述循环的过程:
    #    可以简单理解将根节点的元素拿开, 空了个位置.需要下一层比较大的数顶上来.
    #    下一层的元素顶上来后, 又空了个位置.需要看下一层较大的孩子与暂存的根节点元素比较,大点的弥补上去.
    #    以此类推..
    # 退出循环的条件:
    #    情况1:若i的孩子j的位置大于堆最后元素的下标,那证明i元素是叶子节点,它没有孩子.退出循环.
    #         也就是说,看j的位置有无越界.若没有越界,循环继续.
    #    情况2:在循环的过程中,暂存的根节点元素找到了合适的位置.退出循环.
    # 退出循环后:
    #    将暂存的根节点元素放到合适的位置
    #    while循环正常执行完 - 某一级的领导位置上; while循环遇到break退出 - 叶子节点.
    while j <= high:
        # 右孩子存在且右孩子比左孩子大,j指向右孩子
        if j + 1 <= high and li[j + 1] > li[j]:
            j = j + 1
        if li[j] > temp:
            li[i] = li[j]  # 较大的孩子节点顶上去啦
            # 因为孩子节点顶上去了,i得指向新的空位置,所以这里需要更新下i和j
            i = j
            j = i * 2 + 1
        else:  # li[j] <= temp  temp找到了合适的位置,退出循环
            # ps:其实我对于li[j]=temp的情况存在疑惑,人为可以构造这种情况,堆排序过程中会出现该情况吗?
            #    比如我可以人为构造这样一颗树[8, 9, 7, 8, 5, 0, 1, 6, 4, 3],向下调整.
            #    其调整结果是[9, 8, 7, 8, 5, 0, 1, 6, 4, 3].
            break
        # print('过程中:', li)
    # 退出循环,temp放到了合适的位置
    li[i] = temp


def heap_sort(li):
    # 我们晓得 通过孩子节点的下标i能推导出父节点的下标 --> (i-1)//2
    # 我们也知道,最后一个叶子节点的下标为n-1 <n为列表元素的个数/树的节点个数>
    # 那么求树中最后一个非叶子节点的下标 --> (n-1-1)//2 即 n//2 -1
    n = len(li)
    # "农村包围城市"
    # 依次<从最后一个到第一个>对树中每一个非叶子节点作为根节点的完全二叉树进行向下调整,将其变成一个堆
    # ▲ 该for结束后,建堆完成!!
    # -- ◎ 若将sift()中while循环里 li[j + 1] > li[j] 、li[j] > temp 都改成小于,建立的就是小根堆.
    for i in range((n - 2) // 2, -1, -1):
        # 注意,先明确此处sift函数的最后一个参数,是用来判断有无越界的!
        # 思路1:
        # 很正常的,我们会想着求从大树里剖离出的每个完全二叉树的最后一个元素的下标
        # 该下标作为sift函数最后一个参数的值,我们假设为x
        # 思路2:
        # 再换个思路,用最后一个叶子节点下标 n-1
        # 分析比较:
        #    求得下标为i的节点的左孩子节点下标 j = 2*i + 1
        #    So, [若越界]   j>x 、j>n-1  、n-1>x --> j > n-1 > x
        # ★ 关键在于 越界时, j > n - 1
        # 这里以n-1作为每棵完全二叉树有无越界的判断条件,也许你会问,万一,越界时,j处于x和n-1之间呢?
        # >: 你放一万个心,因为整颗大树是一颗完全二叉树!!越界时候,j一定大于n-1!!!
        sift(li, i, n - 1)
        # print(f"倒数第{i+1}个非叶子节点构建堆的结果:", li)
    # ▲ 建堆完成后, 开始挨个排序.
    # ★ 在该循环过程中,i一直指向当前堆中要与根节点元素交换的那一个元素!!!
    for i in range(n - 1, -1, -1):
        li[0], li[i] = li[i], li[0]
        # 都是对整个堆的调整!!
        # 注:这里堆的向下调整,要排除掉交换下来的那个堆顶元素.. So,这里sift的参数high的值是i-1
        sift(li, 0, i - 1)  # 当i=0时,sift函数内部也是可以正常运行的,无需加判断.
        # print(f"排序过程", li)


if __name__ == '__main__':
    import random

    li = [random.randint(0, 20) for _ in range(10)]
    print(li)
    heap_sort(li)
    print(li)

"""
[15, 7, 18, 12, 6, 7, 16, 6, 17, 9]
[6, 6, 7, 7, 9, 12, 15, 16, 17, 18]
"""

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
86
87

# 堆排序内置模块

Python内置模块 -- heapq
常用函数:
     heapify(x)
     heappush(heap, item)
     heappop(heap)

import heapq  # q指的是queue 优先队列
import random

li = [random.randint(0, 20) for _ in range(10)]
print("初始值:", li)
heapq.heapify(li)  # 建堆,默认是小堆
print("建堆后:", li)
li_sort = []
for _ in range(len(li)):
    li_sort.append(heapq.heappop(li))
print("排序后:", li_sort)

"""
初始值: [15, 2, 9, 15, 5, 3, 12, 19, 6, 13]
建堆后: [2, 5, 3, 6, 13, 9, 12, 19, 15, 15]
排序后: [2, 3, 5, 6, 9, 12, 13, 15, 15, 19]
"""

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# topk问题!!

现在有n个数, 你要设计算法得到前k大的数. (k<n)

解决思路: O(nlogn) ; O(nk) ; O(nlogk)

>> 思路一
   快速排序后切片 -- O(nlogn+k) 四舍五入 O(nlogn)
>> 思路二
   使用lowB三人组 -- O(nk)
       冒泡排序和选择排序有一个特点,循环一次就能得到一个 最大/最小 的数, 循环k次即可.
       插入排序,维护一个长度为k的列表,来一个就放进去,但要根据插入排序的规则保证列表中的元素是排序好.
               维护的列表里有k个元素后,继续插入,需要判断.
                   若比维护的列表中第k大的数大,就插进去.插到合适的位置(保证维护的列表有序),被挤出来的元素舍弃掉.
               即试图插入n个数,但列表长度有限,为k,若能插入,插入时最坏情况需要遍历一遍维护的列表,保证里面的k个元素有序.
               最坏时,n个数都要插进去,插入的位置都要将维护的列表遍历一遍.So,O(nk)
   跟思路一相比,思路二更好,因为思路二不会把所有的都排一遍.
   思路一和思路二谁更快,取决于 k和logn的大小.
>> 思路三
   使用堆排序 -- O(nlogk)
   step1> 取列表前k个数建立一个小根堆. 堆顶就是目前第k个大的数
   step2> 依次往后遍历原列表,对于列表中的元素.
          若小于堆顶,则忽略该元素;
          若大于堆顶,则将堆顶更换为该元素,并且对堆进行一次调整.
   step3> 遍历列表所有元素后,倒序弹出堆顶. 
   简单理解,最坏情况就是进行了n次向下调整,这里对k个元素向下调整,其时间复杂度为O(logk),进行n次,就是O(nlogk)
        最后对k个元素的小根堆进行排序,可以四舍五入忽略不计.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

代码实现:

def sift(li, low, high):
    i = low
    j = 2 * i + 1
    temp = li[low]
    while j <= high:
        if j + 1 <= high and li[j + 1] < li[j]:
            j = j + 1
        if li[j] < temp:
            li[i] = li[j]
            i = j
            j = i * 2 + 1
        else:
            break
    li[i] = temp


def topk(li, k):
    heap = li[0:k]  # 取出列表的前k个值
    # step1: 对取出来的k个值建堆
    for i in range((k - 2) // 2, -1, -1):
        sift(heap, i, k - 1)
    # step2: 遍历列表中剩余的所有元素
    for i in range(k, len(li)):
        # 比较列表中剩下的元素与小根堆堆顶元素的大小
        if li[i] > heap[0]:  # 若比堆顶大
            heap[0] = li[i]  # 覆盖
            sift(heap, 0, k - 1)  # 做调整
    # step3: 挨个输出
    for i in range(k - 1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        sift(heap, 0, i - 1)
    return heap


li = [6, 8, 1, 9, 3, 0, 7, 2, 4, 5]
print(topk(li, 5))  # [9, 8, 7, 6, 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

# 归并排序

def merge(li, low, mid, high):
    i = low
    j = mid + 1
    temp = []
    while i <= mid and j <= high:
        # li[i] < li[j]是升序;li[i] > li[j]是降序.
        if li[i] < li[j]:
            temp.append(li[i])
            i += 1
        else:
            temp.append(li[j])
            j += 1
    while i <= mid:
        temp.append(li[i])
        i += 1
    while j <= high:
        temp.append(li[j])
        j += 1
    li[low:high + 1] = temp


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)

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

时间复杂度: O(nlogn)
还需要O(n)的空间, 最大时, 需要一个排序列表长度的列表进行辅助!! 即空间复杂度 O(n)
Python内置函数sort的底层是基于归并排序结合插入排序并做了一些优化实现的!! -- Tim排序算法

# 归并操作

假设现在的列表分两段有序, 如何将其合成为一个有序列表? -- 这种操作称为一次归并!!
eg: [2,5,7, 1,3]

代码实现归并操作.

# 归并的前提是一个列表包含左右两部分有序的列表
def merge(li, low, mid, high):
    i = low
    j = mid + 1
    temp = []
    # -- 该while循环执行完,左右肯定有一边没有数啦!
    while i <= mid and j <= high:  # 保证左右两边都有数
        if li[i] < li[j]:
            temp.append(li[i])
            i += 1
        else:
            temp.append(li[j])
            j += 1
    # -- 下方的两个while,只会有一个执行!
    # 若左边还有数,将左边的数依次添加到临时列表temp中
    while i <= mid:
        temp.append(li[i])
        i += 1
    # 若右边还有数,将右边的数依次添加到临时列表temp中
    while j <= high:
        temp.append(li[j])
        j += 1
    # -- 将temp列表里的值写回到li列表中
    li[low:high + 1] = temp  # 利用切片,切片可以往回写


if __name__ == '__main__':
    li = [2, 5, 7, 1, 3]
    merge(li, 0, 2, 4)
    print(li)  # [1, 2, 3, 5, 7]

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

# 递归使用归并

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

每次归并操作,时间复杂度都是O(n),可以理解成左边的i走完,右边的j走完,相当于将整个列表走了一遍..
而要进行多少次归并操作呢? 根据图示, 可以看到有2*logn次,时间复杂度为O(logn), 二叉折半了嘛.
So, 归并排序的时间复杂度为 O(nlogn).

# 归并操作
def merge(li, low, mid, high):
    i = low
    j = mid + 1
    temp = []
    while i <= mid and j <= high:
        if li[i] < li[j]:
            temp.append(li[i])
            i += 1
        else:
            temp.append(li[j])
            j += 1
    while i <= mid:
        temp.append(li[i])
        i += 1
    while j <= high:
        temp.append(li[j])
        j += 1
    li[low:high + 1] = temp


def merge_sort(li, low, high):
    # 思想: 跟汉诺塔的实现思想一样,不要管中间具体怎么实现的.保证有一个递归结束条件即可.
    # 有一个列表在这,分三步走,将其左边排好序,将其右边排好序.左右两边做归并.
    # Os:写起来很简单,但真的不好理解(つД`)ノ
    # -- low < high 满足该条件时,会有将列表长度折半,然后递归 递归的终止条件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)


if __name__ == '__main__':
    li = [10, 4, 6, 3, 8, 2, 5, 7]
    merge_sort(li, 0, len(li) - 1)
    print(li)  # [2, 3, 4, 5, 6, 7, 8, 10]

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

# NB三人组小结

三种排序算法的时间复杂度都是 O(nlogn), 比lowB三人组都要快..

一般情况下, 就运行时间而言:
快速排序 < 归并排序 < 堆排序
为啥时间复杂度一样, 运行有快慢之分, 因为将时间复杂度里常量给省略了..

三种排序算法的缺点:
     快速排序 - 极端情况下,排序效率低. 倒序的列表需要正向排序时,使用快排时间复杂度会达到n^2
     归并排序 - 需要额外的内存开销. 不是原地排序的.
     堆排序 - 在这三个排序算法中相对较慢.

排序算法	最坏	平均	最好	空间复杂度	稳定性	代码实现难易
冒泡	O(n^2)	O(n^2)	O(n)	O(1)	稳定	简单
选择	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定	简单
插入	O(n^2)	O(n^2)	O(n^2)	O(1)	稳定	简单
快速	O(n^2)	O(nlogn)	O(nlogn)	平均 O(logn) 最坏 O(n)	不稳定	较难
堆	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定	很难
归并	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定	较难

时间复杂度, 可以分为 最坏情况、平均情况、最好情况
冒泡排序,最好情况的时间复杂度为O(n) -- 已经排好序的列表进行排序,一趟之中不会发生交换,只需遍历一遍.
快速排序,最坏情况的时间复杂度为O(n^2) -- 倒序的列表使用快排进行排序.

注:快速排序还有一个空间复杂度. 快排不是原地排序的吗？
我们说,一个算法需要额外开辟一个列表,则该算法的空间复杂度为O(n);开辟一个n*n的二维列表,那空间复杂度为O(n^2).
还有一种情况需要用到空间,是递归!!递归需要系统占用的空间.
why?beacuse 递归中,函数需要一层一层的往下走,走到下一层时要存放上一层函数的位置.每走一层需要消耗O(1)的空间复杂度.
可以简单理解为一个系统记录递归过程中每一层函数位置的列表.
对快排而言,我们推导过,要递归走logn层,So,快排平均情况下要消耗O(logn)的空间复杂度!
当快排处于最坏的时间复杂度O(n^2)时,要走n层,So,快排最坏情况下要消耗O(logn)的空间复杂度!

对归并而言,该算法的实现已经格外开了一个列表啦O(n).其递归需要的空间复杂度为O(logn).  O(n)+O(logn) logn被省略啦!

★ 排序的稳定性是很重要的!! -- 当两个元素值一样的时候,保证它们的相对位置不变!
比如,对[3,2,1,2,4]排序,稳定的排序能保证排序后原列表中第一个2依旧在原列表的第二个2的前面..
有所谓吗?有.比如对字典的排序.
{"name":'a',"age":18}
{"name":'b',"age":20}
{"name":'a',"age":25}
按照键`name`进行排序.
稳定的排序,排序后,能保证{"name":'a',"age":18}依旧在{"name":'a',"age":25}前面!!!不稳定的排序不能保证这一点.
如何判断一个排序算法是否稳定: 
  有顺序的挨个换的,稳定; -- 如何保证的呢?遇到值一样,不换就行.
  不挨个换,飞着换的,不稳定. -- 保证不了,跳着换,中间可能会有一样的. eg:[2,3,2,1,4] 第一个2和1交换,两个2的相对位置就变了.
Python的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

← LowB三人组其它排序→