八大排序简介
八大排序是数据结构与算法中经典的排序算法，包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、基数排序。它们的时间复杂度、空间复杂度和适用场景各有不同，下面详细说明每种排序的原理、步骤、复杂度及特点：
一、冒泡排序（Bubble Sort）
原理
通过重复遍历待排序数组，每次比较相邻的两个元素，若顺序错误则交换位置，直到所有元素都排好序。因为每一轮最大的元素会 “浮” 到数组末尾，类似冒泡，所以得名。
步骤
- 从数组第一个元素开始，依次比较相邻的两个元素。
- 如果前一个元素大于后一个元素，就交换它们的位置。
- 遍历完一轮后，最大的元素会移动到数组的最后一位。
- 重复上述过程，每次遍历的范围减少一个元素（因为最后一位已排好序），直到没有元素需要交换。
复杂度
- 时间复杂度：O(n²)（最坏和平均情况），O(n)（最好情况，即数组已排序，可通过优化添加标志位实现）。
- 空间复杂度：O(1)（只需要一个临时变量用于交换）。
特点
- 稳定排序（相等元素的相对位置不变）。
- 简单易实现，但效率较低，适合小规模数据。
二、选择排序（Selection Sort）
原理
每一轮从待排序的元素中找到最小（或最大）的元素，将其与数组的起始位置（或当前轮次的起始位置）交换，直到所有元素排好序。
步骤
- 在未排序的数组中找到最小元素，记录其索引。
- 将最小元素与数组的第一个元素交换位置。
- 从剩余未排序的元素中重复步骤 1 和 2，直到所有元素都排好序。
复杂度
- 时间复杂度：O(n²)（无论数组是否有序，都需要遍历寻找最小元素）。
- 空间复杂度：O(1)（只需要一个临时变量用于交换）。
特点
- 不稳定排序（例如数组 [2, 2, 1]，第一次交换后第一个 2 会被换到第二位，破坏稳定性）。
- 交换次数少（每轮最多一次），但比较次数多，适合数据量小的场景。
三、插入排序（Insertion Sort）
原理
将数组分为 “已排序” 和 “未排序” 两部分，每次从 “未排序” 部分取一个元素，插入到 “已排序” 部分的合适位置，直到所有元素都插入完毕。类似整理扑克牌的过程。
步骤
- 假设数组的第一个元素是 “已排序” 部分，其余元素是 “未排序” 部分。
- 从 “未排序” 部分的第一个元素开始，依次与 “已排序” 部分的元素从后往前比较。
- 如果 “未排序” 元素小于 “已排序” 元素，则将 “已排序” 元素后移一位，直到找到合适的插入位置。
- 将 “未排序” 元素插入到该位置，重复步骤 2-3，直到所有元素都插入 “已排序” 部分。
复杂度
- 时间复杂度：O(n²)（最坏和平均情况），O(n)（最好情况，数组已排序，只需遍历一次）。
- 空间复杂度：O(1)。
特点
- 稳定排序。
- 对近乎有序的数据效率很高，适合小规模数据或作为其他排序算法的辅助（如归并排序的子数组排序）。
四、希尔排序（Shell Sort）
原理
插入排序的改进版，通过 “分组” 的方式减少数据移动次数。先将数组按一定的 “步长” 分成多个子数组，对每个子数组进行插入排序；然后逐渐减小步长，重复分组和排序，直到步长为 1（此时相当于一次完整的插入排序）。
步骤
- 选择一个初始步长（通常为数组长度的一半，之后每次减半）。
- 按步长将数组分为多个子数组（例如步长为 3 时，子数组为 [0,3,6,...]、[1,4,7,...] 等）。
- 对每个子数组执行插入排序。
- 减小步长（如步长 = 步长 //2），重复步骤 2-3，直到步长为 1。
- 当步长为 1 时，对整个数组执行插入排序，完成最终排序。
复杂度
- 时间复杂度：取决于步长选择，平均情况约为O(n^1.3)，最坏情况O(n²)（如步长为 1 时）。
- 空间复杂度：O(1)。
特点
- 不稳定排序（分组排序可能破坏相等元素的相对位置）。
- 效率高于直接插入排序，适合中等规模数据。
五、归并排序（Merge Sort）
原理
基于 “分治思想”，将数组不断拆分成两个子数组，直到子数组长度为 1；然后将相邻的子数组两两合并，合并时保证有序，最终得到完整的有序数组。
步骤
- 分解：将数组从中间分成两个子数组，递归分解每个子数组，直到子数组长度为 1。
- 合并：将两个有序的子数组合并为一个有序数组。合并时，设置两个指针分别指向两个子数组的起始位置，比较指针指向的元素，将较小的元素放入临时数组，移动对应指针，直到其中一个子数组遍历完毕，再将剩余元素放入临时数组。
- 重复合并过程，直到所有子数组合并为一个完整的有序数组。
复杂度
- 时间复杂度：O(n log n)（无论最坏、平均还是最好情况，因为每次分解和合并的时间固定）。
- 空间复杂度：O(n)（需要临时数组存储合并结果）。
特点
- 稳定排序。
- 效率高，适合大规模数据，但需要额外的存储空间。
六、快速排序（Quick Sort）
原理
同样基于 “分治思想”，通过选择一个 “基准元素”，将数组分为两部分：小于基准的元素和大于基准的元素；然后递归对这两部分进行排序，直到整个数组有序。
步骤
- 选择数组中的一个元素作为基准（通常选第一个、最后一个或中间元素）。
- 分区：将数组中小于基准的元素移到基准左边，大于基准的元素移到右边（相等元素可放任意一边）。
- 递归地对基准左边的子数组和右边的子数组执行步骤 1-2，直到子数组长度为 1（此时已有序）。
复杂度
- 时间复杂度：O(n log n)（平均和最好情况），O(n²)（最坏情况，如数组已排序且选择第一个元素为基准，此时每次分区只能减少一个元素）。
- 空间复杂度：O(log n)（递归调用栈的深度，平均情况）或O(n)（最坏情况）。
特点
- 不稳定排序（分区过程中可能交换相等元素的位置）。
- 实际应用中效率很高，是最快的排序算法之一，适合大规模数据。可通过优化基准选择（如随机选择或三数取中）避免最坏情况。
七、堆排序（Heap Sort）
原理
利用 “堆” 这种数据结构（完全二叉树）的特性实现排序。堆分为大顶堆（父节点大于子节点）和小顶堆（父节点小于子节点），排序时通常用大顶堆：先将数组构建成大顶堆，然后将堆顶（最大元素）与数组末尾元素交换，再调整剩余元素为大顶堆，重复直到所有元素有序。
步骤
- 构建大顶堆：从最后一个非叶子节点开始，依次向上调整每个节点，确保父节点大于子节点。
- 将堆顶元素（最大元素）与数组最后一个元素交换，此时最大元素已排好序。
- 忽略已排好序的最后一个元素，对剩余元素重新调整为大顶堆。
- 重复步骤 2-3，直到所有元素都排好序。
复杂度
- 时间复杂度：O(n log n)（建堆时间为 O (n)，每次调整堆为 O (log n)，共 n-1 次调整）。
- 空间复杂度：O(1)（原地排序，无需额外空间）。
特点
- 不稳定排序（交换堆顶和末尾元素时可能破坏稳定性）。
- 效率高，适合大规模数据，且对缓存友好（访问元素局部性好）。
八、基数排序（Radix Sort）
原理
非比较型排序算法，通过按 “位”（个位、十位、百位等）依次排序，最终得到有序数组。分为LSD（最低位优先） 和MSD（最高位优先），常用 LSD：先按个位排序，再按十位排序，直到最高位。
步骤（以 LSD 为例）
- 确定数组中最大元素的位数（如最大元素是 123，则位数为 3）。
- 从最低位（个位）开始，对所有元素按当前位的数值进行 “桶排序”（0-9 共 10 个桶）。
- 将每个桶中的元素按顺序取出，组成新的数组。
- 对下一位（十位、百位等）重复步骤 2-3，直到所有位都处理完毕。
复杂度
- 时间复杂度：*O(d(n+k))，其中 d 是最大元素的位数，n 是数组长度，k 是桶的数量（通常为 10）。当 d 为常数时，可视为O(n)**。
- 空间复杂度：O(n+k)（需要存储桶中的元素）。
特点
- 稳定排序（桶排序过程中保持元素的相对顺序）。
- 适合处理整数或可转换为固定位数的字符串等数据，不适合浮点数（位数不固定）。
八大排序对比总结
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(n²) | O(n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 基数排序 | O(d*(n+k)) | O(d*(n+k)) | O(d*(n+k)) | O(n+k) | 稳定 |
适用场景建议
- 小规模数据：冒泡排序、选择排序、插入排序（插入排序最优）。
- 中等规模数据：希尔排序。
- 大规模数据：归并排序、快速排序、堆排序（快速排序实际应用最广）。
- 整数或固定位数数据：基数排序（效率高）。