Question

排序算法之直接插入排序和冒泡排序

Answer 1

直接插入排序是个稳定的排序算法,适用于关键码n较小,在已知关键码基本有序情况(最好的情况,时间复杂度为0(n),只比较元素n-1次,不移动元素),最坏的情况下时间复杂度为0(n^2),比较元素次数为n (n-1)/2,移动元素次数为(n+3) (n -2)/2,空间复杂度为0(1)

下面实现直接插入排序(递增序列)

冒泡排序也是一个稳定的排序,在待排关键码基本有序的情况下,只需要(n-1)次比较,不需要交换元素(O(n),1趟排序),关键码逆序的情况下,需要n(n-1)/2次比较,关键码n(n -1)/2次交换(O(n^2),n-1趟排序)

冒泡排序的实现(递增序列):

直接插入排序和冒泡排序,时间复杂度和空间复杂度相同,但直接插入排序关键码移动次数明显比冒泡排序少,实际应用直接插入排序更加有效,更广.