用Objective-C实现几种基本的排序算法,并把排序的过程图形化显示。其实算法还是挺有趣的 ^ ^.
以升序为例。
选择排序比较好理解,一句话概括就是依次按位置挑选出适合此位置的元素来填充。
选择排序.gif
以下方法在NSMutableArray+JXSort.m
中实现
冒泡排序.gif
插入排序是从一个乱序的数组中依次取值,插入到一个已经排好序的数组中。 这看起来好像要两个数组才能完成,但如果只想在同一个数组内排序,也是可以的。此时需要想象出两个区域:前方有序区和后方乱序区。
插入排序.gif
快排的版本有好几种,粗略可分为:
这里只讨论原始的快排。
关于在快排过程中何时进行交换以及交换谁的问题,我看见两种不同的思路:
第1种思路可以有效降低交换频率,在游标相遇后再对枢轴进行定位,这步会导致略微增加了比较的次数;
第2种思路交换操作会比较频繁,但是在交换的过程中同时也把枢轴的位置不断进行更新,当游标相遇时,枢轴的定位也完成了。 在两种思路都尝试实现过后,我还是喜欢第2种,即便交换操作会多一些,但实质上的交换只是对数组特定位置的赋值,这种操作还是挺快的。
pivot
,它将会在一趟排序中不断被移动位置,只终移动到位于整个数组的正确位置上。i
,指向待排序数组的首位,它将会不断向后移动;
再记一个游标j
,指向待排序数组的末位,它将会不断向前移动。
这样可以预见的是,i
、j
终有相遇时,当它们相遇的时候,就是这趟排序完成时。j
从后往前扫描,寻找比枢轴小的元素x
,找到后停下来,准备把这个元素扔到前方去。pivot
,所以当前它们的位置关系是pivot ... x
。
又排序目标是升序,x
是个小值却放在了pivot
的后方,不妥,需要交换它们的位置。x ... pivot
。此时j
指向了pivot
,i
指向了x
。i
向后扫描,寻找比枢轴大的元素y
,找到后停下来,与pivot
进行交换。
完成后的位置关系是pivot ... y
,此时i
指向pivot,即pivot移到了i
的位置。i
向后扫描开始时,i
是指向x
的,而在上一轮j
游标的扫描中我们已经知道x
是比pivot
小的,所以完全可以让i
跳过x
,不需要拿着x
和pivot
再比较一次。
结论是在j
游标的交换完成后,顺便把i
往后移一位,i ++
。
同理,在i
游标的交换完成后,顺便把j
往前移一位,j --
。i
和j
相遇时,i
和j
都会指向pivot
。在我们的分区方法里,把i
返回,即在分区完成后把枢轴位置返回。快速排序是很天才的设计,实现不复杂,关键是它真的很快~
快速排序.gif
现在讲下UI的实现思路。
NSMutableArray+JXSort.h
从前面的排序代码可以看到,我是给NSMutableArray
写了个分类,排序逻辑写在分类里面,完全与视图无关。
外部调用者只需要传入两个参数:
comparator
代码块。这是遵循苹果原有API的风格设计,在需要比较数组内的两个元素时,排序方法将会调用这个代码块,回传需要比较的两个元素给外部调用者,由外部调用者实现比较逻辑,并返回比较结果给排序方法。exchangeCallback
代码块。这个参数是实现视图变化的关键。排序方法在每次完成两个元素的交换时,都会调用这个代码块。外部调用者,比如ViewController就可以知道排序元素每一次变换位置的时机,从而同步视图的变化。视图控制器持有待排序的数组,这个数组是100条细长的矩形,长度随机。
由于我们加强了NSMutableArray
,它现在可以支持多种指定类型的排序了,同时也可以把排序过程反馈给我们,当需要给barArray
排序时,只需要这样调用:
每一次didExchange的回调,ViewController都会对两个视图的位置进行交换。如此形成不断进行排序的视觉效果。
控制排序速度
为了能够让肉眼感知排序的过程,我们需要放慢排序的过程。
这里我的办法是延长两个元素比较操作的耗时,大约延长到0.002秒。结果很明显,当某个算法所需要进行的比较操作越少时,它排序就会越快(根据上面四张图的比较,毫无疑问快排所进行的比较操作是最少啦~)。
那么如何模拟出比较操作的耗时时间呢?
这里我的办法是借助信号量,在两条线程间通讯。
1.让排序在子线程中进行,当需要进行比较操作时,阻塞线程,等待信号的到来。这里的思想是得到一个信号才能进行一次比较。
2.主线程启用定时器,每隔0.002秒发出一个信号,唤醒排序线程。