《iOS开发快速进阶与实战(移动互联网开发技术丛书)》:
排序算法是算法中一个比较常见的知识点,主要功能是对一个乱序数组进行排序,为了达到更少的计算量,对一些排序方法进行了命名,其中比较出名的8大排序算法是: 冒泡排序,选择排序,希尔排序,快速排序,归并排序,堆排序,基数排序。
如果不涉及架构方面,以及多重计算优化的话,算法其实并不常用,当然在很多比较大的公司的面试题中,算法是一个比较重要的考察方面,并且考察的算法主要就是排序算法和二叉树。而在面试排序算法中,主要考察的排序并不是全部的8大算法,主要分为三个层次: ①手写冒泡排序; ②了解冒泡、选择、快速排序,并以伪代码形式写出; ③除了前面两个层次,需要对剩下的排序算法有了解,并可以简单说出原理。这是面试题中关于考算法的三个等级,一般的公司不强求算法的话都只要求掌握第一个就行了,而大一些的公司,例如BAT,需要掌握到第二个层次,而第三个层次基本上没有公司会考到,当然不排除有些主攻算法的面试官会问到,所以这里对所有的排序算法进行分析讲解,希望读者们在以后的面试算法中能够轻松应付。
由于ObjectiveC的数组和字典不能存储值类型、结构体,也就是包括int、NSInteger、BOOL、CGRect类型都不能直接存储,需要转换成NSNumber或者NSValue来存储。所以为了展示排序算法,我们采用Swift语言来实现,首先Swift相比于ObjectiveC来说不区分可变和不可变数组,另外,Swift的数组和字典属于值类型,并且可以存储基本数据类型,甚至是nil也可以。……。事实上,我们可以将partition放在快速排序的函数体内,成为其私有的函数,从而体现完整性,不过这里暂且只讨论算法,所以不做考虑。
可以从代码中看出,partition函数是将数组的某一区域进行一个简单的排序划分,获取到划分的位置,根据其位置再将数组划分为两个区域,然后分别递归调用快速排序函数。
接下来根据数组以及代码详细分析一下排序过程。
我们传递的数组是[2, 1, 5, 9, 4, 0, 6, 3, 8, 7],并且传递了数组的一个区域,表示在该区域里执行。……进入quickSort函数,由于数组个数至少是大于1的(个数为0或者为1没有必要排序),所以执行partition函数,partition函数是快速排序的要点所在,接下来,我们调用partition函数传递的参数,仍然是该数组以及其整个范围。鉴于Swift的参数默认为let不可修改,所以可以使用同arr参数类似的inout修饰,但这将使整个函数显得过于冗杂,因此在partition内创建同名的局部变量left、right,并且记录区域的第一个值pivot为arr[left],我们称其为比较数,然后便开始while循环了。
……