专题课程
我们平常用的排序算法一般就以下几种：
这些算法具体的定义本文不再赘述。一般情况下，好的排序算法性能是O(nlogn)，坏的性能是O(n^2)。本文在此用swift示范实现归并排序：
表格中有一个特例是桶排序，它是将输入的数组分配到一定数量的空桶中，每个空桶再单独排序。当输入的数组是均匀分配时，桶排序的时间复杂度为O(n)。举个微软的面试题来当例子：
有三种颜色（红，黄，蓝）的球若干，要求将所有红色的球放在黄色球的前面，最后放上所有的蓝色球。
这道题目最直接的解法就是桶排序。首先第一次遍历，统计有多少个红色球（假设x个），多少个黄色球（假设y个），和多少个蓝色球（假设z个）。然后再一次遍历，数组前部x个位置填充红色球，中间y个位置放上对应数量的黄色球，最后z个位置再放上蓝色球。
另外解释一下稳定的意思：相等的键值，如果排过序后与原来未排序的次序相同，则称此排序算法为稳定。举个例子：
我们注意到排序算法一和二的区别就在于对[1, 3], [1, 4]这两个元素的处理。排序算法一中，这两个元素位置与原数组相同，故称其为稳定算法。而排序算法二则是不稳定算法。
Swift中，排序的使用如下：
在其他语言比如Java中，其自带的sort函数是用归并排序实现的。而在Swift源代码中，sort函数采用的是一种内审算法(IntroSort)。它由堆排序、插入排序、快速排序三种算法构成，依据输入的深度相应选择最佳的算法来完成。本文关注的重点是实战，所以不做展开。对源代码感兴趣的朋友可以去Github读苹果的Swift的开源库。
收藏(0)
赞 
粤公网安备44010602001432号