前言

  近期在准备下半年的软考，在刷题过程中遇到了一些经典的数据结构与算法的经典例题，在这里我以博客的形式回顾记录下【排序算法】的应用以及相关拓展。

概述

  常见10种的排序算法包括：【冒泡排序】、【插入排序】、【选择排序】、【快速排序】、归并排序】、【堆排序】、【希尔排序】【计数排序】、【桶排序】、【 基数排序】。在这里我们使用python语言来实现这些排序算法，简化下实现流程，我们生成一个长度为10的随机数组：

python

复制代码

import random
# 生成一个长度为10，元素在0-100之间的随机数组
arr = [random.randint(0, 100) for _ in range(10)]
print(arr)

冒泡排序

  冒泡排序是一种简单的排序算法，它的原理是通过不断交换相邻元素的位置，将最大的元素逐渐“冒泡”到序列的末尾，从而实现排序。

具体实现步骤如下：

1. 首先，比较相邻的两个元素，如果前面的元素比后面的元素大，则交换它们的位置。
2. 对每一对相邻的元素都进行上述比较和交换，这样一轮下来，最大的元素就会“冒泡”到序列的末尾。
3. 针对剩余未排序的元素，重复第 1 步和第 2 步，直到整个序列都被排序。

  在实现过程中，需要使用两层循环来实现冒泡排序。外层循环控制排序轮数，内层循环控制每轮比较的次数。具体实现步骤如下：

1. 首先，外层循环从第一个元素开始，依次遍历到倒数第二个元素。
2. 内层循环从第一个元素开始，依次遍历到倒数第二个未排序的元素。
3. 在内层循环中，比较相邻的两个元素，如果前面的元素比后面的元素大，则交换它们的位置。
4. 每轮内层循环结束后，最大的元素就会被“冒泡”到末尾，因此外层循环可以减少一次遍历。
5. 最终，整个序列就被排好序了。

冒泡排序的时间复杂度为 O(n^2)，空间复杂度为O(1)。，因此它不适合用于大规模数据的排序。

ini

复制代码

# 冒泡
def bubble_sort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(n):
        # 最后i个元素已经排好序，不需要再比较
        for j in range(0, n-i-1):
            # 如果当前元素大于下一个元素，则交换它们
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

插入排序

  插入排序是一种简单的排序算法，其基本原理是将未排序的元素一个一个插入到已排序的序列中，直到所有元素都被排序。

插入排序的实现步骤如下：

1. 将序列的第一个元素视为已排序的序列。
2. 从第二个元素开始，依次将每个元素插入到已排序的序列中。具体操作是将该元素与已排序序列中的元素从后往前比较，如果该元素比已排序序列中的元素小，则将已排序序列中的元素往后移动一个位置，直到找到该元素应该插入的位置。
3. 重复步骤2，直到所有元素都被插入到已排序序列中。

  实现过程中，可以使用嵌套循环来完成插入排序。外层循环从第二个元素开始遍历，内层循环从当前元素往前遍历已排序序列，直到找到该元素应该插入的位置。在内层循环中，如果已排序序列中的元素比当前元素大，则将其往后移动一个位置。最后，将当前元素插入到找到的位置。

ini

复制代码

# 插入排序
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

  插入排序的时间复杂度为O(n²)，空间复杂度为O(1)。虽然插入排序的时间复杂度不如快速排序和归并排序等算法，但是对于小规模数据的排序，插入排序的效率比较高。

选择排序

  选择排序是一种简单的排序算法，其基本原理是每次选择未排序序列中的最小元素，将其放到已排序序列的末尾，直到所有元素都被排序。

选择排序的实现步骤如下：

1. 将序列的第一个元素视为已排序的序列。
2. 从第二个元素开始，依次遍历未排序的序列，找到其中最小的元素，将其放到已排序序列的末尾。
3. 重复步骤2，直到所有元素都被排序。

  实现过程中，可以使用嵌套循环来完成选择排序。外层循环从第一个元素开始遍历，内层循环从当前元素的下一个元素开始遍历未排序的序列，找到其中最小的元素，并将其与当前元素交换位置。

  选择排序的时间复杂度为O(n²)，空间复杂度为O(1)。虽然选择排序的时间复杂度不如快速排序和归并排序等算法，但是对于小规模数据的排序，选择排序的效率比较高。

ini

复制代码

# 选择排序
def selection_sort(arr):
  n = len(arr)
  for i in range(n):
      min_idx = i
      for j in range(i+1, n):
          if arr[j] < arr[min_idx]:
              min_idx = j
      arr[i], arr[min_idx] = arr[min_idx], arr[i]
  return arr

快速排序

  快速排序是一种常用的排序算法，其原理是通过选择一个基准元素，将序列分成两个子序列，将比基准元素小的元素放到左边，比基准元素大的元素放到右边，然后对左右两个子序列递归地进行快速排序，最终得到一个有序序列。

快速排序的实现步骤如下：

1. 选择一个基准元素，通常选择序列的第一个元素。
2. 将序列分成两个子序列，一个子序列包含比基准元素小的元素，一个子序列包含比基准元素大的元素。
3. 对左右两个子序列递归地进行快速排序。
4. 将左子序列、基准元素、右子序列依次连接起来，得到一个有序序列。

ini

复制代码

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

归并排序

  归并排序是一种基于分治思想的排序算法，它将待排序的序列分成两个子序列，对每个子序列递归地进行排序，然后将两个有序子序列合并成一个有序序列。

其实现步骤如下：

1. 分解：将待排序的序列分成两个子序列，递归地将每个子序列分解成更小的子序列，直到每个子序列只有一个元素为止。
2. 合并：将两个有序子序列合并成一个有序序列。具体地，可以使用两个指针分别指向两个子序列的头部，比较两个指针所指向的元素的大小，将较小的元素放入结果序列中，并将该指针后移一位，直到其中一个子序列已经全部放入结果序列中，然后将另一个子序列中剩余的元素依次放入结果序列中。
3. 返回：将合并后的有序序列作为结果返回。

归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)，是一种稳定的排序算法。

ini

复制代码

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = arr[:mid]
    right_arr = arr[mid:]
    left_arr = merge_sort(left_arr)
    right_arr = merge_sort(right_arr)
    return merge(left_arr, right_arr)
def merge(left_arr, right_arr):
    result = []
    i, j = 0, 0
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result

堆排序

  堆排序是一种基于堆的排序算法，它将待排序的序列构建成一个堆，然后依次取出堆顶元素，将其放到已排序序列的末尾。

其实现步骤如下：

1. 构建堆：将待排序的序列构建成一个堆。具体地，可以先将序列看成一棵完全二叉树，然后从最后一个非叶子节点开始，依次将每个节点与其子节点比较，如果节点的值比其子节点的值小，则交换这两个节点的值，然后继续向下比较，直到该节点没有子节点或者节点的值已经比其子节点的值大。
2. 排序：依次取出堆顶元素，将其放到已排序序列的末尾。具体地，可以将堆顶元素与堆底元素交换，然后将堆的大小减1，然后从堆顶开始向下调整堆，以保持堆的性质。
3. 重复：重复步骤2，直到堆中只剩下一个元素为止。

堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)，是一种不稳定的排序算法。

ini

复制代码

# 堆排序
def heap_sort(arr):
    n = len(arr)
    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # 依次取出堆顶元素，将其放到已排序序列的末尾
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr
def heapify(arr, n, i):
    # 在以i为根节点的子树中构建最大堆
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

希尔排序

  希尔排序，也称递减增量排序，是插入排序的一种改进版本。希尔排序的基本思想是将待排序的序列分成若干个子序列，对每个子序列进行插入排序，然后逐渐缩小子序列的长度，最终进行一次插入排序，完成排序。

实现步骤如下：

1. 选择一个增量序列，例如：N/2，N/4，N/8...直到增量为1。
2. 对于每个增量，将待排序的序列分成若干个子序列，每个子序列的元素下标之间相差增量。
3. 对每个子序列进行插入排序。
4. 逐渐缩小增量，重复步骤2和3，直到增量为1。
5. 最后进行一次插入排序，完成排序。

希尔排序的时间复杂度取决于增量序列的选择，通常情况下，时间复杂度为O(n^2)。希尔排序是一种不稳定的排序算法，因为它会改变相等元素的原始顺序。

ini

复制代码

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

计数排序

  计数排序是一种非比较排序算法，其基本思想是统计每个元素在序列中出现的次数，然后根据元素出现的次数将元素排序。计数排序的时间复杂度为 O(n+k)，其中 n 是序列的长度，k 是序列中元素的取值范围。

计数排序的实现步骤如下：

1. 找出序列中的最大值和最小值，确定计数数组的长度。
2. 统计每个元素在序列中出现的次数，将其存储在计数数组中。
3. 计算每个元素在有序序列中的位置，即前缀和数组。
4. 从后往前遍历原序列，根据前缀和数组将元素放到有序序列中的对应位置。

ini

复制代码

def countingSort(arr):
    # 找到数组中的最大值
    max_value = max(arr)
    # 初始化计数数组
    count = [0] * (max_value + 1)
    # 统计每个元素出现的次数
    for i in arr:
        count[i] += 1
    # 根据计数数组排序
    sorted_arr = []
    for i in range(max_value + 1):
        sorted_arr.extend([i] * count[i])
    return sorted_arr

桶排序

  桶排序是一种非比较排序算法，它的核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序，最后将每个桶中的数据按照顺序依次取出，即可得到排序结果。桶排序的时间复杂度为O(n)，但需要额外的空间来存储桶。

桶排序的实现步骤如下：

1. 找到待排序序列中的最大值和最小值。
2. 计算出桶的个数，并创建相应个数的桶。
3. 遍历待排序序列，将每个元素分配到对应的桶中。
4. 对每个桶中的元素进行排序，可以使用任意排序算法，如插入排序等。
5. 将每个桶中的元素按照顺序依次取出，即可得到排序结果。

桶排序的优化：

1. 如果待排序序列中的元素分布不均匀，则可以使用动态桶的方式，即根据待排序数据的分布情况动态的调整桶的个数和桶的大小。
2. 如果待排序序列中的元素重复度较高，则可以使用计数排序的方式，即对每个桶中的元素进行计数，避免重复元素的排序。
3. 如果待排序序列中的元素不是整数类型，可以考虑使用基数排序的方式，即按照元素的位数从低到高进行排序。

桶排序的适用场景：

  桶排序适用于待排序序列中的元素分布均匀、元素重复度低、元素取值范围不大等情况。例如，对学生的成绩进行排序，成绩的取值范围通常是0到100，且分布比较均匀，这时候可以使用桶排序来进行排序。

ini

复制代码

def bucket_sort(arr, bucket_size=5):
    if len(arr) == 0:
        return arr
    # 确定桶的个数
    min_val, max_val = min(arr), max(arr)
    bucket_count = (max_val - min_val) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]
    # 将元素放入桶中
    for i in range(len(arr)):
        bucket_index = (arr[i] - min_val) // bucket_size
        buckets[bucket_index].append(arr[i])
    # 对每个桶进行排序
    for i in range(bucket_count):
        buckets[i].sort()
    # 将桶中的元素按顺序合并
    sorted_arr = []
    for bucket in buckets:
        sorted_arr += bucket
    return sorted_arr

基数排序

  基数排序是一种非比较排序算法，它的原理是将待排序的数字按照位数从低到高进行排序。

具体的实现步骤如下：

1. 找出待排序数列中最大的数字，并确定其位数。
2. 根据位数从低到高的顺序，依次对数列进行排序。
3. 对于每一位数，将待排序数列中的数字按照该位数进行分桶。例如，对于个位数，将所有数字按照个位数的大小分为10个桶。
4. 将分好的桶按照顺序合并成一个新的数列。
5. 重复第3步和第4步，直到所有位数都处理完毕。
6. 最后得到的数列即为排好序的结果。

  基数排序的时间复杂度为O(d * (n + k))，其中d是数字的位数，n是待排序数列的长度，k是数字的取值范围。由于基数排序需要使用桶来存储数字，因此它需要额外的空间来存储桶，空间复杂度为O(n + k)。

  基数排序的优点是稳定性好，适用于数字比较小但位数比较多的数列。但是它的缺点是需要额外的空间来存储桶，当数字的取值范围较大时，空间消耗会很大。

ini

复制代码

# 基数排序
def radix_sort(arr):
    # 获取数组中的最大值
    max_num = max(arr)
    # 获取最大值的位数
    digit = len(str(max_num))
    # 初始化桶
    bucket = [[] for _ in range(10)]
    # 进行 digit 次排序
    for i in range(digit):
        # 将每个元素放入对应的桶中
        for num in arr:
            index = (num // (10 ** i)) % 10
            bucket[index].append(num)
        # 将桶中的元素按顺序放回数组中
        arr.clear()
        for j in range(10):
            arr.extend(bucket[j])
            bucket[j].clear()
    return arr

复杂度

  在软考中常见出现时间复杂度以及空间复杂度，这里先带大家回顾下这两个复杂度的概念：

时间复杂度和空间复杂度都是用于【衡量算法效率】的指标。

  【时间复杂度】 是指算法运行所需要的时间，通常用大 O 表示法来表示。大 O 表示法是一种用于描述算法时间复杂度的符号表示法，它表示算法运行时间的增长率和输入数据规模 n 的关系。例如，如果一个算法的时间复杂度为 O(n)，则算法的运行时间随着输入数据规模 n 的增加而线性增长。

  【空间复杂度】是指算法运行所需要的空间，通常用大 O 表示法来表示。空间复杂度是指算法在运行过程中所需要的额外空间，不包括输入数据所占用的空间。例如，如果一个算法的空间复杂度为 O(n)，则算法在运行过程中所需要的额外空间随着输入数据规模 n 的增加而线性增长。

排序算法中的时间复杂度和空间复杂度：

结尾

不知不觉中写了这么多，软考备考路漫漫，仅以此篇分享众朋客飨阅！若有误烦请评论告知，感谢！