1、插入排序：（在有序的序列中插入新的元素使其仍有序）
(a)直接插入排序：适用于待排序的长度比较小的情况：
最小的比较次数（元素非递减排列）：n-1,元素不需要移动；
最大的比较次数（元素非递增排列）：（n+2)(n-1)/2，移动次数：(n+4)(n-1)/2
故算法的平均时间复杂度为O(n^2)
（b）折半插入排序：在插入新的元素时，应为已有的序列时有序的，所以可以通过折半查找的方式确定待排序元素所在的位置。其时间复杂度仍未：O(n^2)
(c)希尔排序O(n^3/2)：若待排序的序列时基本有序时，可以减少比较次数，由此减小时间复杂度。希尔排序基于此，将序列分成若干组后依次进行排序：如下图：
图1 希尔排序2、快速排序(O(nlogn))：
平均时间上，是目前最好的一种内部排序方法，对冒泡排序的一种改进，冒泡排序的时间复杂度为O(n^2)。但若序列基本有序时，会退化成冒泡排序。
通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序。如下图：
图2 快速排序3、选择排序：最小的元素需要通过比较序列中的元素中n个值外，次小的值可以基于前一次的比较，而不需要再进行n-1次比较。如：树形选择排序（nlogn），堆排序（nlogn）
图 树形选择排序
4、归并排序（O(nlogn)）:
图 归并排序
网友评论