各大排序的性质分析

1. 排序算法可以分为两类：

• 内部排序是指在排序期间元素全部存放在内存中
• 外部排序是指在排序期间元素无法全部同时存放在内存中，必须在排序过程中根据要求不断地在内外存之间移动

内部排序算法的性能取决于算法的时间和空间复杂度，而时间复杂度一般是由比较和移动的次数来决定的。

2. 希尔排序：又称缩小增量排序
   基本思想：先将待排序表分成若干个形如 L[i, i+d, i+2d, ... , i+kd] 的子表，分别进行直接插入排序，当整个表中的元素已经基本有序时，再对全体记录进行一次直接插入排序。

3. 快速排序
   快速排序的时间效率与划分是否对称有关。最坏情况下两个区域分别包含n-1个元素和0个元素，这种最大程度的不对称性若发生在每一层递归上，即初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度O(n^2)。
   有多种方法提高快排的效率：一种是当递归过程划分得到的子序列规模较小时不再继续递归调用快排，而是采用直接插入排序进行后续的排序工作。另一种方法是尽量选取一个可以将数据中分的基准元素，比如随机从当前表中选取基准元素，使得最坏情况基本不发生。
   在快速排序中并不产生有序子序列，但每一趟排序将一个基准元素放到其最终位置上

4. 堆排序
   建堆的时间复杂度为O(n)，说明可以在线性时间复杂度内将一个无序数组建成一个大顶堆。
   然后输出堆顶元素，再将堆底元素送入堆顶，此时堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复n-1次，直到堆中只剩下一个元素为止。
   建堆时间为O(n)，之后有n-1次向下调整，每次调整的时间与树高有关，时间复杂度为O(h)，故堆排序的时间复杂度为O(nlogn)。

5. 归并排序
   归并排序需要n个单元的辅助空间用来进行合并操作，空间复杂度为O(n)
   每一趟归并的时间复杂度为O(n)，共需进行logn趟归并，所以时间复杂度为O(nlogn)

6. 基数排序
   空间效率：一趟排序需要辅助空间为r（r个队列），r为数字的基数，比如10。但在以后的排序中重复使用这些队列，故基数排序的空间复杂度为O(r)
   时间效率：需要进行d 趟分配和收集，d为关键字的位数，一趟分配需要O(n)，即将各个元素送入相应队列中；一趟收集需要O(r)，即把r个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的线性表。所以基数排序的时间复杂度为O(d(n+r))，它与序列的初始状态无关。

7. 总结
   直接插入排序和冒泡排序在最好情况下的时间复杂度可以达到O(n)，而简单选择排序与序列的初始状态无关，始终为O(n^2)。
   归并排序分割子序列与初始序列的排列无关，因此它的最好、最坏和平均时间复杂度均为O(nlogn)。
   插入排序，冒泡排序，归并排序和基数排序都是稳定的排序方法，而简单选择排序，快速排序，希尔排序和堆排序都是不稳定的排序方法。
   快速排序和堆排序都是不稳定的，如果要求排序稳定并且时间复杂度为O(nlogn)，则可以选用归并排序 。