• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    5年前 (2013-05-12)  算法/数据结构 |   5 条评论  14 
    文章评分 0 次,平均分 0.0

    排序是笔试面试中经常考的,赫,当然还有很多改进可以用于其他场合,下面来详细看看。以整数数组a[N]为例。

    1.插入排序。
    顾名思义,就是找到该元素的正确位置后插入。从最开始集合中只有一个元素,到后来的集合中N个元素。插入排序为了给元素找位置,需要进行大量的移动。
    2.选择排序
    顾名思义,就是从一大堆元素中选择合适的元素来安排。从最开始集合中有N个元素待选择,到后来的0个元素待选择。
    3.交换排序
    顾名思义,就是通过两个元素之间交换位置的方式来进行排列。
    排序算法种类与分析

    排序算法种类与分析
    冒泡排序:在已经有序的情况,取得O(N)的复杂度。
    快速排序:每次递归都是N的复杂度,递归次数根据序列有关系,当已经有序的情况下,递归N次,时间复杂度为O(N*LogN)
    插入排序:在已经有序的情况,取得O(N)的复杂度。
    希尔排序:最差时间和平均时间都要根据步长数组来判断,现在最好算法的最差时间复杂度,为O(N*LogN)。空间主要是步长数组需要的。一般步长之间不要存在公因子。
    插入排序:交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。
    堆排序: 堆排序属于选择排序,选择N-1次,每次从堆中选择一个,因此最差就是N*LogN。最好的时间无法准确估计,基本上也是N*LogN这个程度。
    归并排序:这个排序算法的复杂度与数组初始化序列无关,归并次数为LogN次,每次复杂度是O(N),因此复杂度都是O(N*LogN)
    基数排序:K是数组中,数值的最大位数。对于int来说,使用十进制的话,K<=10。稳定性来说,基数排序要求每次必须使用稳定排序,否则最终得不到正确结果。所以这里的稳定是必须的,而不可能存在不稳定的。而其他的排序,比如冒泡排序,可以改写成不稳定的,这点需要注意。 计数排序:K是数组中,数值的范围,即K=Max-Min+1。对于int来说,最坏的情况为K=2^32,即数组内包含了最大正数和最小负数。 桶排序:由于桶排序可能有的桶没有数据,那么假设N个数据,只被分到了M个桶中,O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM) =O(N+N*(logN-logM)),当分到的桶越多时,越是接近N。计数排序可以看作桶排序的一个特例,将桶开的很大,直到能够保证每个不同的数值都被分到一个桶中。

     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/1118.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享