几种排序的总结_n个记录直接插入排序,最小比较次数

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个辅助存储空间，是稳定的排序；