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