Question

各种排序算法最好和最坏情况比较

Answer 1

最坏情况下比较次数最少的为D）堆排序：
A）冒泡排序 需要比较O(n^2)次（n(n - 1)/2次），即序列逆序的情况
B）简单选择排序，无论是否最坏都需要O(n^2)次（n(n - 1)/2次）
C）直接插入排序，最坏情况需要比较O(n^2)次（n(n - 1)/2次）
D）堆排序，无论是否最坏比较O(nlog2n)次
E）快速排序，最坏情况退化为冒泡排序，需要比较O(n^2)次（n(n - 1)/2次）

Answer 2

都不知道怎么回答，各种排序说的也太多了，这里讲几种简单的吧，希望对你有帮助！
比如n个顺序存储元素进行排序，a[0]做“哨兵”（即a[0]不存数据，而是用作辅存空间使用）的情况
1 直接插入排序：比较次数 最少n-1次；最多(n-1)(n+2)/2
移动次数 最少0； 最多(n-1)(n+4)/2
使用一个辅助存储空间，是稳定的排序；

2 折半插入排序：比较次数 最少与最多同，都是n*log2n（其中2为底，下边表示同），
移动次数 最少0，最多时间复杂度为O(n2);(n的平方，以下也如此表示)；
使用一个辅助存储空间，是稳定的排序；

3 冒泡排序： 比较最少为：n-1次，最多时间复杂度表示为o(n2);
移动次数最少为0，最多时间复杂度表示为O(n2);
使用一个辅存空间，是稳定的排序；

4 简单选择排序： 比较次数没有多少之分，均是n(n-1)/2;
移动次数最少为0，最多为3(n-1);
使用一个辅存空间，是稳定的排序；

5 快速排序：比较和移动次数最少时间复杂度表示为O(n*log2n);
比较和移动次数最多的时间复杂度表示为O(n2);
使用的辅助存储空间最少为log2n，最多为n的平方；是不稳定的排序；

6 堆排序： 比较和移动次数没有好坏之分，都是O(n*log2n);
使用一个辅存空间，是不稳定的排序；

7 2-路归并排序：比较和移动次数没有好坏之分，都是O(n*log2n);
需要n个辅助存储空间，是稳定的排序；

另外还有很多的排序方法如 希尔排序，基数排序，2-路插入排序 等等很多的排序方法，这里就不一一列举了，希望列举的对你有帮助！