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提取指定位数字
* 需要处理负数时的特殊位计算