10种常用排序算法简介

news/2024/4/29 15:14:39/文章来源:https://blog.csdn.net/li_peixiansang/article/details/136988599

常用排序算法

冒泡排序（Bubble Sort）

选择排序（Selection Sort）

插入排序（Insertion Sort）

希尔排序（Shell Sort）

归并排序（Merge Sort）

快速排序（Quick Sort）

堆排序（Heap Sort）

计数排序（Counting Sort）

桶排序（Bucket Sort）

基数排序（Radix Sort）

算法简介

接下来本文将从算法基本实现思路，时间复杂度，空间复杂度，使用情况来对10种算法一一介绍

冒泡排序（Bubble Sort）：
- 思路：依次比较相邻的元素，如果它们的顺序错误就交换位置，重复这个过程直到没有任何交换发生。
- 时间复杂度：平均情况和最坏情况下都为O(n^2)。
- 空间复杂度：O(1)。
- 使用情况：适用于小型数据集的排序，效率较低，不建议用于大规模数据排序。
选择排序（Selection Sort）：
- 思路：每次从未排序的部分选择最小（或最大）的元素放到已排序部分的末尾。
- 时间复杂度：平均情况和最坏情况下都为O(n^2)。
- 空间复杂度：O(1)。
- 使用情况：不稳定排序算法，适用于简单实现且不占用额外空间的情况。
插入排序（Insertion Sort）：
- 思路：将待排序的元素插入到已经排序的数组中的合适位置。
- 时间复杂度：平均情况和最坏情况下都为O(n^2)。
- 空间复杂度：O(1)。
- 使用情况：适用于小型数据集或基本有序的数据集。
希尔排序（Shell Sort）：
- 思路：插入排序的改进版，通过设定一个间隔序列来进行插入排序，最终达到完全排序。
- 时间复杂度：取决于间隔序列的选择，一般为O(n log^2 n)。
- 空间复杂度：O(1)。
- 使用情况：适用于中等规模的数据集，对大规模数据也有较好的表现。
归并排序（Merge Sort）：
- 思路：采用分治法，将数组分成两半分别排序，然后合并两个有序的子数组。
- 时间复杂度：平均和最坏情况下都为O(n log n)。
- 空间复杂度：O(n)。
- 使用情况：稳定排序算法，适用于大规模数据集的排序。
快速排序（Quick Sort）：
- 思路：选取一个基准值，将小于基准值的放在左边，大于基准值的放在右边，然后递归处理左右两边。
- 时间复杂度：平均情况下为O(n log n)，最坏情况下为O(n^2)。
- 空间复杂度：取决于递归的深度，在最坏情况下为O(n)。
- 使用情况：常用的高效排序算法，对大规模数据表现良好。
堆排序（Heap Sort）：
- 思路：利用堆的性质进行排序，首先构建最大堆或最小堆，然后不断取出堆顶元素调整堆。
- 时间复杂度：平均和最坏情况下都为O(n log n)。
- 空间复杂度：O(1)。
- 使用情况：不稳定排序算法，适用于需要原地排序的情况。
计数排序（Counting Sort）：
- 思路：统计数组中每个元素出现的次数，然后根据统计信息将元素放回数组。
- 时间复杂度：O(n + k)，其中k为最大元素的范围。
- 空间复杂度：O(k)。
- 使用情况：适用于元素范围不是很大的情况。
桶排序（Bucket Sort）：
- 思路：将元素分散到多个桶中，然后对每个桶中的元素进行排序，最后合并所有桶。
- 时间复杂度：取决于桶的数量和每个桶内排序所用的算法。
- 空间复杂度：O(n + k)，k为桶的数量。
- 使用情况：适用于元素均匀分布在范围内的情况。
基数排序（Radix Sort）：
- 思路：按照数字的位数从低位到高位依次进行排序，通常使用稳定的排序算法作为子排序。
- 时间复杂度：O(d*(n+k))，其中d为数字的位数，k为基数。
- 空间复杂度：O(n + k)。
- 使用情况：适用于整数数据的排序，位数较少且范围不是很大的情况。