使用C++实现基数排序算法
基数排序是一种非比较型整数排序算法，采用最低有效位优先（LSD）方式，按数字每一位（个位、十位等）排序，无需比较元素大小。其核心思想是通过稳定的计数排序处理每一位，确保低位排序结果在高位排序中保持有序。 实现步骤：1. 找出数组最大数，确定需处理的最高位数；2. 从低位到高位，对每一位用计数排序处理：统计当前位数字频次，计算位置，从后往前稳定放置元素，最后复制回原数组。 C++代码中，`countingSort`辅助函数实现按位排序（统计频次、计算位置、稳定放置），`radixSort`主函数循环处理每一位。时间复杂度为O(d×(n+k))（d为最大位数，n为数组长度，k=10），适用于整数范围较大的场景。其核心是利用计数排序的稳定性，确保低位排序结果在高位排序中不被破坏。测试结果显示排序后数组有序，验证了算法有效性。
阅读全文使用C++实现桶排序算法
桶排序是一种非比较型排序算法，通过将待排序元素分配到多个“桶”中，对每个桶内元素单独排序后合并，实现整体排序。核心是合理划分桶，使每个桶元素数量少，降低排序成本。 以[0,1)范围内的浮点数为例，算法步骤：1. 创建n个空桶（n为数组长度）；2. 按元素x的桶索引x*n（取整数部分）分配到对应桶；3. 各桶内用std::sort排序；4. 合并所有桶元素。 C++实现中，`bucketSort`函数通过vector<vector<double>>创建n个桶，遍历元素分配，排序后合并。测试验证了算法正确性。 复杂度：平均时间O(n)（元素均匀分布时），最坏O(n log n)（所有元素入同一桶）；空间O(n)。适用于数据分布均匀、范围明确的数值型数据，数据不均时性能退化。 该算法在数据分布合理时高效，尤其适合统计分析中的区间数据排序。
阅读全文使用C++实现计数排序算法
**计数排序**是一种非比较型排序算法，核心思想是通过统计元素出现次数构建排序数组，适用于整数范围不大的场景（如学生成绩、年龄）。 **基本思路**：以数组`[4,2,2,8,3,3,1]`为例，步骤为：1. 确定最大值（8），创建计数数组`count`统计各元素出现次数（如`count[2]=2`）；2. 按计数数组顺序将元素插入结果数组，得到排序结果`[1,2,2,3,3,4,8]`。 **实现要点**：C++代码中，先找最大值，统计次数，构建结果数组并复制回原数组。关键步骤包括计数数组初始化、统计次数、按次数填充结果数组。 **复杂度**：时间复杂度O(n+k)（n为数组长度，k为数据范围），空间复杂度O(k)。 **适用场景**：非负整数且范围小，需高效排序；负数可通过偏移量转换（如加最小值）处理。 计数排序通过“计数-构建”逻辑实现线性时间排序，是处理小范围整数
阅读全文使用C++实现选择排序算法
选择排序是简单直观的排序算法，核心思想是每次从待排序元素中选出最小（或最大）元素，将其放入已排序序列末尾，直至完成排序。基本思路分四步：外层循环控制当前待排序起始位置，内层循环在剩余元素中寻找最小值，交换操作将最小值移至当前起始位置，重复直至所有元素排序完成。 以数组{64,25,12,22,11}为例，演示过程：i=0时找到最小值11交换到首位，i=1找到12交换到第二位，i=2找到22交换到第三位，i=3无需交换，最终数组排序完成。 C++代码通过两层循环实现：外层循环控制位置i，内层循环找最小值索引minIndex，交换arr[i]与arr[minIndex]。时间复杂度O(n²)，空间复杂度O(1)。 选择排序实现简单、无需额外空间，适合小规模数据排序，是理解排序算法的基础。
阅读全文使用C++实现希尔排序算法
希尔排序是插入排序的改进版，又称“缩小增量排序”，通过分组插入排序并逐步缩小增量实现高效排序。基本思路：选定初始增量`gap`（如数组长度的一半），按`gap`分组（子序列元素间隔`gap`），对各组子序列插入排序；重复缩小`gap`（通常减半），直至`gap=1`完成整体排序。 核心原理：大`gap`时分组减少移动次数，小`gap`时数组已部分有序，大幅降低最终插入排序的移动量。以数组`[12,34,54,2,3]`为例，初始`gap=2`分组排序后数组渐趋有序，再`gap=1`完成最终排序。 代码通过三层循环实现：外层控制`gap`，中层遍历分组，内层移动元素。时间复杂度平均`O(n^1.3)`（依赖增量），最坏`O(n²)`，空间复杂度`O(1)`，不稳定。希尔排序通过分组优化插入排序，适用于较大数组，核心逻辑为“分组→排序→缩小增量→最终排序”。
阅读全文使用C++实现插入排序算法
插入排序是简单直观的排序算法，核心思想是将元素逐个插入到已排序子数组的合适位置（类似整理扑克牌）。基本思路：从第二个元素开始，取当前元素，与前面已排序元素比较，若前面元素更大则后移，直到找到插入位置，插入后继续处理下一个元素。 实现时，外层循环遍历元素，内层循环用临时变量保存当前元素，通过比较移动前面元素腾出位置，最后插入。时间复杂度最坏O(n²)，最好O(n)，空间复杂度O(1)。适用于小规模数据或基本有序数据，优点是稳定、简单，是理解复杂排序的基础。
阅读全文