冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序和基数排序是十大经典排序算法。它们各自有不同的特点、时间复杂度和适用场景,是学习和应用排序算法的基础。
1. 冒泡排序
冒泡排序通过相邻元素的比较和交换,将最大(或最小)元素“冒泡”到数组的末尾。其时间复杂度为O(n²),适合小规模数据排序。
2. 选择排序
选择排序每次从未排序部分选择最小(或最大)元素,将其放到已排序部分的末尾。时间复杂度为O(n²),空间复杂度为O(1),但效率较低。
3. 插入排序
插入排序通过构建有序序列,将未排序数据按顺序插入。时间复杂度为O(n²),在部分有序的数组中表现较好。
4. 希尔排序
希尔排序是插入排序的改进版,通过比较相距一定间隔的元素,逐步减少间隔,最终将整个数组排序。时间复杂度介于O(n)和O(n²)之间,适合中等规模的数据排序。
5. 归并排序
归并排序采用分治法,将数组分为两部分分别排序,然后合并。时间复杂度为O(n log n),适合大规模数据排序。
6. 快速排序
快速排序通过选取“基准”元素,将数组分为两部分,递归排序。时间复杂度为O(n log n),但在最坏情况下会退化到O(n²)。
7. 堆排序
堆排序利用堆这种数据结构,通过不断调整堆来排序。时间复杂度为O(n log n),空间复杂度为O(1),适合外部排序。
8. 计数排序
计数排序通过统计每个元素的出现次数,直接计算其在排序后的位置。时间复杂度为O(n+k),k为元素范围,适合小范围整数的排序。
9. 桶排序
桶排序将数组划分为若干个桶,每个桶内部进行排序。时间复杂度为O(n+k),适合分布均匀的数据。
10. 基数排序
基数排序根据数字的每一位进行排序,通过多次排序实现整体排序。时间复杂度为O(nk),k为数字位数,适合非负整数排序。
这些排序算法各有优劣,选择合适的算法可以显著提高排序效率。