定义计算函数运行时长的装饰器

1
2
3
4
5
6
7
8
9
10
11
import time

def calcTime(func):

    def wrapper(*args, **kwargs):
        startTime = time.time()
        func(*args, **kwargs)
        endTime = time.time()
        print(f"函数{func.__name__}耗时为{endTime-startTime}s")

    return wrapper

冒泡排序（Bubble Sort）

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

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
import random
"""
冒泡排序
第一种实现方式是不稳定排序，当数组中存在两个相同的元素时，第一种实现方式可能会改变它们原本在数组中的顺序, 如下示例数组a中的元素2。故第一种实现在这里仅作为参照，不建议使用
bubbleSort2函数中，代码优化与否(加标志位判断)，在数据量较大的情况下，执行时间可能会有上千倍的差距
"""

@calcTime
def bubbleSort1(a: list, n: int):
    if n <= 1:
        return
    for i in range(n):
        for j in range(i, n):
            if a[i] > a[j]:
                a[i],a[j] = a[j],a[i]

@calcTime
def bubbleSort2(a: list, n: int):
    if n <= 1:
        return
    flag = False
    for i in range(n):
        for j in range(n-i-1):
            if a[j] > a[j+1]:
                a[j],a[j+1] = a[j+1],a[j]
                flag = True
        if not flag:
            break

插入排序（Insertion Sort）

首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
插入排序
思想：将数组分为已排序区间和未排序区间，取未排序区间的元素，在已排序区间找到合适的位置将其插入，并一直保持已排序区间数据有序，重复过程直到未排序区间元素为空，算法结束
过程涉及到元素比较和元素移动两种操作
"""

@calcTime
def insertionSort(a: list, n: int):
    if n <= 1:
        return
    for i in range(1, n):
        value = a[i]
        # 查找插入位置
        j = i - 1
        while j >= 0:
            if a[j] > value:
                a[j + 1] = a[j] # 数据移动
                j -=1
            else:
                break
        a[j+1] = value # 插入数据

选择排序（Selection Sort）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
选择排序
思想：选择排序和插排类似，也是将数组分为已排序区间和未排序区间，但不同的是，选择排序每次会从未排序区间找到最小的元素。将其放到到已排序区间的末尾
选择排序是一种不稳定的排序算法，因为每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。
比如 [5,8,5,2,9] 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。
"""

@calcTime
def selectionSort(a: list, n: int):
    if n <= 1:
        return
    for i in range(n):
        value = a[i]
        index = i
        for j in range(i+1, n):
            if a[j] < value:
                value = a[j]
                index = j
        if index != i:
            a[index] = a[i]
            a[i] = value

测试代码

1
2
3
4
5
6
7
8
9
10
if __name__ == "__main__":
    a = [1, 2, 34, 2, 23, 77, 89, -4, 0, 121, 0, 33]
    b = [random.randint(-1000, 10000) for i in range(1000)]


    # bubbleSort1(b, len(b))
    # bubbleSort2(b, len(b))
    insertionSort(b, len(b))
    selectionSort(b, len(b))
    # print(b)