算法思想及排序算法的实现与对比

Algorithm

算法思想及排序算法的实现与对比

循环和递归

​ 递归即大问题分解成小问题，但递归通常效率较低，通常表现为时间， 空间 均效率低下。

​ 递归时由于重复调用方法自身，每次调用方法时皆需在内存栈中分配空间以保存参数，返回地址及临时变量 因此需大量空间，而压栈弹栈皆需要时间。

​

​ 写递归代码切忌人脑模拟电脑思考进栈出栈细节。

​ 只需确认三点：

​ 终止条件 + 函数功能 + 函数方程；

​ 此外思考函数方程时，也需注意终止条件中的返回值是什么。

​

​ 同时， 别太死板的觉得 终止条件一定要 “同时包含互斥条件的两方”， 例如 offer 13. 只需判断当前格子不可选时，return 0即可。 无需包含 当前格子是最后一 个可选的时返回1， 观察函数方程即可理解。

动态规划

​ 特点：

​ （1）某个问题可以分解成小问题 ，并且所问为求最优解（关于是否要求最优解不绝对 ）。

​ （2）把小问题的最优解组合起来能得到整体最优解，则通常可用动态规划。

​ （3） 小问题之间有重叠的子问题（即如果用递归则需要算很多重复的值）。

​ 分析动态规划时的思考方式与递归类似，因为都是大问题分解小问题。

​ 动态规划则为自上而下 方式思考解体思路。而用代码实现时则用自下而上 的方式解决问题，同时利用数据存储小问题的解然后组合小问题的解以得到整个问题的解， 熟练后可抛弃数组，仅用几个变量 存储有用的解

贪心

​ 若某个问题用动态规划的思路思考以后， 发现分解子问题时存在某种特定条件能使得结果一定为最优解， 则此时应思考贪心算法

回溯

可理解为有剪枝的穷举，其从解决问题每一步的多个选项里系统的选择一个可行的方案。

适合用于解决有多个步骤组成，且每个步骤有多个选项的问题。

回溯法解决问题的过程，可以近似理解为“遍历”一颗树的过程。 树中的每一个level 即一个步骤，每个node即一个选项。

当遍历至一个节点时，发现结果已不可能满足条件，则可放弃该节点返回至上一层节点。

同理，若发现一个节点的所有子节点均不满足条件时，则同样返回至上一层节点。

而返回至上一层节点时，若发现上一层中所有节点均已被遍历过，则再次返回至上一层节点。

如果所有节点（即路径）均已遍历且无符合条件的路径，则r

对于在二维数组中搜索路径的问题，如迷宫或棋盘，以及搜索可行解的问题，则通常可用回溯法。 而回溯法通常可用递归的方式求解。 递归又可用栈来实现。

查找算法

顺序查找
二分查找

对于在一个排序的，或部分排序的数组中查找一个数字，或统计一个数字出现的次数的问题，均可尝试使用二分查找

哈希查找

优： 效率最高， 时间复杂度O(1)

缺： 空间效率较低，需额外空间维护哈希表

二叉排序树查找（即二叉查找树）

排序算法

Code and Commitment:

冒泡排序

空间复杂度O(1)

时间复杂度：

最低O(n): 即input is already sorted

最高O(n^2): input is fully reversed

平均： 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
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
def bubble_sort(nums: List) -> List:
    """
    # wrong answer writen in 2021-11-29

    for i in range(len(nums)-1, 0):
        for j in range(len(nums)-1, i):
            if nums[j] < nums[j - 1]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]

    冒泡排序：
        冒泡排序每次交换相邻的两个元素
        每次循环结束后， 最大或最小的元素均被挪动至数组结尾，因此， “循环条件为每次上层循环结束后，下层循环的终点应右移”
        上述错误产生原因在与对第一层循环i的理解有误， i的作用是使第二曾循环j的终点至右移， 因为i每加1， 则意味着有 1 个元素已经被
        放置在正确位置， 也即数组的后i个元素已经排好序无需在比较

    """

    if len(nums) == 0:
        return nums

    for i in range(0, len(nums) - 1):
        for j in range(0, len(nums) - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

    return nums


def bubble_sort_optimized(nums):
    """
        原版本代码对于一个已排序的数组，依旧需循环 n + n-1 + n-2 + ... 次， which is unefficient
        可加入标志为实现对于一个已排序的数组，时间复杂度为O(n)
        关于标志位：
        即记录每次内层循环中是否发生换位，如果没发生，则代表每两个数据间大小顺序均已符合条件，即数组已排好序
    :param nums:
    :return:
    """
    if len(nums) == 0:
        return nums
    for i in range(0, len(nums) - 1):
        no_swap = True
        for j in range(0, len(nums) - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                no_swap = False
        if no_swap is True:
            break

    return nums

插入排序

时间复杂度总是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
24
25
26
27
28
29
def insert_sort(nums) -> List:
    """
        Overall, insertion sort virtually divide the array into two parts: sorted part and unsorted part
        It get one of elements in unsorted part every time and insert it into the right position of sorted part
        During the insertion process, we need to move the elements in sorted part to make space for the newly inserted one
        E.g. sorted part:
        index:    0, 1, 2, 3, 4
        element:  1, 3, 4, 5, 6      to be inserted: 2

        Then:
        index:    0, 1, 2, 3, 4, 5
        element:  1,  , 3, 4, 5, 6

    """
    if len(nums) <= 1:
        return nums

    # i 的左侧为已经排好序的元素， 右侧为未排序元素
    # 每当i右移1位，则取一个未排序元素并将其插入i的左侧为其排序
    # i的值从1开始
    for i in range(1, len(nums)):
        current = nums[i]
        j = i
        while current < nums[j-1] and j >= 1:
            # 已排序元素右移为新元素腾位置
            nums[j] = nums[j-1]
            j -= 1
        nums[j] = current
    return nums

快速排序

平均时间复杂度： O(nlogn)

最佳： O(nlogn)

最坏： O(n^2)

快排的复杂度好坏取决于pivot的选取，而因为一般实现快排时通常选取最左或最有的元素为pivot，因此在这种情况下，当输入数组为完全倒序时时间复杂度最坏，为O(n^2)

Specifically, 当pivot总是为数组正中的元素时，那么时间复杂度最佳，为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
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
def quick_sort(nums: List) -> List:
    """
    快排的关键即为pivot找位置
    pivot：
    可以选取任意元素为pivot
    pivot左侧皆比其小，右侧皆比其大

    为pivot选好位置后，即可将pivot左右两侧的数据分为两个数组（pivot无需再包括在其中）
    然后对两个sub arrays 进行同样操作即可


    注意理解quick_sort_recursive的终止条件
    e.g. [1,3,2] ==> pivot = index1 ==> left array = [1], right array = [2]
    以[1] 为例， 此时[1] 调用partition后返回的pivot index 为0，
    此时再传参至下列代码时
    quick_sort_recursive(left, pivot_index - 1, li)
    quick_sort_recursive(pivot_index + 1, right, li)
    left = 0, right = -1;
    left = 1, right = 0
    触发终止条件
    """
    def partition(left, right, li):
        pivot = li[left]
        while left < right:

            # 之所以加上left < right 的条件，是为了防止始终没找到符合条件的元素
            # 比如到了index 0 还比pivot大， 再减1 则会变-1， 访问li[-1] 便会报错
            while left < right and li[right] >= pivot:
                right -= 1
            # 至此，找到了比pivot小的元素， 所以应将其移到左侧，在第一次循环时， left指针指向的值为pivot，
            # 当使left = right时， 数组中重复了一个right指针指向的元素，丢失了pivot
            # 但是pivot的值已经保存在pivot变量中，所以最后会被还原
            li[left] = li[right]
            while left < right and li[left] <= pivot:
                left += 1
            # 而当程序运行至此，数组中重复的right值会被消除，因为此时right指针没动，还指向原本right值的位置，当进行此赋值操作时，
            # right值变成了left。 此时数组中又重复了一个left值
            li[right] = li[left]

        # 此时，left指针指向应该消除的重复的left值，并且此时left指针必定会移动到pivot应该所在的位置
        # 所以进行该赋值操作后，整个数组中元素没有重复，没有丢失，且pivot被转移到应在的位置
        li[left] = pivot
        return left

    def quick_sort_recursive(left, right, li):
        if left >= right:
            return
        pivot_index = partition(left, right, li)
        quick_sort_recursive(left, pivot_index - 1, li)
        quick_sort_recursive(pivot_index + 1, right, li)

    left = 0
    right = len(nums) - 1

    quick_sort_recursive(left, right, nums)
    return nums

归并排序

时间复杂度总是O(nlogn)

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
def merge_sort(nums) -> List:
    """
        归并即先将数组持续对半分，直到分解成单个元素
        再依次进行merge
        典型的分治思想
    """
    def merge(left: List, right: List):
        """
        2021-11-29
        错误代码：

        temp_result = []
        while len(n1) != 0 and len(n2) != 0:
            # 错误1.1：
            en1 = n1.pop(0)
            en2 = n2.pop(0)
            if en1 > en2:
                # 错误1.2：
                temp_result.append(en2)
                temp_result.append(en1)
            else:
                # 错误1：
                temp_result.append(en1)
                temp_result.append(en2)
        # 错误2
        temp_result.append(en1)
        temp_result.append(en2)
        return temp_result

        错1：
        根源在于，在merge时，有可能n1中的元素全部比n2中的小，即n1全部添加进了result以后n2才开始pop
        1.1 and 1.2 皆时assume n1， n2 必是轮流进一个， 即n1进一个后n2就进一个

        错2：
        此处以为添加剩余元素，不可直接append， 这样会使整个列表变成result中的一个元素，即[..., []] 而非 [...,...]

        """
        result = []
        while left and right:
            if left[0] < right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))

        result += left
        result += right
        return result

    def merge_sort_entry(nums):
        """
            merge_sort_entry 本身的函数功能 “仅仅为分解而已！” ， 看终止条件的设置即可理解。（写递归代码时需确定： 终止条件，函数功能，递归方程）
            merge排序的工作是merge function做的
        :param nums:
        :return:
        """
        if len(nums) == 1:
            return nums

        mid = len(nums)//2
        left = nums[:mid]
        right = nums[mid:]
        return merge(merge_sort_entry(left), merge_sort_entry(right))

    if len(nums) <= 1:
        return nums

    return merge_sort_entry(nums)