十大经典排序算法

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

🔢 比较类排序（基于元素比较，时间复杂度最差为 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）

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