0.x 6.如何对一组数据进行排序？

dddd数据结构课本

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

首先，应该列举出所有的排序算法。

• O(n^2)级别的：起泡，直接插入排序，简单选择排序
• O(n^1.5)级别的：希尔排序（直接插入排序的升级版）
• O(nlogn)级别的：堆排序，快速排序，归并排序
• O(m+n):桶排序，m为桶的数量，n为待排元素数量

理论上，快速排序是最快的排序算法。
但是，并不是所有情况下，一定会选择快速排序，it depends这组数据有什么特征：

• 大量重复元素（三路快排）
• 近乎有序（直接插入排序）
• 取值范围有限，但是待排序元素很多，比如四川省高考成绩（桶排序）
• 问题规模小，而且元素很大（简单选择排序，交换次数最少的排序）
• 是否是使用链表存储（归并，快速排序需要随机访问迭代器）

有没有额外要求：

• 稳定性（快速排序不稳定，归并排序稳定）
• 空间要求（堆排序空间需求最少）
• 数据量非常大，不能放在内存（外排序）

各种排序算法实现