下载安卓APP箭头
箭头给我发消息

客服QQ:3315713922
论坛 >编程语言 >Swift 算法实战之路:排序(基本概念)

Swift 算法实战之路:排序(基本概念)

课课家iOS游客发布于 2017-09-14 09:10查看:914回复:1

    基本概念

        我们平常用的排序算法一般就以下几种:

image.png

        这些算法具体的定义本文不再赘述。一般情况下,好的排序算法性能是O(nlogn),坏的性能是O(n^2)。本文在此用swift示范实现归并排序:

image.png

        表格中有一个特例是桶排序,它是将输入的数组分配到一定数量的空桶中,每个空桶再单独排序。当输入的数组是均匀分配时,桶排序的时间复杂度为O(n)。举个微软的面试题来当例子:

        有三种颜色(红,黄,蓝)的球若干,要求将所有红色的球放在黄色球的前面,最后放上所有的蓝色球。

        这道题目最直接的解法就是桶排序。首先第一次遍历,统计有多少个红色球(假设x个),多少个黄色球(假设y个),和多少个蓝色球(假设z个)。然后再一次遍历,数组前部x个位置填充红色球,中间y个位置放上对应数量的黄色球,最后z个位置再放上蓝色球。

        另外解释一下稳定的意思:相等的键值,如果排过序后与原来未排序的次序相同,则称此排序算法为稳定。举个例子:

image.png

        我们注意到排序算法一和二的区别就在于对[1, 3], [1, 4]这两个元素的处理。排序算法一中,这两个元素位置与原数组相同,故称其为稳定算法。而排序算法二则是不稳定算法。

        Swift中,排序的使用如下:

image.png

        在其他语言比如Java中,其自带的sort函数是用归并排序实现的。而在Swift源代码中,sort函数采用的是一种内审算法(IntroSort)。它由堆排序、插入排序、快速排序三种算法构成,依据输入的深度相应选择最佳的算法来完成。本文关注的重点是实战,所以不做展开。对源代码感兴趣的朋友可以去Github读苹果的Swift的开源库。


收藏(0)0
查看评分情况

全部评分

此主贴暂时没有点赞评分

总计:0

回复分享

版主推荐

    共有1条评论

    • 课课家运营团队
    • 酸酸~甜甜
    • Mr ken
    • YUI
    • cappuccino
    • mr jack
    • IT宅男
    • Mright
    • 课课家技术团队1
    • 选择版块:

    • 标题:

    • 内容

    • 验证码:

    • 标题:

    • 内容

    • 选择版块:

    移动帖子x

    移动到: