首页 > algorithm > 排序6(线性时间排序)

排序6(线性时间排序)

  今天看了《算法导论》第八章,这一章介绍了三种排序的思路:计数排序,基数排序,还有桶排序。
  计数排序,就是用一个辅助数组记录每一个数的出现次数。然后,把数挨着放进去,排序。这不是一个排序算法,因为元素之间没有存在比较。计数排序比较稳定,常作为基数排序的一个子过程。
  基数排序,一种老式穿卡机上的算法,就是在多位数中,排序从低位到高位排序,这让我想起对年月日进行排序,用这种方法绝对不错。先对日,再对月,最后对年进行排序。
  桶排序,就是在一个小范围内的输入,不能太大,就是存储有点类似于hash吧!不过hash是随机的,这个是按顺序存储的。形象上,就是摆一排顺序的桶,然后把数据按一定顺序落在桶中。整个桶排序算法就以线性期望时间运行。
  好了,以上三种算法都是以线性时间排序。都是用一些非比较的一些操作来确定排序的顺序。到目前为止,已经有了7种比较排序的方法,这三种还见的不太多(可能见识的少吧!)。觉得有用的还是基数排序的进行排日期的那种思维,这中思路还是值得借鉴的。

  1. Nicole 9月 2nd, 2012 @ 08:07 | #1

    That’s a smart asnewr to a tricky question

评论提交中, 请稍候...

留言


可以使用的标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
Trackbacks & Pingbacks ( 0 )
  1. 还没有 trackbacks