[[排序算法对比]]
[[堆排序]]
[[希尔排序]]

1 熟悉每种排序的步骤

2 区分：

选择排序 每次选择最小的和本次迭代最左边交换
冒泡排序 每次两两比较交换，直到本次迭代最右边，最大的元素会被移到最右边
插入排序 依次迭代插入到前面已经排好的元素

3 稳定性等排序性质，适合范围

4 最差、最好、平均时间复杂度，空间复杂度

5 手撕步骤

希尔排序是插入排序的优化

所有递归都可以用非递归(迭代)的方式实现

理论上所有递归算法都可以用非递归（迭代）的方式实现。这是因为递归本质上利用了函数调用栈，而非递归实现则通过显式地维护一个栈数据结构来模拟递归过程。

将外循环条件加入内循环条件，这样当外部条件不满足，也可以直接跳出两重循环

基数排序

[[基数排序]]

自适应排序与非自适应排序

[[自适应排序与非自适应排序]]

非原地排序 (Out-of-Place Sorting)和原地排序

定义

非原地排序（Out-of-Place Sorting）是指在排序过程中需要额外的存储空间（通常与原数组大小相当或更大）来辅助排序的算法。这些算法不会直接在原始数据上进行修改，而是借助额外的数据结构（如数组、链表、堆等）来完成排序。

特点

  1. 需要额外存储空间：通常需要 O(n) 或更多的辅助空间。
  2. 不影响原始数据：排序过程中不会直接修改原数组，而是先复制数据到新空间，再返回排序后的结果。
  3. 适用于不可变数据：适合处理不可变（immutable）数据或需要保留原始数据的情况。
  4. 通常更稳定：许多非原地排序算法（如归并排序）是稳定的（即相等元素的相对顺序不变）。

稳定排序 (Stable Sorting)和非稳定排序

定义

稳定排序（Stable Sort）是指排序算法在排序后能保持相等元素的原始相对顺序。即，如果两个元素的值相同，排序后它们的相对位置与排序前一致。

非比较型排序和比较型排序