排序算法分类:
分类方法一:
简单排序(包括冒泡、插入、直接插入等),分治排序(快速、归并等)
分类二:
插入排序类(直接插入、shell排序)
交换排序类(冒泡、快速)
选择排序(直接选择、堆排序、选择书归并)
分配排序(桶排序、基数排序、索引排序)
1、直接插入排序
原地算法
最差时间复杂度O(n2)(原序列为逆序)
平均时间复杂度O(n2)
最佳时间复杂度O(n)(原序列是顺序)
对于短序列,直接插入排序比较有效
可以实现稳定排序
2、shell排序(缩小增量排序法)
利用了插入排序的两个优点(正序列排序时间O(n);对短序列较为有效)
效率比直接插入排序高。
增量序列需要考虑。
如果增量每次除以2递减,效果不佳。(原因:增量之间不互质)。平均时间复杂度是O(n2)。
如果采用hibbard的增量序列{2^k-1, 2^(k-1)-1, ....7,3,1}, 时间为O(n^3/2)
如果增量每次除以3递减,时间为O(n^3/2)
注意:最后要用增量为1的插入排序扫尾
非稳定排序
3、 冒泡排序
思想:不停比较相邻的记录,如果不满足排序要求,交换。一趟又一趟,直到所有的记录都排好序为止。
可以用NoSwap指示变量。如果某一趟没有交换,则不需要再冒泡了
可以实现稳定排序
最大、平均时间代价均为O(n2)