数据从结构中各种排序方法的综合比较

提示：排序是计算机程序设计中一个非常重要的操作，它将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列,在有序的序列中查找元素的效率很高，但是无序序列只能逐一查找，因此，如何进行排序，尤其是高效排序，是一个重要的课题。

• 前言
• 一、时间性能
• 二、空间性能
• 三、排序方法的稳定性能
• 四、排序方法的时间复杂度的下限
• 总结

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排 序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

提示：以下是本篇文章正文内容，下面案例可供参考

1、平均的时间性能
时间复杂度为 O(nlog₂n)：快速排序、堆排序和归并排序
时间复杂度为 O(n²)：直接插入排序、冒泡排序和简单选择排序

2、当待排记录序列按关键字顺序有序时
直接插入排序和起泡排序能达到 O(n) 的时间复杂度，
快速排序的时间性能蜕化为 O(n²)

3.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

指的是排序过程中所需的辅助空间大小

1、所有的简单排序方法 (包括：直接插入、起泡和简单选择) 和堆排序的空间复杂度为 O(1)

2、快速排序为O(log₂n)，为递归程序执行过程中，栈所需的辅助空间

3、归并排序所需辅助空间最多，其空间复杂度为O(n);

1、快速排序、简单选择排序、堆排序和希尔排序是不稳定的排序方法

2、对于不稳定的排序方法，只要能举出一个实例说明即可

以上链接中讨论的各种排序方法都是基于 “比较关键字” 进行排序的排序方法。

可以证明，这类排序法可能达到的最快的时间复杂度为O(nlogn)

这里用张图代替总结