排序算法折半插入排序and​简单选择排序（）折半插入排序：为什么比较次数最少与最多同,都是n*log2n,最多时间复杂度为O(n2)?简单选择排序：为什么比较次数均是n(n-1)/2;移动次数最少

Question

排序算法 折半插入排序and​简单选择排序（）
折半插入排序：为什么 比较次数 最少与最多同,都是n*log2n,最多时间复杂度为O(n2)?
简单选择排序：为什么 比较次数均是n(n-1)/2; 移动次数最少为0,最多为3(n-1)?

Answer 1

折半插入排序：我对这些名称比较模糊,但如果没有猜错,应该是快速排序算法这样子的算法,或者更准确点,有一个排序算法叫做归并排序算法.因为每次都取半,而且要处理所有元素,所以理论时间时间效率是O(nlogn).但是这一类算法在一定情况下会退化成O(n^2),根据算法原理,逆向思维构造数据,是可以让算法卡出翔的.所以延伸出了随机快速排序算法这一类算法.
简单选择排序：这个算法比较简单,一共有n个元素,每个元素俩俩之间比较,肯定需要O(n^2)的时间复杂度.至于移动次数,跟算法中的比较函数有关系.当且仅当两个元素为逆序对的时候才尽享移动,所以移动次数最少可以为0,即序列在一开始就为有序.最多为3(n-1)次,因为移动元素需要n-1次,而每次做出移动需要一个辅助空间,即t = a,a = b,b = t,这就是常数3的由来.
本人大学生ACMer,看到这个问题就手打了一下,我以上所有回答都需要斟酌,不排除有出错的地方.恳请发现错误的网友帮忙斧正,@海胖博客