排序算法

排序算法目录

稳定

• 冒泡排序
• 插入排序
• 归并排序
• 计数排序
• 桶排序
• 基数排序
• 鸡尾酒排序
• 奇偶排序
• 二叉树排序
• Gnome Sort
• Tim Sort

不稳定

• 选择排序
• 快速排序
• 堆排序
• 希尔排序
• 梳排序
• 平滑排序
• Bitonic Sort
• Pancake Sort
• Stooge Sort

总结

1. 冒泡排序 (Bubble Sort)

• 描述：重复地遍历要排序的列表，比较相邻的元素并交换顺序，直到没有需要交换的元素为止。
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定

2. 选择排序 (Selection Sort)

• 描述：每次从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾。
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：不稳定

3. 插入排序 (Insertion Sort)

• 描述：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定

4. 归并排序 (Merge Sort)

• 描述：采用分治法，将数组分成两个子数组，分别排序，然后合并。
• 时间复杂度：O(n log n)
• 空间复杂度：O(n)
• 稳定性：稳定

5. 快速排序 (Quick Sort)

• 描述：采用分治法，从数组中选择一个基准元素，将数组分成两部分，一部分小于基准元素，另一部分大于基准元素，然后递归排序。
• 时间复杂度：O(n log n) 平均，O(n^2) 最坏
• 空间复杂度：O(log n) 平均，O(n) 最坏
• 稳定性：不稳定

6. 堆排序 (Heap Sort)

• 描述：利用堆这种数据结构来排序，首先构建一个最大堆，然后依次取出堆顶元素，调整堆结构。
• 时间复杂度：O(n log n)
• 空间复杂度：O(1)
• 稳定性：不稳定

7. 希尔排序 (Shell Sort)

• 描述：插入排序的一种改进，通过将数组分成若干子序列分别进行插入排序，逐步减少子序列的间隔，最终进行一次插入排序。
• 时间复杂度：O(n log n) 到 O(n^2) 之间，取决于间隔序列
• 空间复杂度：O(1)
• 稳定性：不稳定

8. 计数排序 (Counting Sort)

• 描述：适用于一定范围内的整数排序，通过计数数组记录每个元素出现的次数，然后依次输出。
• 时间复杂度：O(n + k)，其中 k 是整数范围
• 空间复杂度：O(n + k)
• 稳定性：稳定

9. 桶排序 (Bucket Sort)

• 描述：将数组元素分到有限数量的桶中，每个桶内分别排序，然后合并。
• 时间复杂度：O(n + k)，其中 k 是桶的数量
• 空间复杂度：O(n + k)
• 稳定性：稳定

10. 基数排序 (Radix Sort)

• 描述：对每个数位进行排序，从最低位到最高位，依次进行。
• 时间复杂度：O(n * k)，其中 k 是数位的数量
• 空间复杂度：O(n + k)
• 稳定性：稳定

11. 鸡尾酒排序 (Cocktail Shaker Sort)

• 描述：冒泡排序的一种变种，双向进行排序，先从左到右，再从右到左，交替进行。
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定

12. 梳排序 (Comb Sort)

• 描述：改进的冒泡排序，通过逐渐减少间隔来比较和交换元素，最终变为冒泡排序。
• 时间复杂度：O(n^2) 最坏，O(n log n) 平均
• 空间复杂度：O(1)
• 稳定性：不稳定

13. 奇偶排序 (Odd-Even Sort)

• 描述：并行排序算法的一种，交替比较和交换奇数和偶数索引的元素。
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定

14. 二叉树排序 (Binary Tree Sort)

• 描述：将元素插入二叉搜索树，然后进行中序遍历得到有序序列。
• 时间复杂度：O(n log n) 平均，O(n^2) 最坏
• 空间复杂度：O(n)
• 稳定性：稳定

15. 平滑排序 (Smooth Sort)

• 描述：堆排序的一种改进，利用斐波那契堆来减少比较次数。
• 时间复杂度：O(n log n)
• 空间复杂度：O(1)
• 稳定性：不稳定

16. Gnome Sort

• 描述：类似插入排序，通过逐步交换相邻元素来排序。
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定

17. Tim Sort

• 描述：归并排序和插入排序的混合算法，Python 和 Java 的内置排序算法。
• 时间复杂度：O(n log n)
• 空间复杂度：O(n)
• 稳定性：稳定

18. Bitonic Sort

• 描述：并行排序算法的一种，适用于并行计算环境。
• 时间复杂度：O(n log^2 n)
• 空间复杂度：O(n log n)
• 稳定性：不稳定

19. Pancake Sort

• 描述：通过翻转子数组来排序，类似于煎饼翻转。
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：不稳定

20. Stooge Sort

• 描述：递归排序算法，通过递归地排序子数组的前2/3和后2/3来排序。
• 时间复杂度：O(n^(log 3 / log 1.5)) ≈ O(n^2.71)
• 空间复杂度：O(n)
• 稳定性：不稳定

二叉树排序算法利用二叉树的数据结构来对元素进行排序。以下是几种常见的二叉树排序算法：

1. 二叉搜索树排序 (Binary Search Tree Sort)

• 描述：通过构建二叉搜索树（BST），然后进行中序遍历来获得有序序列。
• 步骤：
  1. 将所有元素插入二叉搜索树。
  2. 对二叉搜索树进行中序遍历，得到排序后的序列。
• 时间复杂度：
  • 平均情况：O(n log n)
  • 最坏情况：O(n^2)（当树退化为链表时）
• 空间复杂度：O(n)
• 稳定性：不稳定

2. 平衡二叉搜索树排序 (Balanced Binary Search Tree Sort)

• 描述：通过构建平衡二叉搜索树（如 AVL 树或红黑树），然后进行中序遍历来获得有序序列。
• 步骤：
  1. 将所有元素插入平衡二叉搜索树。
  2. 对平衡二叉搜索树进行中序遍历，得到排序后的序列。
• 时间复杂度：O(n log n)
• 空间复杂度：O(n)
• 稳定性：不稳定

3. 堆排序 (Heap Sort)

• 描述：利用二叉堆（通常是最大堆或最小堆）来进行排序。
• 步骤：
  1. 将所有元素插入二叉堆。
  2. 反复从堆中取出最大（或最小）元素，重建堆，直到堆为空。
• 时间复杂度：O(n log n)
• 空间复杂度：O(1)（原地排序）
• 稳定性：不稳定

4. 树状数组排序 (Fenwick Tree Sort)

• 描述：利用树状数组（Fenwick Tree）来进行排序，通常用于处理动态数据。
• 步骤：
  1. 初始化树状数组。
  2. 根据元素的值更新树状数组。
  3. 根据树状数组的状态输出排序后的序列。
• 时间复杂度：O(n log n)
• 空间复杂度：O(n)
• 稳定性：不稳定

5. Treap 排序

• 描述：Treap 是一种结合了二叉搜索树和堆的数据结构，通过随机优先级来保持平衡。
• 步骤：
  1. 将所有元素插入 Treap。
  2. 对 Treap 进行中序遍历，得到排序后的序列。
• 时间复杂度：O(n log n)
• 空间复杂度：O(n)
• 稳定性：不稳定

6. Splay 树排序 (Splay Tree Sort)

• 描述：Splay 树是一种自调整二叉搜索树，通过旋转操作将最近访问的节点移到根节点。
• 步骤：
  1. 将所有元素插入 Splay 树。
  2. 对 Splay 树进行中序遍历，得到排序后的序列。
• 时间复杂度：O(n log n) 平均，O(n^2) 最坏
• 空间复杂度：O(n)
• 稳定性：不稳定

总结

这些二叉树排序算法各有特点和适用场景，选择合适的算法取决于具体的应用需求和数据特性。二叉搜索树排序和平衡二叉搜索树排序适用于需要动态插入和删除的场景，而堆排序则适用于需要原地排序的场景。Treap 和 Splay 树提供了自调整的特性，可以在某些情况下提高性能。