抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

python自学笔记（8）——10种排序方式的python实现

学习笔记编程自学

发布于：2023年7月4日

字数：7.2k 字

时长：30 分钟
次浏览

最近中期答辩结束，稍微有点空闲的时间捋一捋数据结构和算法方面的知识。虽然现在用python实现排序就一个sort()函数的事，但是还是想锻炼下自己的思维，从底层代码学习一下10种经典排序的实现方式。

对于时间复杂度和空间复杂度的计算，自己还是一知半解，每种排序方式后面放了自己的理解，有错误会继续修改，最后有一张菜鸟教程总结的图可以参考。

本篇笔记的内容主要是跟着b站up主做的，代码整理来自英雄哪里出来的个人空间

我这里先定义一个生成随机整数序列的函数，后面都会调用，就不重复写了：

1
2
3
4
5
6
7
8
import random

# 生成指定范围、长度的序列
def generate_random_sequence(len, min, max):
    seq = []
    for i in range(len):
        seq.append(random.randint(min, max))
    return seq

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
26
def SelectionSort(a):
    n = len(a)
    for i in range(n - 1): # 排完倒数第二个数之后就不用再排了，所以这里用n-1而不是n
        min = i
        for j in range(i + 1, n):
            if a[j] < a[min]:
                min = j
        a[i], a[min] = a[min], a[i]
        print(a)
a = generate_random_sequence(10, 1, 100)
print(a)
SelectionSort(a)

'''
输出结果：
[77, 76, 21, 51, 29, 23, 19, 68, 53, 37]
[19, 76, 21, 51, 29, 23, 77, 68, 53, 37]
[19, 21, 76, 51, 29, 23, 77, 68, 53, 37]
[19, 21, 23, 51, 29, 76, 77, 68, 53, 37]
[19, 21, 23, 29, 51, 76, 77, 68, 53, 37]
[19, 21, 23, 29, 37, 76, 77, 68, 53, 51]
[19, 21, 23, 29, 37, 51, 77, 68, 53, 76]
[19, 21, 23, 29, 37, 51, 53, 68, 77, 76]
[19, 21, 23, 29, 37, 51, 53, 68, 77, 76]
[19, 21, 23, 29, 37, 51, 53, 68, 76, 77]
'''

这个算法时间复杂度（算法中循环执行的次数，量级估算）为O(n^2)，其中n是输入序列的长度。空间复杂度（算法运行过程中临时占用存储大小，量级估算）为O(1)，因为它只需要使用常数级别的额外空间。

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
def BubbleSort(a):
    n = len(a)
    for i in range(n - 1, 0, -1):	# range()左闭右开，n-1可以取到右边界，逆序枚举
        for j in range(0, i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
        print(a)
a = generate_random_sequence(10, 1, 100)
print(a)
BubbleSort(a)

'''
输出结果：
[57, 86, 40, 11, 38, 46, 21, 38, 18, 6]
[57, 40, 11, 38, 46, 21, 38, 18, 6, 86]
[40, 11, 38, 46, 21, 38, 18, 6, 57, 86]
[11, 38, 40, 21, 38, 18, 6, 46, 57, 86]
[11, 38, 21, 38, 18, 6, 40, 46, 57, 86]
[11, 21, 38, 18, 6, 38, 40, 46, 57, 86]
[11, 21, 18, 6, 38, 38, 40, 46, 57, 86]
[11, 18, 6, 21, 38, 38, 40, 46, 57, 86]
[11, 6, 18, 21, 38, 38, 40, 46, 57, 86]
[6, 11, 18, 21, 38, 38, 40, 46, 57, 86]
'''

这个算法的时间复杂度为O(n^2)（最好的情况下数据本来有序，复杂度O(n)），其中n是待排序数组的长度。空间复杂度为O(1)，因为只使用了常数级别的额外空间。和选择排序算法是一样。

3. 插入排序

对前i-1个数已经有序的情况下，将第i个数插入到合适的位置。

将第二个元素和第一个元素比较，如果第二个元素小于等于第一个元素，则将第一个元素向后移动，并将第一个元素执行插入，这样前两个元素就是有序的。接着进行第二轮比较，也就是将第三个元素依次和第二元素和第一个元素比较，并插入到合适的位置，使前三个元素有序。以此类推，迭代执行n-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
26
27
def InsertionSort(a):
    n =len(a)
    for i in range(1, n):
        x = a[i]
        j = i - 1
        while j >= 0 and x <= a[j]:	# 若x<=a[j]，则将a[j]往后移动，继续判断前一个数
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
        print(a)
a = generate_random_sequence(10, 1, 100)
print(a)
InsertionSort(a)

'''
输出结果：
[95, 69, 37, 81, 21, 11, 53, 12, 22, 16]
[69, 95, 37, 81, 21, 11, 53, 12, 22, 16]
[37, 69, 95, 81, 21, 11, 53, 12, 22, 16]
[37, 69, 81, 95, 21, 11, 53, 12, 22, 16]
[21, 37, 69, 81, 95, 11, 53, 12, 22, 16]
[11, 21, 37, 69, 81, 95, 53, 12, 22, 16]
[11, 21, 37, 53, 69, 81, 95, 12, 22, 16]
[11, 12, 21, 37, 53, 69, 81, 95, 22, 16]
[11, 12, 21, 22, 37, 53, 69, 81, 95, 16]
[11, 12, 16, 21, 22, 37, 53, 69, 81, 95]
'''

这个算法的时间复杂度为O(n^2)，其中n是待排序数组的长度。空间复杂度为O(1)，因为只使用了常数级别的额外空间。

要改善选择排序的时间复杂度，可以考虑使用其他更高效的排序算法，例如快速排序（Quick Sort）或归并排序（Merge Sort）。这些算法的时间复杂度通常为O(nlogn)，比上面三个排序算法的O(n^2)更快。此外，还可以考虑使用内置的排序函数，如Python中的sorted()函数，它使用了优化的排序算法。如果待排序数组已经基本有序，可以通过引入一些优化措施来提高插入排序的性能，例如使用二分查找来确定插入位置，减少比较和交换的次数。

4. 归并排序

利用分治的思想，采用递归的形式，对元素进行排序。当有两个长度为n的有序数组时，可以通过两个指针的移动，在O(n)的时间复杂度内，快速合并成一个有序数组。而这两个长度为n的有序数组，也可以通过两个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
# 实现一个合并函数(a列表start到mid的元素，以及mid+1到end的元素，需要分别按照递增顺序排列)，执行后a列表start到end的元素也按照递增顺序排序
def Merge(a, start, mid, end):
    tmp = []
    l = start   # l和r是两个区间的起点
    r = mid + 1
    # 当两个区间都未到达右端点，判断a[l]和a[r]，小的值放入临时列表，下标自增
    while l <= mid and r <= end:    
        if a[l] <= a[r]:
            tmp.append(a[l])
            l += 1
        else:
            tmp.append(a[r])
            r += 1
    # 跳出循环时，剩余部分全部放入临时列表（因为跳出循环表示一个列表已经排完了，另一个列表剩下的也是有序的）
    tmp.extend(a[l : mid + 1])  
    tmp.extend(a[r : end + 1])
    # 临时列表值拷贝回原列表a，完成一次合并
    for i in range(start, end + 1):
        a[i] = tmp[i - start]
    print(start, end, tmp)

# 实现一个递归函数（作用是拆分子数组）
def MergeSort(a, start, end):
    # 待排序元素只有一个则返回
    if start == end:
        return
    # 计算中点mid，整数除法，向下取整
    mid = (start + end) // 2
    MergeSort(a, start, mid)
    MergeSort(a, mid + 1, end)
    # 两次调用MergeSort()产生两个有序数组，之后对两个有序数组进行Merge()合并
    Merge(a, start, mid, end)

a = generate_random_sequence(10, 1, 100)
print(a)
MergeSort(a, 0, 9)

'''
输出结果：
[92, 87, 91, 24, 5, 36, 76, 62, 66, 89]
0 1 [87, 92]
0 2 [87, 91, 92]
3 4 [5, 24]
0 4 [5, 24, 87, 91, 92]
5 6 [36, 76]
5 7 [36, 62, 76]
8 9 [66, 89]
5 9 [36, 62, 66, 76, 89]
0 9 [5, 24, 36, 62, 66, 76, 87, 89, 91, 92]
'''

其实也可以不用递归的方法，用迭代的方式来实现归并排序：

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
# 实现一个合并函数
def merge(arr, start, mid, end, temp):
    i = start
    j = mid
    k = start
    while i < mid and j < end:
        if arr[i] < arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            j += 1
        k += 1
    while i < mid:
        temp[k] = arr[i]
        i += 1
        k += 1
    while j < end:
        temp[k] = arr[j]
        j += 1
        k += 1
        
# 实现一个拆分子数组和合并的函数
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    # 创建一个临时数组用于存储排序结果
    temp = [0] * len(arr)
    # 设置初始步长为1
    step = 1
    while step < len(arr):
        # 按照步长将数组分为多个子数组进行合并
        for start in range(0, len(arr), 2 * step):
            # 计算子数组的起始索引、中间索引和结束索引
            mid = min(start + step, len(arr))
            end = min(start + 2 * step, len(arr))
            # 合并两个子数组
            merge(arr, start, mid, end, temp)
        # 将临时数组的结果复制回原始数组
        arr[:] = temp[:]
        # 增加步长
        step *= 2
        print(arr)
    return arr

arr = generate_random_sequence(10, 1, 100)
print(arr)
sorted_arr = merge_sort(arr)

'''
输出结果：
[65, 50, 64, 33, 58, 7, 97, 87, 92, 52]		（原序列）
[50, 65, 33, 64, 7, 58, 87, 97, 52, 92]		（步长2）
[33, 50, 64, 65, 7, 58, 87, 97, 52, 92]		（步长4）
[7, 33, 50, 58, 64, 65, 87, 97, 52, 92]		（步长8）
[7, 33, 50, 52, 58, 64, 65, 87, 92, 97]		（最终序列）
'''

在这个实现中，使用了一个临时数组temp来存储排序的结果。首先，设置初始步长为1，然后在每一轮迭代中，按照步长将原始数组分为多个子数组，并调用merge函数将这些子数组进行合并。合并后的结果存储在临时数组temp中。最后，将临时数组的结果复制回原始数组。迭代的思想在于通过不断迭代地合并子数组，直到得到完整的有序数组。

归并排序的时间复杂度是O(nlogn)，其中n是待排序数组的大小。空间复杂度是O(n)，因为在每次合并操作中需要创建一个临时列表来存储合并后的结果。

时间复杂度的算法可以参考如何计算归并排序算法的时间复杂度？

空间复杂度的算法可以参考归并排序的空间复杂度

5. 桶排序

生成一些桶，让数字散列在不同桶中，对桶中元素分别执行排序，再将元素依次取出。

比如建立4个桶，遍历所有数字并依次分散到4个桶中，保证第2个桶所有数字都大于第1个桶，第3个桶所有数字都大于第2个桶。每个桶中分别进行选择排序，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
# 确定桶内排序方法（这里用选择排序）
def SelectionSort(a):
    n = len(a)
    for i in range(n - 1): 
        min = i
        for j in range(i + 1, n):
            if a[j] < a[min]:
                min = j
        a[i], a[min] = a[min], a[i]

def BucketSort(a):
    # 确定列表元素最小值和最大值，定义桶数量
    minV = min(a)
    maxV = max(a)
    bucketCount = 3		# 桶的数量
    bucket = [[], [], []]
    # 计算每个桶的范围
    perBucket = (maxV - minV + bucketCount) // bucketCount
	# 遍历列表每个元素，计算该元素放入的桶的索引，并且放入相应桶中
    for num in a:
        bucketIndex = (num - minV) // perBucket
        bucket[bucketIndex].append(num)
    # 遍历每个桶，对每个桶的元素进行选择排序
    for i in range(bucketCount):
        SelectionSort(bucket[i])
    
    idx = 0
    # 遍历每个桶，遍历桶中元素，将元素放回原列表
    for i in range(bucketCount):
        for v in bucket[i]:
            a[idx] = v
            idx += 1
    print(bucket)
    print(a)
    
a = generate_random_sequence(10, 1, 100)
print(a)
BucketSort(a)

'''
输出结果：
[84, 66, 53, 83, 22, 15, 95, 6, 32, 70]
[[6, 15, 22, 32], [53], [66, 70, 83, 84, 95]]
[6, 15, 22, 32, 53, 66, 70, 83, 84, 95]
'''

桶的数量可以根据待排序元素的分布情况和排序的要求来决定，一般将待排序的元素均匀分配到桶中，桶内的排序算法可以是任意一种排序算法，取决于应用场景和性能要求。这个算法挺有意思的，可以看到每个桶的元素数量不一定一样，桶排序一般不会直接用，往往会做变形。

这个桶排序算法的时间复杂度为O(n + k^2)，其中n是待排序元素的数量，k是桶的数量。具体来说，遍历列表并将元素放入桶中的时间复杂度为O(n)，对每个桶进行选择排序的时间复杂度为O(k^2)，遍历每个桶并将元素放回原列表的时间复杂度为O(n)。因此，总的时间复杂度为O(n + k^2)，也就是O(n)。

空间复杂度方面，除了原始列表外，额外使用了一个大小为k的桶列表来存储元素。因此，空间复杂度为O(n + k)，也就是O(n)。

6. 计数排序

利用哈希表的思想，对数据类型和范围有要求。

首先生成一个计数器数组，并且一开始所有值的计数都为0，然后遍历枚举原数组的所有元素，在元素值对应的计数器上执行计数操作。最后遍历枚举计数器数组，按照数组中元素个数放回到原数组中，这样所有元素都是升序排列了。

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 CountingSort(a):
    n = len(a)
    # 获取原数组中最大值，加1，作为计数器列表的实际长度
    cntlen = max(a) + 1
    # 生成一个值都为0的计数器列表
    cnt = [0] * cntlen
    # 遍历枚举原数组所有元素，在对应的计数器上加1
    for val in a:
        cnt[val] += 1
    print(cnt)
    n = 0
    # 遍历枚举计数器列表，cnt[val]代表val这个数有多少个，大于0，则将它的计数器减一，并放到原来的列表中。如果还有则继续迭代至计数为0
    for val in range(0, cntlen):
        while cnt[val] > 0:
            cnt[val] -= 1
            a[n] = val
            n += 1

a = generate_random_sequence(10, 1, 20)
print(a)
CountingSort(a)
print(a)

'''
输出结果
[8, 14, 18, 13, 16, 17, 7, 10, 8, 15]		（原列表）
[0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1]		（计数器列表）
[7, 8, 8, 10, 13, 14, 15, 16, 17, 18]		（计数排序后的列表）
'''

很明显，这种排序方式对数据有较大的限制，适用于数据范围较小的非负整数，且数据分布较均匀的情况（并不是说负数就完全不能用）。这很好理解，数据范围太广，会导致计数数组很大，占用大量内存空间，如果数据分布不均匀，计数的效率也会降低。

本质上来说这种计数排序算法是一种简单的桶排序算法，一个计数器就是一个桶。计数排序算法**时间复杂度是O(n)，空间复杂度是O(n)**。

7. 基数排序

和上面的计数排序很像，本质上也是桶排序，只不过用数位来划分桶。

首先建立0-9的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
def RadixSort(a):
    base = 1		# base为取的数位
    maxv = max(a)
    # 从低到高遍历每个数位
    while base < maxv:	
        bucket = []
        # 每次遍历定义10个桶
        for idx in range(10):	
            bucket.append([])
        # 每个原列表元素根据当前数位放入对应的桶中
        for num in a:
            idx = num // base % 10		# //向下取整，%除法取余
            bucket[idx].append(num)
        l = 0
        # 遍历每个桶，按顺序放回原列表
        for idx in range(10):
            for v in bucket[idx]:
                a[l] = v
                l += 1
        print(a)
        base *= 10

a = generate_random_sequence(10, 1, 1000)
print(a)
RadixSort(a)

'''
输出结果：
[119, 13, 832, 247, 117, 126, 996, 904, 112, 396]		（原序列）
[832, 112, 13, 904, 126, 996, 396, 247, 117, 119]		（按照个位数放入桶中，遍历取出）
[904, 112, 13, 117, 119, 126, 832, 247, 996, 396]		（按照十位数放入桶中，遍历取出）
[13, 112, 117, 119, 126, 247, 396, 832, 904, 996]		（按照百位数放入桶中，遍历取出）
'''

上面的代码只适用于正整数，我们通过循环遍历每个数位，所以外层循环的次数是位数d。内层循环中，我们遍历了待排序数组并将每个元素放入对应的桶中，所以内层循环的时间复杂度是O(n)。最后，我们遍历每个桶，按顺序将元素放回原列表，这也需要O(n)的时间复杂度。

总的来说，基数排序的时间复杂度为O(d * (n + k))，其中d表示位数，n表示待排序数组的长度，k表示桶的数量。空间复杂度为O(dk+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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def RadixSort(a):
    # 分离正数和负数
    positive_nums = [num for num in a if num >= 0]
    negative_nums = [-num for num in a if num < 0]
    # 对正数部分进行基数排序
    if len(positive_nums) > 0:
        base = 1
        maxv = max(positive_nums)
        while base < maxv:
            bucket = [[] for _ in range(10)]
            for num in positive_nums:
                idx = num // base % 10
                bucket[idx].append(num)
            positive_nums = [v for bucket_list in bucket for v in bucket_list]
            print(positive_nums)
            base *= 10
    # 对负数部分进行基数排序
    if len(negative_nums) > 0:
        base = 1
        maxv = max(negative_nums)
        while base < maxv:
            bucket = [[] for _ in range(10)]
            for num in negative_nums:
                idx = num // base % 10
                bucket[idx].append(num)
            negative_nums = [v for bucket_list in bucket for v in bucket_list]
            print(negative_nums)
            base *= 10
    # 将负数部分反转
    negative_nums = [-num for num in negative_nums[::-1]]
    print(negative_nums)
    # 合并正数和负数部分
    sorted_a = negative_nums + positive_nums
    return sorted_a

a = generate_random_sequence(10, -1000, 1000)
print(a)
a = RadixSort(a)
print(a)

'''
输出结果：
[-918, -574, 385, -322, -164, 880, -158, -400, 607, -746]		(原序列)
[880, 385, 607]
[607, 880, 385]
[385, 607, 880]		（基数排序后的正数序列）
[400, 322, 574, 164, 746, 918, 158]
[400, 918, 322, 746, 158, 164, 574]
[158, 164, 322, 400, 574, 746, 918]		（基数排序后取反的负数序列）
[-918, -746, -574, -400, -322, -164, -158]		（反转的成原来的负数序列）
[-918, -746, -574, -400, -322, -164, -158, 385, 607, 880]	（整合排序后的结果）
'''

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
# 从a列表start到end之间寻找基准数下标，并且将所有小于等于它的数放在它左边，大于它的数放在右边
def QuickSortPivot(a, start, end):
    pivot = start   # 最左边数为基准数
    j = start + 1   # j代表大于基准数的数的下标左边界
    # 遍历列表所有数，如果当前数小于等于基准数，则a[i]和a[j]交换，j自增；大于则不处理（保证j下标以前的数小于等于基准数）
    for i in range(start + 1, end + 1):
        if a[i] <= a[pivot]:
            a[i], a[j] = a[j], a[i]
            j += 1
    # 遍历之后，基准数与小于基准数的最后一个数交换（这样就可以让基准数左边和右边分开，且基准数位置就是正确的了）
    a[pivot], a[j - 1] = a[j - 1], a[pivot]
    # 更新基准数下标
    pivot = j - 1 
    print(a[pivot], a[start : pivot], a[pivot + 1 : end + 1])
    return pivot

# 快速排序函数，用来对区间[start, end]的数递归执行快速排序
def QuickSort(a, start, end):
    if start >= end:
        return
    # 获得基准数下标，分别递归计算左边和右边部分
    pivot = QuickSortPivot(a, start, end)
    QuickSort(a, start, pivot - 1)
    QuickSort(a, pivot + 1, end)

a = generate_random_sequence(10, 1, 100)
print(a)
QuickSort(a, 0, 9)
print(a)

'''
输出结果：
[55, 100, 41, 99, 52, 90, 50, 71, 92, 44]		# 原序列
55 [44, 41, 52, 50] [90, 99, 71, 92, 100]		# 基准数，基准数左边序列，基准数右边序列
44 [41] [52, 50]
52 [50] []
90 [71] [99, 92, 100]
99 [92] [100]
[41, 44, 50, 52, 55, 71, 90, 92, 99, 100]		# 快速排序后的序列
'''

这种排序算法也有一个缺点，如果很不巧每次选取的基准点都是序列的最大值或者最小值，那么时间复杂度将会是最大值O(n^2)。

时间复杂度：

  • 在每一次划分操作中，需要遍历待排序数组的所有元素，这需要O(n)的时间。
  • 在每一次划分操作中，将数组划分为两个子数组，每个子数组的长度大约是原数组的一半（最好的情况）。因此，划分操作的时间复杂度为O(n)。
  • 快速排序的递归深度为logn，因为每次划分操作都将数组的规模减半。
  • 因此，最好的情况下时间复杂度为O(nlogn)，最坏情况下时间复杂度为O(n^2)。

空间复杂度：

  • 快速排序使用递归调用来对子数组进行排序，每次递归调用都需要保存当前的函数调用信息（包括参数、局部变量等）。
  • 快速排序的递归深度通常为logn，因此需要的栈空间也是logn。
  • 因此，总的空间复杂度为O(logn)。最坏的情况下是O(n)，随机化基准值pivot可以防止最坏情况发生。

可以用随机快速排序，每次找基准点采用了一次随机，规避快速排序最坏的情况发生。

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
import random

def QuickSortPivot(a, start, end):
    # 引入区间中随机一个元素的索引值，和最左边的数交换（本来是最左边的数作为下一轮的基准数）
    randIdx = random.randint(start, end)
    a[start], a[randIdx] = a[randIdx], a[start]
    
    pivot = start  
    j = start + 1  
    for i in range(start + 1, end + 1):
        if a[i] <= a[pivot]:
            a[i], a[j] = a[j], a[i]
            j += 1
    a[pivot], a[j - 1] = a[j - 1], a[pivot]
    pivot = j - 1 
    print(a[pivot], a[start : pivot], a[pivot + 1 : end + 1])
    return pivot

def QuickSort(a, start, end):
    if start >= end:
        return
    pivot = QuickSortPivot(a, start, end)
    QuickSort(a, start, pivot - 1)
    QuickSort(a, pivot + 1, end)
    
a = generate_random_sequence(10, 1, 100)
print(a)
QuickSort(a, 0, 9)
print(a)

'''
输出结果：
[24, 2, 44, 75, 32, 32, 68, 36, 9, 79]
68 [9, 2, 44, 32, 32, 24, 36] [75, 79]
36 [9, 2, 32, 32, 24] [44]
9 [2] [32, 32, 24]
24 [] [32, 32]
32 [32] []
79 [75] []
[2, 9, 24, 32, 32, 36, 44, 68, 75, 79]
'''

9. 希尔排序

本质是一种改进后的插入排序，又称“缩小增量排序”，增量在这里是指按照一定规则选择的间隔值（这里也是分组数），通常设置为数组长度的一半，每次缩小增量直到增量为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
26
27
28
29
30
def ShellSort(a):
    n = len(a)
    # gap为增量，每隔gap值执行插入排序
    gap = n // 2    
    while gap > 0:
        for i in range(gap, n):
            x = a[i]
            j =i
            while j >= gap:
                if x < a[j - gap]:
                    a[j] = a[j - gap]
                else:
                    break
                j -= gap
            a[j] = x
        print(a)
        # 增量除2向下取整，继续迭代
        gap = gap // 2

a = generate_random_sequence(10, 1, 100)
print(a)
ShellSort(a)

'''
输出结果：
[20, 17, 75, 69, 34, 85, 38, 23, 57, 28]		# 原序列
[20, 17, 23, 57, 28, 85, 38, 75, 69, 34]		# 第一次希尔排序，实际分了5组[20,85][17,38][75,23][69,57][34,28]并组内进行了插入排序
[20, 17, 23, 34, 28, 57, 38, 75, 69, 85]		# 第二次希尔排序，实际分了2组[20,23,28,38,69][17,57,85,75,34]并组内进行了插入排序
[17, 20, 23, 28, 34, 38, 57, 69, 75, 85]		# 第三次希尔排序，实际就是1组，所有组内元素插入排序
'''

希尔排序的时间复杂度是根据增量序列的选择而变化的。在最坏情况下（原序列为逆序），时间复杂度是O(n^2)；最好的情况下（原序列本身有序），时间复杂度是O(n)。平均情况下，希尔排序的时间复杂度可以达到O(nlogn)。

希尔排序的空间复杂度是O(1)，即不需要额外的空间来存储数据。希尔排序是一种原地排序算法，它通过交换元素的位置来实现排序，不需要额外的辅助数组或链表。因此，希尔排序的空间复杂度是常数级别的。

10. 堆排序

堆是一颗完全二叉树，假设一个节点编号为idx，则左子树树根编号为idx*2，右子树树根编号为idx*2+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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 实现大顶堆下沉操作，heap整个顺序表start到end之间组成合法的堆，start为根结点坐标
def maxHeapify(heap, start, end):
    son = start * 2     # 左子树根
    # 左子树存在，则取左子树和右子树根中的大者的下标，存储到son中
    while son <= end:
        if son + 1 <= end and heap[son + 1] > heap[son]:
            son += 1
        # 如果结点点的值大于根结点的值，则将根结点和子结点交换（下沉），子结点迭代执行
        if heap[son] > heap[start]:
            heap[start], heap[son] = heap[son], heap[start]
            start, son = son, son * 2
        # 如果子结点的值小于等于根结点的值，说明堆构造没问题，跳出循环
        else:
            break

# 实现堆排序操作
def HeapSort(a):
    # 堆下标从1开始，列表下标从0开始，所以在0的位置加上占位符None
    heap = [None] + a
    # 定义堆顶元素下标root为1
    root = 1
    l = len(heap)
    # 从顺序表l//2个元素开始(因为堆的最后一层是没有子结点的)逆序枚举，自底向上构造堆
    for i in range(l // 2, root - 1, -1):
        maxHeapify(heap, i, l - 1)
    # 堆顶和最后一个元素交换，除最后一个元素外，重构堆
    for i in range(l - 1, root, -1):
        heap[i], heap[root] = heap[root], heap[i]
        maxHeapify(heap, root, i - 1)
        print(heap[root:])

a = generate_random_sequence(10, 1, 100)
print(a)
HeapSort(a)

'''
输出结果：
[3, 52, 44, 78, 60, 100, 54, 61, 38, 1]		# 原数列
[78, 61, 54, 52, 60, 44, 3, 1, 38, 100]		# 最大数为100，1-9位重新构造大顶堆
[61, 60, 54, 52, 38, 44, 3, 1, 78, 100]		# 次大数为78，1-8位重新构造大顶堆
[60, 52, 54, 1, 38, 44, 3, 61, 78, 100]		# 第三大数为61，1-7重新构造大顶堆
[54, 52, 44, 1, 38, 3, 60, 61, 78, 100]				.
[52, 38, 44, 1, 3, 54, 60, 61, 78, 100]				.
[44, 38, 3, 1, 52, 54, 60, 61, 78, 100]				.
[38, 1, 3, 44, 52, 54, 60, 61, 78, 100]				.
[3, 1, 38, 44, 52, 54, 60, 61, 78, 100]				.
[1, 3, 38, 44, 52, 54, 60, 61, 78, 100]		# 最后一次构造大顶堆，只有一个最小元素1，此时数列已经升序排好
'''

堆排序的时间复杂度为O(nlogn)，n是待排序元素的数量，空间复杂度为O(1)，因为它是原地排序算法，不需要额外的空间来存储元素。

最后是一张来自菜鸟教程的排序算法总结图：

本文由Phantom创作，转载请注明出处

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://www.shelven.com/2023/07/04/a.html

更新于：2023年7月4日

python

欢迎小伙伴们留言评论~