十大经典排序算法

经典排序算法有很多，常见的包括比较类排序和非比较类排序两大类。以下是最具代表性的经典排序算法及其简要介绍：

🔢 比较类排序（基于元素比较，时间复杂度最差为 O(n²) 或 O(n log n)）

1. 冒泡排序（Bubble Sort）

原理：相邻元素两两比较，大的往后“冒”。
时间复杂度：最坏 O(n²)，最好 O(n)
空间复杂度：O(1)
是否稳定：✅ 稳定
详情：冒泡排序（Bubble Sort）

2. 选择排序（Selection Sort）

原理：每次选择最小（大）元素，放到已排序序列尾部。
时间复杂度：O(n²)
空间复杂度：O(1)
是否稳定：❌ 不稳定
详情：选择排序（Selection Sort）

3. 插入排序（Insertion Sort）

原理：将当前元素插入到前面已排序部分的合适位置。
时间复杂度：最坏 O(n²)，最好 O(n)
空间复杂度：O(1)
是否稳定：✅ 稳定
详情：插入排序（Insertion Sort）

4. 希尔排序（Shell Sort）

原理：分组插入排序，逐步缩小间隔。
时间复杂度：平均 O(n^1.3)，具体取决于增量序列
空间复杂度：O(1)
是否稳定：❌ 不稳定
详情：希尔排序（Shell Sort）

5. 归并排序（Merge Sort）

原理：分治法，先递归分解，再合并有序数组。
时间复杂度：O(n log n)
空间复杂度：O(n)
是否稳定：✅ 稳定
详情：归并排序（Merge Sort）

6. 快速排序（Quick Sort）

原理：分治法，选定一个基准元素，划分左右两边递归排序。
时间复杂度：平均 O(n log n)，最坏 O(n²)
空间复杂度：O(log n)
是否稳定：❌ 不稳定
详情：快速排序（Quick Sort）

7. 堆排序（Heap Sort）

原理：构造最大（或最小）堆，依次取顶元素。
时间复杂度：O(n log n)
空间复杂度：O(1)
是否稳定：❌ 不稳定
详情：堆排序（Heap Sort）

⚙️ 非比较类排序（基于元素特征，不是基于比较）

8. 计数排序（Counting Sort）

原理：统计每个数出现次数，适用于整数、范围小。
时间复杂度：O(n + k)，k 是数值范围
空间复杂度：O(k)
是否稳定：✅ 稳定
详情：计数排序（Counting Sort）

9. 桶排序（Bucket Sort）

原理：将元素分到多个桶中，桶内排序。
时间复杂度：平均 O(n)，最坏 O(n²)
空间复杂度：O(n + k)
是否稳定：✅ 稳定（若桶内排序稳定）
详情：桶排序（Bucket Sort）

10. 基数排序（Radix Sort）

原理：按位排序（最低位开始），适合整数或字符串。
时间复杂度：O(nk)，k 为最大位数
空间复杂度：O(n + k)
是否稳定：✅ 稳定
详情：基数排序（Radix Sort）

🧠 按应用选择排序算法建议：

数据规模	数据特点	推荐算法
小规模	无明显特点	插入排序、冒泡排序
中等规模	稳定性要求高	归并排序
大规模	速度要求高	快速排序、堆排序
整数且范围小	非比较排序适用	计数、基数、桶排序