Question

插入排序和选择排序哪个算法更有效

Answer 1

一、选择排序
原理：将初始序列(A[0]~A[n-1])作为待排序序列，第一趟在待排序序列(A[0]~A[n-1])中找到最小值元素，将其与第一个元素A[0]交换，这样子序列(A[0])已经有序，下一趟在排序在待排序子序列(A[1]~A[n-1])中进行。第i趟排序在待排序子序列(A[i-1]~A[n-1])中找到最小值元素，与该子序列中第一个元素A[i-1]交换。经过 n-1 趟排序后使得初始序列有序。

其他说明：选择排序的最好、最坏和平均情况的时间复杂度都为O(n2)，而且它还需交换元素(n-1)次和移动元素3(n-1)次；它是不稳定的排序算法。
二、插入排序
原理：将初始序列中的第一个元素作为一个有序序列，然后将剩下的 n-1 个元素按关键字大小依次插入该有序序列，每插入一个元素后依然保持该序列有序，经过 n-1 趟排序后使初始序列有序。

其他说明：插入排序在最好的情况下时间复杂度为O(n)，比较次数为(n-1)次，移动元素次数是2(n-1)；最坏的情况下时间复杂度为O(n2)；插入排序是稳定的排序算法。
三、冒泡排序
原理：第一趟在序列(A[0]~A[n-1])中从前往后进行两个相邻元素的比较，若后者小，则交换，比较 n-1 次；第一趟排序结束，最大元素被交换到A[n-1]中，下一趟排序只需要在子序列(A[0]~A[n-2])中进行；冒泡排序最多进行 n-1 趟。基本的冒泡排序可以利用旗标的方式稍微减少一些比较的时间，当寻访完序列后都没有发生任何的交换动作，表示排序已经完成，而无需再进行之后的比较与交换动作。

其他说明：冒泡排序最好的情况下只需进行一趟排序，(n-1)次比较，此时的时间复杂度为O(n)，无需移动元素；最坏的情况下进行 n-1 趟排序，时间复杂度为O(n2)；冒泡排序是稳定的排序算法。

Answer 2

选择排序：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
选择排序是不稳定的。算法复杂度是O(n ^2 )。
插入排序：
每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
直接插入排序是稳定的。算法时间复杂度是O(n ^2)。