pyTenSort 1.0.0

Python Top 10 Sorting Algorithms

Python 十大排序

1. 快速排序‌(Quick Sort)

‌分治思想‌：

• 从数列中挑出一个元素作为"基准"(pivot)
• 将数列分为两部分：比基准小的放左边，比基准大的放右边
• 对左右两个子序列递归地进行相同操作

具体步骤‌：

• 选择基准值(通常选第一个/最后一个/中间元素)
• 分区操作：重新排列数列，使小于基准的都在前面，大于的都在后面
• 递归地对左右子序列进行快速排序

‌关键特点‌：

• 平均时间复杂度O(nlogn)，最坏O(n²)
• 原地排序(空间复杂度O(logn)递归栈)
• 不稳定排序

‌优化点‌：

• 小数组时切换为插入排序
• 三数取中法选择基准值
• 三向切分处理大量重复元素

2. 冒泡排序(Bubble Sort)

‌分治思想‌：

• 从数列中挑出一个元素作为"基准"(pivot)
• 将数列分为两部分：比基准小的放左边，比基准大的放右边
• 对左右两个子序列递归地进行相同操作

具体步骤‌：

• 选择基准值(通常选第一个/最后一个/中间元素)
• 分区操作：重新排列数列，使小于基准的都在前面，大于的都在后面
• 递归地对左右子序列进行快速排序

‌关键特点‌：

• 平均时间复杂度O(nlogn)，最坏O(n²)
• 原地排序(空间复杂度O(logn)递归栈)
• 不稳定排序

‌优化点‌：

• 小数组时切换为插入排序
• 三数取中法选择基准值
• 三向切分处理大量重复元素

3. 选择排序‌(Selection Sort)

核心原理‌：

• 将数组分为已排序和未排序两部分
• 每次从未排序部分选出最小(或最大)元素
• 将其放到已排序部分的末尾
• 重复这个过程直到所有元素排序完成

‌具体步骤‌：

• 初始状态：整个数组都是未排序区
• 第1轮：在0~n-1范围找最小值，与第0位交换
• 第2轮：在1~n-1范围找最小值，与第1位交换
• ...
• 第n-1轮：在n-2~n-1范围找最小值，完成排序

‌算法特点‌：

• 时间复杂度：固定O(n²)（无论数据是否有序）
• 空间复杂度：O(1)（原地排序）
• 不稳定排序（相同元素可能改变相对位置）
• 交换次数少（最多n-1次交换）

‌与冒泡排序对比‌：

• 选择排序：每次遍历只交换1次
• 冒泡排序：每次遍历可能多次交换
• 两者时间复杂度相同，但选择排序通常更快

4. 插入排序(Insertion Sort)

‌核心原理‌：

• 模拟玩扑克牌时的理牌方式
• 将数组分为已排序和未排序两部分
• 每次从未排序部分取出第一个元素
• 在已排序部分找到合适位置插入

‌具体步骤‌：

• 初始状态：第0个元素视为已排序
• 第1轮：将第1个元素插入到前1个元素的合适位置
• 第2轮：将第2个元素插入到前2个元素的合适位置
• ...
• 第n-1轮：将第n-1个元素插入到前n-1个元素的合适位置

‌算法特点‌：

• 时间复杂度：最好O(n)(已排序情况)，平均和最坏O(n²)
• 空间复杂度O(1)(原地排序)
• 稳定排序算法
• 对小规模或基本有序数据效率很高

‌与选择排序对比‌：

• 插入排序：边比较边移动元素
• 选择排序：先找到最小元素再交换
• 插入排序在数据基本有序时效率更高

5. ‌归并排序(Merge Sort)

‌核心原理‌：

• 采用分治策略(Divide and Conquer)
• 将数组递归地分成两半直到最小单元
• 对分割后的子数组进行排序合并
• 通过合并操作构建最终有序数组

‌具体步骤‌：

• 分割阶段：将当前数组平分成左右两部分
• 递归排序：对左右子数组分别递归调用归并排序
• 合并阶段：将两个已排序的子数组合并成一个有序数组

‌算法特点‌：

• 时间复杂度：稳定O(nlogn)（所有情况下）
• 空间复杂度：O(n)（需要额外存储空间）
• 稳定排序算法（相同元素保持原始顺序）
• 适合处理大规模数据

‌关键操作‌：

• 分割操作：简单取中间索引分割
• 合并操作：需要额外的临时数组
• 使用双指针技术比较两个子数组元素

6. 堆排序(Heap Sort)

1. 核心原理‌：

• 基于完全二叉树的堆数据结构实现
• 通过构建最大堆/最小堆实现排序
• 分为建堆和排序两个阶段

2.关键步骤‌：

• 建堆阶段‌：
  • 将无序数组构建成堆结构
  • 从最后一个非叶节点开始调整
  • 通过下沉(sift down)操作维护堆性质
• 排序阶段‌：
  • 将堆顶元素(最大值/最小值)与末尾元素交换
  • 缩小堆范围并重新调整堆结构
  • 重复直到堆中只剩一个元素

3. 堆的性质‌：

• 大顶堆：父节点 ≥ 子节点（用于升序排序）
• 小顶堆：父节点 ≤ 子节点（用于降序排序）
• 完全二叉树特性：可用数组存储，节点位置满足：
  • 父节点i的左子节点：2i+1
  • 父节点i的右子节点：2i+2
  • 子节点i的父节点：(i-1)//2

4. 算法特点‌：

• 时间复杂度：稳定O(nlogn)（建堆O(n)，每次调整O(logn)）
• 空间复杂度：O(1)（原地排序）
• 不稳定排序（相同元素可能改变顺序）

5. Python实现要点‌：

• 通常从最后一个非叶节点(len(arr)//2 -1)开始建堆
• 下沉操作是关键，需递归比较父子节点
• 排序阶段逐步缩小堆范围

7. ‌希尔排序(Shell Sort)

1. 核心原理‌：

• 基于插入排序的改进算法，通过分组策略提升效率
• 采用"缩小增量"的分治思想，逐步细化排序粒度
• 通过大间隔跳跃比较减少元素移动次数

2. 关键步骤‌：

• 分组阶段‌：按增量序列将数组划分为逻辑子序列
  • 初始增量通常为数组长度的一半
  • 每个子序列包含间隔为增量的元素
• 组内排序‌：对每个子序列进行插入排序
• 缩小增量‌：逐步减小间隔直至1（最终执行标准插入排序）

3. 增量序列选择‌：

• 希尔原始序列：h = N/2, N/4,...,1（时间复杂度O(n²)）
• Hibbard序列：1,3,7,...,2^k-1（时间复杂度O(n^{3/2})）
• Sedgewick序列：1,5,19,41,...（时间复杂度O(n^{4/3})）

4. 算法特点‌：

• 时间复杂度：平均O(n^{1.3})，优于简单插入排序
• 空间复杂度：O(1)（原地排序）
• 不稳定排序（相同元素可能改变相对位置）
• 适合中等规模数据，实现简单且无需额外存储

5. Python实现要点‌：

• 外层循环控制增量递减
• 中层循环处理各个分组
• 内层循环执行组内插入排序

8. 计数排序(Counting Sort)

1. 核心原理‌：

• 非比较型整数排序算法
• 通过统计元素出现次数实现排序
• 需要已知输入数据的范围(k)

2. 关键步骤‌：

• ‌统计阶段‌：统计每个元素出现次数
• ‌累加阶段‌：计算元素排序后的位置
• ‌重构阶段‌：按统计结果重构有序数组

3. 算法特点‌：

• 时间复杂度：O(n+k)（n为元素数量，k为数据范围）
• 空间复杂度：O(n+k)（需要额外计数数组）
• 稳定排序（相同元素保持原始顺序）
• 仅适用于整数且范围不大的情况

4. 适用条件‌：

• 数据必须是整数
• 数据范围(k)不应远大于数据量(n)
• 适合数据量大但范围小的场景

5. Python实现要点‌：

• 需要找出数组最大值确定计数范围
• 计数数组长度应为max_val+1
• 反向填充保证排序稳定性

9. ‌桶排序(Bucket Sort)

1. 核心原理‌：

• 分布式排序算法，将元素分配到不同的"桶"中
• 先分散后集中，每个桶单独排序后再合并
• 适合数据均匀分布的场合

2. 关键步骤‌：

• ‌分桶阶段‌：根据映射函数将元素分配到多个桶
• ‌桶内排序‌：对每个非空桶进行排序（通常使用插入排序）
• ‌合并阶段‌：按顺序连接所有桶中的元素

3. ‌算法特点‌：

• 时间复杂度：
  • 平均情况：O(n+k)（k为桶数量）
  • 最坏情况：O(n²)（所有元素集中在一个桶）
• 空间复杂度：O(n+k)（需要额外桶存储）
• 稳定性取决于桶内排序算法的选择

4. ‌适用条件‌：

• 输入数据均匀分布在某个范围内
• 数据分布情况已知
• 适合外部排序（数据量大于内存容量）

5. Python实现要点‌：

• 桶数量通常取√n或根据数据特征确定
• 需要设计合理的映射函数
• 桶内排序可选择任意合适算法

10. 基数排序(Radix Sort)

1. 核心原理‌：

• 非比较型整数排序算法，通过逐位分配和收集实现排序
• 采用"低位优先"(LSD)或"高位优先"(MSD)的位比较策略
• 利用稳定的子排序算法（通常用计数排序）处理每位数字

2. 关键步骤‌：

• ‌确定最大位数‌：找到数组中最大数字的位数k
• ‌按位排序‌：从最低位到最高位依次进行：
  • 分配：根据当前位数字将元素放入0-9的桶中
  • 收集：按桶顺序合并元素
• ‌重复操作‌：直到处理完最高位得到有序数组

3. 算法特点‌：

• 时间复杂度：O(n*k)（n为元素数量，k为最大位数）
• 空间复杂度：O(n+k)（需要额外桶空间）
• 稳定排序（保持相同元素的原始顺序）
• 仅适用于整数或可分离位的数据类型

4. Python实现要点‌：

• 使用计数排序作为子排序算法
• 通过(num//exp)%10提取指定位数字
• 需要处理负数时的特殊位计算