排序算法之冒泡排序、选择排序、插入排序的区别与联系

冒泡排序

（1）算法：

假如有N项数据。第一趟，将首项与第二项比较，较小者放在前面，较大者放后面，然后比较第二项和第三项，依次进行，第一趟结束，最大项排在最后一个位置；第二趟，比较前N-1项，将首项与第二项比较，较小者放在前面，较大者放后面，然后比较第二项和第三项，依次进行，第二趟结束，次大项排在倒数第二个位置；……，最后，排序结束。共进行N-1趟。在比较之后，立马进行交换。

（2）时间复杂度：不考虑被排序数据的类型，算法时间复杂度：O( n^2 )

比较所需的时间：（ N-1) + (N-2) +...+2+1 = N*(N-1) / 2= N^2 / 2

交换所需时间：每次交换视为常数，平均交换时间为 （ 0 + N^2 / 2）/ 2 = N^2 / 4

共需时间：N^2 / 2 + N^2 / 4 = 3* N^2 / 4

选择排序

（1）算法：在冒泡排序上做了优化，减少了交换次数

假如有N项数据。第一趟，从N个数据中选出最小的那一项，放到第一个位置；第二趟，从第二个开始，共N-1个数据中选最小的，放到第二个位置；……；共进行N-1趟。在循环中进行比较，然后在循环外面进行交换，所以交换次数少于比较次数。

（2）时间复杂度：不考虑被排序数据的类型，算法时间复杂度：O( n^2 )

比较所需的时间：（ N-1) + (N-2) +...+2+1 = N*(N-1) / 2= N^2 / 2

交换所需时间： （0 + （N-1））/ 2 = （N-1） / 2 

总时间：N^2 / 2 +（N-1）/ 2 

插入排序

（1）算法：

要求：在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序。

核心：始终定义第一个元素为有序的，将元素逐个插入到有序排列之中，其特点是要不断的移动数据，空出一个适当的位置，把待插入的元素放到里面去。

思路：用一个临时变量存放待排序的数字；从数组前依次遍历找第一个比待排序数字大的数字的位置；将从待排序的数字位置开始，到找的要插入的数字的位置之间的数字向后挪一位，最后将待排序数字插入到找到的位置；

（2）时间复杂度：不考虑被排序数据的类型，算法时间复杂度：O( n^2 )

比较的时间：第一趟最多比较一次，第二趟最多比较俩次，最后一趟比较N-1次，最终，最多比较N*(N-1)/2趟；

交换的时间：与冒泡排序的时间相同，每次交换视为常数，平均交换时间为 （ 0 + N^2 / 2）/ 2 = N^2 / 4

总时间：N*(N-1)/2 + N^2 / 4

（3）区别：

和前两个排序算法不同，插入排序在排序过程中是局部有序，随着插入项的增多，有序部分的项的位置会发生改变，而冒泡排序和选择排序每轮确定的项数的位置是永远不变的。