[数据结构与算法] 我的数据结构与算法「排序算法」

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 我的数据结构与算法「排序算法」 -> 正文阅读

[数据结构与算法]我的数据结构与算法「排序算法」

文章目录

- 排序算法

排序算法

排序算法是将原本无序的序列重新排列成有序的序列的算法

排序算法大致分为 $5$ 类，交换类、插入类、选择类、归并类和桶相关类

排序算法执行过程中，在可预见使用不同的排序算法去排序不同的数据结构的序列，移动元素所需的时间复杂度与空间复杂度也是不同的，因此只分析排序算法的时间复杂度与空间复杂度。另外如果，待排序表中有两个元素 $R_i、R_j$ ，其对应的关键字 $key_i=key_j$ ，且在排序前 $R_i$ 在 $R_j$ 前面，如果使用某一排序算法排序后， $R_i$ 仍然在 $R_j$ 的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的，不稳定将增加额外的复杂度

交换类

冒泡排序

算法逻辑

假设待排序表长为 $n$ ，从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即 $A [i ? 1] > A [i]$ ），则交换它们，直到序列比较完成，称为一趟冒泡，结果将最小的元素交换到待排序列的第一个位置。下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素，每趟冒泡的结果把序列中的最小元素放到了序列的最终位置，这样最多做 $n ? 1$ 趟冒泡就能把所有元素排好序

算法实现

def bubble_sort(List):
    # 1. 原列表长度
    n = len(List)
    # 2. 依次两两比较
    for i in range(1, n):
        for j in range(0, n - i):
            # 3. 前者比后者大，则交换位置
            if List[j] > List[j + 1]:
                List[j], List[j + 1] = List[j + 1], List[j]
    return List


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = bubble_sort(List)
    print(result)

空间复杂度，交换时开辟了存储空间来存储中间变量，所以为 $O (1)$
时间复杂度为 $O(n^2)$
稳定性，因为关键字相等时，不存在交换，是所以稳定的

快速排序

算法逻辑

快速排序是一种基于分治法的排序方法。每一趟快排选择序列中任一个元素作为枢轴（pivot）通常选第一个元素，将序列中比枢轴小的元素都移到枢轴前边，比枢轴大的元素都移到枢轴后边

算法实现

def quick_sort(List):
    # 1. 原列表长度
    n = len(List)
    # 2. 若列表少于2个元素，返回当前列表（递归的结束条件）
    if n < 2:
        return List
    # 3. 选取基准值，这里选择首位元素，并将其从原列表中移除（因为要将剩下的元素分组）
    base = List[0]
    List.remove(base)
    # 3. 预先定义空列表，即基准值的左右两个列表
    left, right = [], []
    # 4. 遍历剩下的元素
    for value in List:
        if value >= base:
            # 大于等于基准值放右边
            right.append(value)
        else:
            # 小于基准值放左边
            left.append(value)
    # 5. 递归，将基准值放中间组合成已完成的有序列表
    return quick_sort(left) + [base] + quick_sort(right)


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = quick_sort(List)
    print(result)

时间复杂度，最好情况下，比如每次都均等二分左右部分则为 $O(nlog_n)$ ，待排序序列越无序，算法效率越高。最坏情况下，比如，全是 $1$ 则为 $O(n^2)$ ，待排序序列越有序，算法效率越低
空间复杂度，由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为 $O(log_2n)$ 即递归树的深度是 $log_2(n+1)?$ 。最坏情况下，因为要进行 $n ? 1$ 次递归调用，所以栈的深度为 $O (n)$
稳定性，因为关键字相等时，存在交换，所以是不稳定的

插入类

直接插入排序

算法逻辑

将原列表第一个元素固定，当成是已排序列表，剩下的所有元素组成待排序列表，从第二个元素开始，从后往前遍历已排序列表并进行比较，插入到顺序合适位置，重复上一步骤，直到所有元素都插入有序序列

算法实现

def insert_sort(List):
    # 1. 原列表长度
    n = len(List)
    # 2. 依次遍历“待排序列表”（即原列表第2个元素开始）
    for i in range(1, n):
        # 当前待排序元素的值
        current = List[i]
        # “已排序列表”中最后一个元素的位置索引（相较于原列表）
        index = i - 1
        # 3. 从后往前遍历“已排序列表”
        while index >= 0 and current < List[index]:
            # 若小于，则交换值，继续往前遍历
            List[index + 1], List[index] = List[index], current
            index -= 1
    return List


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = insert_sort(List)
    print(result)

时间复杂度为 $O (n)$
空间复杂度为 $O (1)$
稳定性，因为关键字相等时，不存在交换，是所以稳定的

希尔排序

算法逻辑
希尔排序本质上是插入排序，不过是把待排序序列分成几个子序列，再分别对这几个子序列进行直接插入排序
1. 先以增量 $d$ （一般取序列长度的一半）来分割序列，也就是索引为 $0,d,2d,3d,\cdots$ 的元素分成一组，索引为 $1,d+1,2d+1,3d+1,\cdots$ 的元素分成一组等等，然后对这些组分别进行插入排序，就完成了一轮希尔排序
2. 接着缩小增量 $d$ ，比如设为 $\frac{d}{2}$ 再执行一次类似过程
3. 接下来不断重复 $2$ 直到最后一轮的增量为 1。此时就是直接插入排序

算法实现

def shell_sort(List):
    # 1. 原列表长度
    n = len(List)
    # 2. 首轮排序设置的间隔增量
    h = int(n / 2)

    # 3. 循环分组
    while h >= 1:
        # 4. 循环每一组子列表
        for i in range(h, n):
            # 当前待排序元素的值
            current = List[i]
            # “已排序列表”中最后一个元素的位置索引（相较于原列表）
            index = i
            # 5. 每一组子列表分别进行插入排序
            while index >= h and current < List[index - h]:
                # 若小于，则交换值，继续往前遍历
                List[index], List[index - h] = List[index - h], current
                index -= h
        # 6. 间隔增量缩小一半，继续循环，直到 h=1 再整体进行最后一次插入排序
        h = int(h / 2)
    return List


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = shell_sort(List)
    print(result)

时间复杂度，最好情况下约为 $O(n^{1.3})$ ，最坏情况下为 $O(n^2)$
空间复杂度为 $O (1)$
稳定性，因为不同的增量可能就会把相等的关键字划分到两个直接插入排序中进行排序，可能就会造成相对顺序变化，所以是不稳定的

选择类

简单选择排序

算法逻辑

从头开始，依次遍历列表，找到最小元素，选择它交换到待排序列表的最前面。每次都将产生 $1$ 个最小元素排在最前，该元素不再参与下一轮比较，相应剩余的元素作为新的待排序列表，不断重复

算法实现

def select_sort(List):
    # 1. 原列表长度
    n = len(List)
    # 2. 循环（n-1）轮排序
    for i in range(n - 1):
        # 3. 记下最小元素的位置索引，默认为每轮新的待排序列表的首位i
        min_index = i
        # 4. 循环寻找待排序列表中的最小元素的位置索引，并更新min_index
        for j in range(i + 1, n):
            if List[j] < List[min_index]:
                min_index = j
        # 5. 循环完元素后判断，若最小元素的位置索引min_index不是首位i，则交换元素
        if min_index != i:
            List[i], List[min_index] = List[min_index], List[i]
    return List


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = select_sort(List)
    print(result)

时间复杂度，关键操作在于交换元素操作，整个算法由双重循环组成，外层循环共 $n ? 1$ 次，对于第 $i$ 层外层循环，内层循环执行 $n ? 1 ? i$ 次。所以总执行次数是一个等差数列求和为 $\frac{n(n-1)}{2}$ 所以为 $O(n^2)$
空间复杂度，需要额外的存储空间仅为交换元素时借助的中间变量，所以空间复杂度是 $O (1)$
稳定性，因为最终会交换部分不必交换的元素的顺序，如 $5^*, 5, 1, 7$ 排序后变成了 $1,5,5^*,7$ ，所以不是稳定的

堆排序

算法逻辑

堆是一棵完全二叉树，而且小顶堆满足任何一个非叶结点的值都不大于其左右孩子结点的值（大顶堆则不小于左右孩子结点的值，一般升序采用大顶堆，降序采用小顶堆）因此，可将将原序列按顺序从上往下、从左往右的原则一个个元素插入，构建出一个堆。然后将其调整成大顶堆（所有孩子节点都与父结点比较，若大于父结点，则与父结点元素交换位置），最后将最大值即堆顶与堆尾元素交换，移除该最大值，此后得到的新堆，继续调整成大顶堆并交换堆顶与堆尾，不断重复

算法实现

# 堆排序
def heap_sort(List):
    build_heap(List)
    for i in range(len(List) - 1, -1, -1):
        List[0], List[i] = List[i], List[0]
        heapify(List, 0, i)
    return List

# 构建堆，列表中元素按顺序组成堆，故自然构成无需再做调整
def build_heap(List):
    lenght = len(List)
    # 从最后一个非叶子结点（是右结点）开始比较
    for i in range((lenght-1)//2, -1, -1):
        heapify(List, i, lenght)

def heapify(List, i, lenght):
    # 1. 找到节点的左右孩子节点
    left = i*2+1
    right = i*2+2    
    # 2. 判断左右孩子节点与父节点的大小，交换最大索引值
    if left < lenght and List[left] > List[i]:
        largest = left
    else:
        largest = i
    if right < lenght and List[right] > List[largest]:
        largest = right
    # 3. 若最大值节点的索引发生变化，则交换值
    if largest != i:
        List[i], List[largest] = List[largest], List[i]   
        # 4. 递归继续寻找最大值节点索引，因为可能左右孩子结点都比根结点大
        heapify(List, largest, lenght)


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = heap_sort(List)
    print(result)

时间复杂度，堆排序的总时间可以分为，构建堆与选择堆顶，为 $O(nlog_2n)=O(n)+O(nlog_2n)$
空间复杂度为 $O (1)$
稳定性，因为关键字相等时，存在交换，所以是不稳定的

归并类

归并排序

算法逻辑
假定待排序表含有 $n$ 个元素，则可以看成是 $n$ 个有序的子表，每个子表长度为 $1$ ，然后两两归并，得到 $? n / 2 ?$ 个长度为 $2$ 或 $1$ 的有序表；再两两归并，如此重复，直到合并成一个长度为 $n$ 的有序表为止

例如， $49, 38, 65, 97, 76, 13, 27$
1. 将整个序列的每个关键字看成一个单独的有序的子序列
2. 两两归并， $49$ 和 $38$ 归并成 ${38,49\}$ ， $65$ 和 $97$ 归并成 ${65,97\}$ ， $76$ 和 $13$ 归并成 ${13,76\}$ ， $27$ 没有归并对象
3. 两两归并， ${38,49\}$ 与 ${65,97\}$ 归并成 ${38, 49, 65, 97\}$ ， ${13,76\}$ 与 $27$ 归并成 ${13, 27, 76\}$
4. 两两归并， ${38, 49, 65, 97\}$ 与 ${13, 27, 76\}$ 归并成 ${13, 27, 38, 49, 65, 76, 97\}$

算法实现

def merge(left, right):
    """
    副程序：合并排序
    """
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))  # 每次消掉首位元素
        else:
            result.append(right.pop(0)) # 每次消掉首位元素
    while left:
        result.append(left.pop(0))  # 每次消掉首位元素
    while right:
        result.append(right.pop(0)) # 每次消掉首位元素
    return result

def merge_sort(List):
    """
    主程序
    """
    # 1. 原列表长度
    n = len(List)
    # 2. 若列表少于2个元素，返回当前列表（递归的结束条件）
    if n < 2:
        return List
    # 3. 拆分成左、右2个列表
    middle = n // 2
    left, right = List[0:middle], List[middle:]
    # 4. 返回递归结果
    return merge(merge_sort(left), merge_sort(right))


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = merge_sort(List)
    print(result)

时间复杂度为 $O(nlog_2n)$
空间复杂度，因为需要将这个待排序序列转存到一个数组，所以需要额外开辟大小为 $n$ 的存储空间为 $O (n)$
稳定性，因为关键字相等时，不存在交换，是所以稳定的

桶相关类

计数排序

算法逻辑

首先，找出原列表中最大值与最小值，初始化一个计数列表记录各个元素出现次数，然后，在原列表中，统计各个元素前比自己小的数的个数，然后输出（要求输入的数据必须是有确定范围的整数）

算法实现

def count_sort(List):
    # 1. 原列表长度
    n = len(List)
    # 2. 初始化一个尽量大长度的“计数列表”，用来统计原列表各个元素出现次数
    max_value = max(List)
    min_value = min(List)
    count_len = max_value - min_value + 1
    count_list = [0 for i in range(count_len)]
    # 3. 初始化一个最终“结果列表”
    res = [0 for i in range(n)]
    # 4. 遍历“原列表”，统计各元素出现次数，并记录在“计数列表”（只要是同一个元素就会出现在同一位置）
    for value in List:
        # 该元素与最小值的距离
        distance = value - min_value
        count_list[distance] += 1
    # 5. 遍历“计数列表”，每个元素前一位，增加到本元素中，“计数列表”即刻更新
    for j in range(1, count_len):
        count_list[j] = count_list[j] + count_list[j - 1]
    # 6. 遍历“原列表”，统计各个元素前比自己小的数的个数，然后输出
    for value in List:
        # 该元素与最小值的距离
        distance = value - min_value
        res[count_list[distance] - 1] = value
        count_list[distance] -= 1
    return res


if __name__ == '__main__':
	List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
  result = count_sort(List)
  print(result)

时间复杂度为 $O (n)$
空间复杂度为 $O (n)$
稳定性，因为关键字相等时，不存在交换，是所以稳定的

桶排序

算法逻辑

首先，初始化一个个空的桶列表用于存放元素，其次，每个桶等间距的涵盖一定的数值范围，按照数的大小把数据放到对应的桶中，最后，对每个不为空的桶中数据进行排序，按桶的顺序拼接得到结果（可以排序非整数）

算法实现

def bucket_sort(List):
    # 1. 原列表长度
    n = len(List)
    # 2. 初始化一个个空的“桶列表”
    min_value = min(List)
    max_value = max(List)
    bucket_len = (max_value - min_value) / n
    bucket_list = [[] for i in range(n + 1)]
    # 3. 遍历“原列表”，向“桶列表”压入元素
    for value in List:
        bucket_list[int((value - min_value) // bucket_len)].append(value)
    # 4. 声明一个返回的“结果列表”
    res = []
    # 5. 遍历“桶列表”，这里直接使用sorted排序，压入“结果列表”
    for i in bucket_list:
        for j in sorted(i):
            res.append(j)
    return res


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = bucket_sort(List)
    print(result)

时间复杂度，遍历了 $2$ 次原始数组，运算量为 $2 n$ ，最后，遍历桶输出排序结果的运算量为 $n$ ，初始化桶的运算量为 $m$ ，对每个桶进行排序时选择不同的排序算法运算量是不同的，若选取 $n^2$ 则最多为 $O(n)=O(2n)+O(m)+O(n)+O(m\cdot(\frac{n}{m})^2)$
空间复杂度为 $O (n) = O (n + m)$
稳定性，因为关键字相等时，不存在交换，是所以稳定的

基数排序

算法逻辑

不是基于比较进行排序的，而是基于关键字各位的大小进行排序的，依次从后往前比较其每一位上的大小，借助分配与收集两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先（MSD）排序和最低位优先（LSD）排序

对于 $53, 3, 542, 748, 14, 214, 154, 63, 616$ ，需要先补充位数 $053, 003, 542, 748, 014, 214, 154, 063, 616$ ，其中关键字数量为 $n$ ，关键字的位数为 $d$ ，比如 $748, d = 3$ ， $r$ 为关键字的基的个数，就是组成关键字的数据的种类，比如十进制数字一共有 $0$ 至 $9$ 一共 $10$ 个数字，即 $r = 10$

算法实现

def radix_sort(List):
    # 1. 记录初始排序的位置，为个位数
    index = 0
    # 2. “原列表”最大值
    max_value = max(List)
    # 3. 最大值的长度
    max_value_len = len(str(max_value))
    # 4. 循环按位数排序
    while index < max_value_len:
        # 5. 初始化一个空的[]“桶列表”
        bucket_list = [[] for i in range(10)]
        for value in List:
            # 6. 放入“桶列表”
            bucket_list[int(value / (10 ** index)) % 10].append(value)
        # 7. 清空“原列表”
        List.clear()
        # 8. 遍历“桶列表”元素，将元素放入“原列表”
        for x in bucket_list:
            for y in x:
                List.append(y)
        # 9. 位数+1
        index += 1
    return List


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = radix_sort(List)
    print(result)

时间复杂度，需要进行关键字位数 $d$ 次分配与收集，一次分配需要将 $n$ 个关键字放进各个队列中，一次收集需要将 $r$ 个桶都收集一遍。所以一次分配和一次收集时间复杂度为 $O (n + r)$ 。 $d$ 次就需要 $O (d (n + r))$ 的时间复杂度
空间复杂度，需要开辟关键字基的个数个队列，所以为 $O (r)$
稳定性，由于不直接比较大小，在分配与收集是按照先后顺序分配，所以不会改变相同关键字的顺序，是稳定的