目录
冒泡排序（Bubble Sort）
选择排序（Selection Sort）
插入排序（Insertion Sort）
希尔排序（Shell Sort）
快速排序（Quick Sort）
堆排序（Heapsort）
归并排序（Merge Sort）
计数排序（Counting Sort）
桶排序（Bucket Sort）
基数排序（Radix Sort）
常见的排序算法包括冒泡排序、选择排序、插入排序、希尔排序、快速排序、堆排序、归并排序、计数排序、桶排序和基数排序等。以下是对这些排序算法的详细介绍：
冒泡排序（Bubble Sort）
- 原理：通过重复遍历要排序的序列，每次比较相邻的元素并交换它们的位置，使得每次遍历都将当前未排序部分中的最大元素移动到末尾。
- 优点：稳定。
- 缺点：慢，每次只能移动相邻两个数据，时间复杂度为O(n^2)。
- 适用场景：适用于数据量较小且对效率要求不高的场景。
选择排序（Selection Sort）
- 原理：每次从未排序部分找到最小（或最大）元素，将其放到已排序序列的末尾。
- 优点：数据移动次数已知为（n-1）次。
- 缺点：比较次数多，时间复杂度为O(n^2)。
- 适用场景：适用于数据量较小且对稳定性无要求的场景。
插入排序（Insertion Sort）
- 原理：将未排序的部分元素一个一个插入到已排序部分的合适位置。
- 优点：稳定，当序列已经有序时，时间复杂度为O(n)。
- 缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，最坏情况下时间复杂度为O(n^2)。
- 适用场景：适用于数据量较小且基本有序的数据排序场景。
希尔排序（Shell Sort）
- 原理：对插入排序进行改进，通过逐步减小增量对数组进行排序。
- 优点：快，数据移动少，平均时间复杂度为O(n^1.3)，比直接插入排序效率更高。
- 缺点：不稳定，增量的选择对排序效率有影响。
- 适用场景：适用于中等规模的数据排序，当希望获得比简单排序算法更好的效率时。
快速排序（Quick Sort）
- 原理：采用分治策略，选择一个基准元素，将数组分割成两部分，分别递归排序。
- 优点：极快，数据移动少，平均时间复杂度为O(n log n)。
- 缺点：不稳定，最坏情况下时间复杂度为O(n^2)，但通常可以通过优化来避免。
- 适用场景：适用于大规模数据排序。
堆排序（Heapsort）
- 原理：基于最大堆或最小堆的特性进行排序。
- 优点：不需要额外的存储空间，时间复杂度为O(n log n)。
- 缺点：不稳定，需要构建堆的过程。
- 适用场景：适用于需要快速访问最大或最小元素的场景。
归并排序（Merge Sort）
- 原理：通过分割和合并两个有序子数组来排序。
- 优点：稳定，时间复杂度为O(n log n)。
- 缺点：需要额外的存储空间。
- 适用场景：适用于大规模数据排序，但需要额外存储空间。
计数排序（Counting Sort）
- 原理：通过创建一个数组来计数每个元素出现的次数，然后根据计数结果重新排列数组。
- 优点：线性时间复杂度O(n+k)，其中k是元素范围。
- 缺点：需要额外的存储空间，且适用于元素范围有限的场景。
- 适用场景：适用于元素范围有限且数据量不大的场景。
桶排序（Bucket Sort）
- 原理：将数组元素分布到几个有序的桶里，每个桶里的元素再排序（可以再使用其他的排序算法或是递归的桶排序）。
- 优点：简单直观，适用于输入近似均匀分布的情况。
- 缺点：需要额外的存储空间，且桶的数量选择对排序效率有影响。
- 适用场景：输入数据服从均匀分布时，桶排序的性能较好。
基数排序（Radix Sort）
- 原理：按位对数字进行排序，通常从最低有效位（LSD）到最高有效位（MSD）进行排序。
- 优点：稳定，适用于多位数整数排序。
- 缺点：需要额外的存储空间，且时间复杂度与数字的位数有关。
- 适用场景：适用于log(N)远大于K的情况，如多位数整数排序。