• 【算法基础】一文掌握十大排序算法，冒泡排序、插入排序、选择排序、归并排序、计数排序、基数排序、希尔排序和堆排序

    目录

    1 冒泡排序（Bubble Sort）

    2 插入排序（Insertion Sort）

    3 选择排序（Selection Sort）

    4. 快速排序（Quick Sort）

    5. 归并排序（Merge Sort）

    6 堆排序 (Heap Sort)

    7 计数排序 (Counting Sort)

    8 基数排序 (Radix Sort)

    9 希尔排序（Shell Sort）

    10 桶排序

       

    1 冒泡排序（Bubble Sort）

           冒泡排序是一种基本的排序算法，其核心思想是多次遍历待排序的元素，比较相邻的两个元素，如果它们的顺序不正确，则交换它们，直到整个数组按照指定顺序排列。

    1. def bubble_sort(arr):
    2.     n = len(arr)
    3.     for i in range(n):
    4.         for j in range(0, n-i-1):
    5.             # 比较相邻的两个元素
    6.             if arr[j] > arr[j+1]:
    7.                 # 如果顺序不正确，则交换它们
    8.                 arr[j], arr[j+1] = arr[j+1], arr[j]
    9.  
    10. # 示例用法
    11. arr = [64, 34, 25, 12, 22, 11, 90]
    12. bubble_sort(arr)
    13. print("冒泡排序后的数组：", arr)

            冒泡排序通过多次遍历数组，每次比较相邻的两个元素，如果它们的顺序不正确就交换它们。这个过程将最大的元素逐渐“冒泡”到数组的末尾。

            

            时间复杂度为 O(n^2)，不适合大规模数据集。 

    2 插入排序（Insertion Sort）

            插入排序是一种稳定的排序算法，其核心思想是将未排序的元素逐个插入到已排序的部分，从前往后遍历，保持前面的元素有序。

    1. def insertion_sort(arr):
    2.     for i in range(1, len(arr)):
    3.         key = arr[i]
    4.         j = i - 1
    5.         while j >= 0 and key < arr[j]:
    6.             # 将较大的元素向右移动
    7.             arr[j + 1] = arr[j]
    8.             j -= 1
    9.         arr[j + 1] = key
    10.  
    11. # 示例用法
    12. arr = [64, 34, 25, 12, 22, 11, 90]
    13. insertion_sort(arr)
    14. print("插入排序后的数组：", arr)

            插入排序逐个将未排序的元素插入到已排序的部分，从前往后遍历，保持前面的元素有序。时间复杂度为 O(n^2)，适合小规模数据集和部分有序的数据。 

    3 选择排序（Selection Sort）

            选择排序是一种简单的不稳定排序算法，其核心思想是找到未排序部分的最小元素，将其与未排序部分的第一个元素交换位置。

    1. def selection_sort(arr):
    2.     n = len(arr)
    3.     for i in range(n):
    4.         min_index = i
    5.         for j in range(i+1, n):
    6.             # 找到未排序部分的最小元素的索引
    7.             if arr[j] < arr[min_index]:
    8.                 min_index = j
    9.         # 交换最小元素与未排序部分的第一个元素
    10.         arr[i], arr[min_index] = arr[min_index], arr[i]
    11.  
    12. # 示例用法
    13. arr = [64, 34, 25, 12, 22, 11, 90]
    14. selection_sort(arr)
    15. print("选择排序后的数组：", arr)

          选择排序通过多次选择未排序部分的最小元素，并将其与未排序部分的第一个元素交换位置来进行排序。时间复杂度为 O(n^2)，不适合大规模数据集。

    4. 快速排序（Quick Sort）

            快速排序是一种高效的分治排序算法，它选择一个基准元素，将数组分成两部分，左边的元素都小于基准，右边的元素都大于基准，然后递归对左右两部分进行排序。

    1. def quick_sort(arr):
    2.     # 基本情况：如果数组为空或只包含一个元素，无需排序
    3.     if len(arr) <= 1:
    4.         return arr
    5.     
    6.     # 选择中间元素作为基准点（pivot）
    7.     pivot = arr[len(arr) // 2]
    8.     
    9.     # 将数组分成三部分：小于、等于、大于基准点的元素
    10.     left = [x for x in arr if x < pivot]
    11.     middle = [x for x in arr if x == pivot]
    12.     right = [x for x in arr if x > pivot]
    13.     
    14.     # 递归排序左右两部分，然后合并结果
    15.     return quick_sort(left) + middle + quick_sort(right)
    16.  
    17. # 示例用法
    18. arr = [64, 34, 25, 12, 22, 11, 90]
    19. arr = quick_sort(arr)
    20. print("快速排序后的数组：", arr)
    • 快速排序是一种高效的分治排序算法，它通过选择一个基准点（通常是数组中的中间元素）将数组分成左右两部分，并递归地对左右两部分进行排序。
    • 基本情况是数组为空或只包含一个元素，无需排序。
    • 针对每个元素，将它与基准点进行比较，分成小于、等于和大于基准点的三个子数组。
    • 然后，递归地对左右两部分进行排序，最后将它们与基准点合并，形成一个有序的数组。

    5. 归并排序（Merge Sort）

            归并排序是一种稳定的分治排序算法，它将数组分成两半，分别排序，然后将已排序的两个子数组合并成一个有序数组。

    1. def merge_sort(arr):
    2.     # 基本情况：如果数组为空或只包含一个元素，无需排序
    3.     if len(arr) <= 1:
    4.         return arr
    5.     
    6.     # 将数组分成两半
    7.     mid = len(arr) // 2
    8.     left = arr[:mid]
    9.     right = arr[mid:]
    10.     
    11.     # 递归地对左右两部分进行排序
    12.     left = merge_sort(left)
    13.     right = merge_sort(right)
    14.     
    15.     # 合并已排序的左右两部分
    16.     return merge(left, right)
    17.  
    18. def merge(left, right):
    19.     result = []
    20.     i = j = 0
    21.     
    22.     # 合并两个已排序的子数组
    23.     while i < len(left) and j < len(right):
    24.         if left[i] < right[j]:
    25.             result.append(left[i])
    26.             i += 1
    27.         else:
    28.             result.append(right[j])
    29.             j += 1
    30.     
    31.     # 如果左边或右边的子数组还有剩余元素，将它们添加到结果中
    32.     result.extend(left[i:])
    33.     result.extend(right[j:])
    34.     
    35.     return result
    36.  
    37. # 示例用法
    38. arr = [64, 34, 25, 12, 22, 11, 90]
    39. arr = merge_sort(arr)
    40. print("归并排序后的数组：", arr)
    • 归并排序是一种稳定的分治排序算法，它将数组递归分成两半，然后合并已排序的子数组。
    • 基本情况是数组为空或只包含一个元素，无需排序。
    • 递归地对左右两部分进行排序，然后使用 merge 函数将它们合并成一个有序的数组。
    • merge 函数将两个已排序的子数组合并，同时维护它们的有序性。

    6 堆排序 (Heap Sort)

            堆排序是一种不稳定的排序算法，它使用堆数据结构（通常是最大堆）来进行排序。堆排序分为两个主要步骤：建立堆和排序。

    1. def heapify(arr, n, i):
    2.     largest = i
    3.     left = 2 * i + 1
    4.     right = 2 * i + 2
    5.  
    6.     # 找到左子节点和右子节点中的最大值
    7.     if left < n and arr[left] > arr[largest]:
    8.         largest = left
    9.  
    10.     if right < n and arr[right] > arr[largest]:
    11.         largest = right
    12.  
    13.     # 如果最大值不是当前节点，交换它们
    14.     if largest != i:
    15.         arr[i], arr[largest] = arr[largest], arr[i]
    16.  
    17. def heap_sort(arr):
    18.     n = len(arr)
    19.  
    20.     # 构建最大堆
    21.     for i in range(n // 2 - 1, -1, -1):
    22.         heapify(arr, n, i)
    23.  
    24.     # 一个接一个地从堆中取出元素，交换根节点与最后一个节点，然后重新构建堆
    25.     for i in range(n - 1, 0, -1):
    26.         arr[i], arr[0] = arr[0], arr[i]
    27.         heapify(arr, i, 0)
    28.  
    29. # 示例用法
    30. arr = [64, 34, 25, 12, 22, 11, 90]
    31. heap_sort(arr)
    32. print("堆排序后的数组：", arr)
    • 排序使用堆数据结构（通常是最大堆）来进行排序。首先构建最大堆，然后一个接一个地从堆中取出元素，交换根节点与最后一个节点，然后重新构建堆。
    • heapify 函数用于维护堆的性质，即父节点的值大于或等于子节点的值。
    • 这个算法的时间复杂度为 O(nlogn)，是一种高效的排序算法。

    7 计数排序 (Counting Sort)

            计数排序是一种非比较排序算法，它根据输入元素的计数来对元素进行排序。它适用于整数或有限范围内的非负整数。

    1. def counting_sort(arr):
    2.     max_val = max(arr)
    3.     min_val = min(arr)
    4.     range_of_elements = max_val - min_val + 1
    5.     count_arr = [0] * range_of_elements
    6.     output_arr = [0] * len(arr)
    7.  
    8.     # 计数每个元素的出现次数
    9.     for num in arr:
    10.         count_arr[num - min_val] += 1
    11.  
    12.     # 计算每个元素的累积计数
    13.     for i in range(1, len(count_arr)):
    14.         count_arr[i] += count_arr[i - 1]
    15.  
    16.     # 根据累积计数将元素放入输出数组
    17.     for i in range(len(arr) - 1, -1, -1):
    18.         output_arr[count_arr[arr[i] - min_val] - 1] = arr[i]
    19.         count_arr[arr[i] - min_val] -= 1
    20.  
    21.     return output_arr
    22.  
    23. # 示例用法
    24. arr = [4, 2, 2, 8, 3, 3, 1]
    25. arr = counting_sort(arr)
    26. print("计数排序后的数组：", arr)
    • 计数排序是一种非比较排序算法，适用于整数或有限范围内的非负整数。
    • 首先，计算每个元素的出现次数，然后计算每个元素的累积计数，最后根据累积计数将元素放入输出数组。
    • 这个算法的时间复杂度为 O(n+k)，其中 k 是输入范围的大小。 

    8 基数排序 (Radix Sort)

            基数排序是一种非比较排序算法，它将数字按照每个位数进行排序，从最低位到最高位，依次排列。

    1. def counting_sort(arr, exp):
    2.     n = len(arr)
    3.     output = [0] * n
    4.     count = [0] * 10
    5.  
    6.     # 计数每个元素的出现次数
    7.     for i in range(n):
    8.         index = arr[i] // exp
    9.         count[index % 10] += 1
    10.  
    11.     # 计算每个元素的累积计数
    12.     for i in range(1, 10):
    13.         count[i] += count[i - 1]
    14.  
    15.     # 根据累积计数将元素放入输出数组
    16.     i = n - 1
    17.     while i >= 0:
    18.         index = arr[i] // exp
    19.         output[count[index % 10] - 1] = arr[i]
    20.         count[index % 10] -= 1
    21.         i -= 1
    22.  
    23.     # 将输出数组的内容复制到原始数组中
    24.     for i in range(n):
    25.         arr[i] = output[i]
    26.  
    27. def radix_sort(arr):
    28.     max_val = max(arr)
    29.     exp = 1
    30.     while max_val // exp > 0:
    31.         counting_sort(arr, exp)
    32.         exp *= 10
    33.  
    34. # 示例用法
    35. arr = [170, 45, 75, 90, 802, 24, 2, 66]
    36. radix_sort(arr)
    37. print("基数排序后的数组：", arr)
    • 基数排序是一种非比较排序算法，它按照每个位数进行排序，从最低位到最高位，依次排列。
    • 首先使用计数排序对每个位数进行排序，然后再次对下一个位数进行排序，依次进行直到最高位。
    • 这个算法的时间复杂度为 O(nk)，其中 k 是数字的最大位数。

    9 希尔排序（Shell Sort）

            希尔排序（Shell Sort）是一种插入排序的改进版本，也被称为缩小增量排序。希尔排序通过将数组分成若干个子序列来排序数据，然后逐渐缩小子序列的间隔，最终得到一个完全排序的数组。希尔排序的主要思想是提前交换较远的元素，以加快排序过程。

    算法原理：

    1. 选择一个增量序列（间隔序列），通常选择的增量是数组长度的一半，然后逐渐减小增量。

    2. 对于每个增量，将数组分成若干个子序列，每个子序列使用插入排序进行排序。

    3. 重复步骤2，逐渐减小增量，直到增量为1。

    4. 当增量为1时，整个数组成为一个序列，使用插入排序对其进行排序。

    1. def shell_sort(arr):
    2.     n = len(arr)
    3.     gap = n // 2  # 初始增量取数组长度的一半
    4.  
    5.     while gap > 0:
    6.         for i in range(gap, n):
    7.             temp = arr[i]
    8.             j = i
    9.             # 使用插入排序对子序列进行排序
    10.             while j >= gap and arr[j - gap] > temp:
    11.                 arr[j] = arr[j - gap]
    12.                 j -= gap
    13.             arr[j] = temp
    14.         gap //= 2  # 缩小增量
    15.  
    16. # 示例用法
    17. arr = [64, 34, 25, 12, 22, 11, 90]
    18. shell_sort(arr)
    19. print("希尔排序后的数组：", arr)

             希尔排序的关键在于选择合适的增量序列。常见的增量序列有希尔增量、Hibbard增量、Knuth增量等，不同的增量序列会影响排序的性能。

    • 希尔排序的时间复杂度取决于增量序列的选择，平均时间复杂度通常在 O(n^1.25) 到 O(n^2) 之间，比插入排序要快。

    • 希尔排序是一种不稳定排序算法，适用于中等大小的数据集。虽然不如快速排序和归并排序快，但在某些情况下比插入排序更快。希尔排序通常用于嵌入式系统等资源有限的环境。

    10 桶排序（Bucket Sort）

             桶排序（Bucket Sort）是一种分布式排序算法，它将元素分散到一组桶中，然后对每个桶中的元素进行排序，最后将所有桶中的元素按顺序合并成一个有序序列。桶排序适用于元素均匀分布在一个范围内的情况，特别适用于浮点数排序。

    算法原理：

    1. 确定桶的数量和范围，通常根据输入数据的分布来选择桶的数量。如果元素均匀分布在一个范围内，那么可以选择桶的数量等于元素的数量。

    2. 将每个元素分配到相应的桶中。元素的分配可以采用不同的方法，例如线性划分或哈希函数。

    3. 对每个桶中的元素进行排序，可以使用任何排序算法，通常选择插入排序。

    4. 合并所有桶中的元素，按照桶的顺序得到最终的有序序列。

    1. def bucket_sort(arr):
    2.     # 确定桶的数量，这里选择与输入元素数量相同
    3.     n = len(arr)
    4.     if n <= 1:
    5.         return arr
    6.  
    7.     # 初始化桶
    8.     max_val = max(arr)
    9.     min_val = min(arr)
    10.     bucket_range = (max_val - min_val) / n  # 每个桶的范围
    11.     bucket_count = n  # 桶的数量等于元素数量
    12.     buckets = [[] for _ in range(bucket_count)]
    13.  
    14.     # 将元素分配到桶中
    15.     for num in arr:
    16.         index = int((num - min_val) / bucket_range)
    17.         buckets[index].append(num)
    18.  
    19.     # 对每个桶中的元素进行排序
    20.     for i in range(bucket_count):
    21.         buckets[i].sort()
    22.  
    23.     # 合并所有桶中的元素
    24.     sorted_arr = []
    25.     for bucket in buckets:
    26.         sorted_arr.extend(bucket)
    27.  
    28.     return sorted_arr
    29.  
    30. # 示例用法
    31. arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
    32. arr = bucket_sort(arr)
    33. print("桶排序后的数组：", arr)

             桶排序的性能取决于桶的数量和元素的分布。如果元素均匀分布在一个范围内，并且桶的数量足够多，那么桶排序可以非常高效。

    • 桶排序的时间复杂度通常为 O(n + k)，其中 n 是元素的数量，k 是桶的数量。

    • 桶排序是一种稳定排序算法，适用于浮点数排序等特定情况。不过，它需要额外的内存空间来存储桶，因此不适用于数据集非常大的情况。

  • 相关阅读:
    自定义MVC增删改查
    软考高级信息系统项目管理师系列论文十六：论信息系统项目质量管理
    python判断是否为回文字符串
    关于Redis在windows上运行及fork函数问题
    51单片机的hello world之点灯
    Linux知识点 -- 网络基础 -- 网络层
    切水果游戏开发1
    使用Testconainers来进行JAVA测试
    使用 http-proxy 代理 HTTP 请求时遇到的 the requested url is invalid 错误消息
    字节输入流【InputStream】(读文件)
  • 原文地址：https://blog.csdn.net/qq_35831906/article/details/133421111