八大排序 (上)
@TOC
一、 直接插入排序
1.概念
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列
2.直接插入排序的实现
直接插入排序的时间复杂度
二、 希尔排序
1.概念
思想为 :先选定一个整数,把 待排序文件中所有记录分组,所有距离内的记录在同一组中,再对每一组内的记录进行排序,重复分组和排序, 直到=1 时结束.
希尔是直接插入排序的优化 1.先进行预排序,让数组接近有序 2.直接插入排序
此时发现: 多组间隔为 gap 的预排序,gap 由大变小 gap 越大,大的数越快到后面,小的数越快到前面 gap 越大,预排完,越不接近有序,gap 越小,预排完,越接近有序当 gap=1 时,就时直接插入排序
2. 希尔排序的实现
3. 希尔排序的时间复杂度
gap=n , gap=gap/3+1 即 n=n/3+1 假设 x 为操作次数 3^x=n+1 x=log 3 n+1 时间复杂度为 O(log 3 N)
2.预排序会使数组接近有序 ,如 gap=1 时 ,就为直接插入排序,时间复杂度为 O(N)
希尔排序 整体时间复杂度为 O(N *log 3 N )
三、 直接选择排序
1.直接选择排序的实现
2.注意事项
3.直接选择排序的时间复杂度
直接选择排序 ,无论 数组处于 有序 (最好情况下),还是无序 (最坏情况下) 都需要将整个数组遍历一遍 ,时间复杂度为 O(N^2)
四、 堆排序
点击这里 :堆排序详解
五、冒泡排序
1.冒泡排序的实现
2.冒泡排序的时间复杂度
正常情况下:第一趟时,共比较 n-1 次 ,第二趟时,共比较 n-2 次,第 n-1 趟时,共比较 1 次操作次数为: n-1+n-2+n-3+.......+1=n(n-1)/2 通过大 O 渐进法省略 ,时间复杂度为 O(N^2)
最好情况下:数组为有序时 ,如 : 1 2 3 4 5 正好排升序,遍历一遍后发现并没有进入交换中,exchange==0 则跳出循环。时间复杂度为 O(N)
3.冒泡排序与直接插入排序谁更好?
当数组接近有序时 ,如: 1 2 3 5 4 61.冒泡排序:
2.直接插入排序:1 2 3 5 4 6
时间复杂度为 O(N)
则直接插入排序更优
版权声明: 本文为 InfoQ 作者【lovevivi】的原创文章。
原文链接:【http://xie.infoq.cn/article/d5b5088706c272bbe3b46ffca】。文章转载请联系作者。
评论