内容简介：用Objective-C实现选择排序、冒泡排序、插入排序、快速排序、选择排序几种基本的排序算法，并把排序的过程图形化显示。其实算法还是挺有趣的 ^ ^.
用Objective-C实现几种基本的 排序 算法，并把排序的过程图形化显示。其实算法还是挺有趣的 ^ ^.
- 选择排序
- 冒泡排序
- 插入排序
- 快速排序
选择排序
以升序为例。
选择排序比较好理解，一句话概括就是依次按位置挑选出适合此位置的元素来填充。
- 暂定第一个元素为最小元素，往后遍历，逐个与最小元素比较，若发现更小者，与先前的”最小元素”交换位置。达到更新最小元素的目的。
- 一趟遍历完成后，能确保刚刚完成的这一趟遍历中，最的小元素已经放置在前方了。然后缩小排序范围，新一趟排序从数组的第二个元素开始。
- 在新一轮排序中重复第1、2步骤，直到范围不能缩小为止，排序完成。
选择排序.gif
以下方法在NSMutableArray+JXSort.m中实现
|
1 2 3 4 5 6 7 8 9 10 11 12 |
- (void)jx_selectionSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback { if (self.count == 0) { return; } for (NSInteger i = 0; i < self.count - 1; i ++) { for (NSInteger j = i + 1; j < self.count; j ++) { if (comparator(self[i], self[j]) == NSOrderedDescending) { [self jx_exchangeWithIndexA:i indexB:j didExchange:exchangeCallback]; } } } } |
冒泡排序
- 在一趟遍历中，不断地对相邻的两个元素进行排序，小的在前大的在后，这样会造成大值不断沉底的效果，当一趟遍历完成时，最大的元素会被排在后方正确的位置上。
- 然后缩小排序范围，即去掉最后方位置正确的元素，对前方数组进行新一轮遍历，重复第1步骤。直到范围不能缩小为止，排序完成。
冒泡排序.gif
冒泡排序.gif
|
1 2 3 4 5 6 7 8 9 10 11 12 |
- (void)jx_bubbleSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback { if (self.count == 0) { return; } for (NSInteger i = self.count - 1; i > 0; i --) { for (NSInteger j = 0; j < i; j ++) { if (comparator(self[j], self[j + 1]) == NSOrderedDescending) { [self jx_exchangeWithIndexA:j indexB:j + 1 didExchange:exchangeCallback]; } } } } |
插入排序
插入排序是从一个乱序的数组中依次取值，插入到一个已经排好序的数组中。这看起来好像要两个数组才能完成，但如果只想在同一个数组内排序，也是可以的。此时需要想象出两个区域：前方有序区和后方乱序区。
- 分区。开始时前方有序区只有一个元素，就是数组的第一个元素。然后把从第二个元素开始直到结尾的数组作为乱序区。
- 从乱序区取第一个元素，把它正确插入到前方有序区中。把它与前方无序区的最后一个元素比较，亦即与它的前一个元素比较。
- 如果比前一个元素要大，则不需要交换，这时有序区扩充一格，乱序区往后缩减一格，相当于直接拼在有序区末尾。
- 如果和前一个元素相等，则继续和前二元素比较、再和前三元素比较……如果往前遍历到头了，发现前方所有元素值都长一个样的话(囧)，那也可以，不需要交换，这时有序区扩充一格，乱序区往后缩减一格，相当于直接拼在有序区末尾。如果比前一个元素大呢？对不起作为有序区不可能出现这种情况。如果比前一个元素小呢，请看下一点。
- 如果比前一个元素小，则交换它们的位置。交换完后，继续比较取出元素和它此时的前一个元素，若更小就交换，若相等就比较前一个，直到遍历完成。
至此，把乱序区第一个元素正确插入到前方有序区中。
- 往后缩小乱序区范围，继续取缩小范围后的第一个元素，重复第2步骤。直到范围不能缩小为止，排序完成。
插入排序.gif
|
1 2 3 4 5 6 7 8 9 10 |
- (void)jx_insertionSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback { if (self.count == 0) { return; } for (NSInteger i = 1; i < self.count; i ++) { for (NSInteger j = i; j > 0 && comparator(self[j], self[j - 1]) == NSOrderedAscending; j --) { [self jx_exchangeWithIndexA:j indexB:j - 1 didExchange:exchangeCallback]; } } } |
快速排序
快排的版本有好几种，粗略可分为：
- 原始的快排。
- 为制造适合高效排序环境而事先打乱数组顺序的快排。
- 为数组内大量重复值而优化的三向切分快排。
这里只讨论原始的快排。
关于在快排过程中何时进行交换以及交换谁的问题，我看见两种不同的思路：
- 当左右两个游标都停止时，交换两个游标所指向元素。枢轴所在位置暂时不变，直到两个游标相遇重合，才更新枢轴位置，交换枢轴与游标所指元素。
- 当右游标找到一个比枢轴小的元素时，马上把枢轴交换到游标所在位置，而游标位置的元素则移到枢轴那里。完成一次枢轴更新。然后左游标再去寻找比枢轴大的元素，同理。
第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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
- (void)jx_quickSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback { if (self.count == 0) { return; } [self jx_quickSortWithLowIndex:0 highIndex:self.count - 1 usingComparator:comparator didExchange:exchangeCallback]; } - (void)jx_quickSortWithLowIndex:(NSInteger)low highIndex:(NSInteger)high usingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback { if (low >= high) { return; } NSInteger pivotIndex = [self jx_quickPartitionWithLowIndex:low highIndex:high usingComparator:comparator didExchange:exchangeCallback]; [self jx_quickSortWithLowIndex:low highIndex:pivotIndex - 1 usingComparator:comparator didExchange:exchangeCallback]; [self jx_quickSortWithLowIndex:pivotIndex + 1 highIndex:high usingComparator:comparator didExchange:exchangeCallback]; } - (NSInteger)jx_quickPartitionWithLowIndex:(NSInteger)low highIndex:(NSInteger)high usingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback { id pivot = self[low]; NSInteger i = low; NSInteger j = high; while (i < j) { // 略过大于等于pivot的元素 while (i < j && comparator(self[j], pivot) != NSOrderedAscending) { j --; } if (i < j) { // i、j未相遇，说明找到了小于pivot的元素。交换。 [self jx_exchangeWithIndexA:i indexB:j didExchange:exchangeCallback]; i ++; } /// 略过小于等于pivot的元素 while (i < j && comparator(self[i], pivot) != NSOrderedDescending) { i ++; } if (i < j) { // i、j未相遇，说明找到了大于pivot的元素。交换。 [self jx_exchangeWithIndexA:i indexB:j didExchange:exchangeCallback]; j --; } } return i; } |
UI实现
现在讲下UI的实现思路。
NSMutableArray+JXSort.h
从前面的排序代码可以看到，我是给NSMutableArray写了个分类，排序逻辑写在分类里面，完全与视图无关。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
typedef NSComparisonResult(^JXSortComparator)(id obj1, id obj2); typedef void(^JXSortExchangeCallback)(id obj1, id obj2); @interface NSMutableArray (JXSort) // 选择排序 - (void)jx_selectionSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback; // 冒泡排序 - (void)jx_bubbleSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback; // 插入排序 - (void)jx_insertionSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback; // 快速排序 - (void)jx_quickSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback; @end |
外部调用者只需要传入两个参数：
comparator代码块。这是遵循苹果原有API的风格设计，在需要比较数组内的两个元素时，排序方法将会调用这个代码块，回传需要比较的两个元素给外部调用者，由外部调用者实现比较逻辑，并返回比较结果给排序方法。exchangeCallback代码块。这个参数是实现视图变化的关键。排序方法在每次完成两个元素的交换时，都会调用这个代码块。外部调用者，比如ViewController就可以知道排序元素每一次变换位置的时机，从而同步视图的变化。
|
1 2 3 4 5 6 7 8 9 |
- (void)jx_exchangeWithIndexA:(NSInteger)indexA indexB:(NSInteger)indexB didExchange:(JXSortExchangeCallback)exchangeCallback { id temp = self[indexA]; self[indexA] = self[indexB]; self[indexB] = temp; if (exchangeCallback) { exchangeCallback(temp, self[indexA]); } } |
ViewController.m
视图控制器持有待排序的数组，这个数组是100条细长的矩形，长度随机。
|
1 |
@property (nonatomic, strong) NSMutableArray<UIView *> *barArray; |
由于我们加强了NSMutableArray，它现在可以支持多种指定类型的排序了，同时也可以把排序过程反馈给我们，当需要给barArray排序时，只需要这样调用：
|
1 2 3 4 5 6 7 |
- (void)quickSort { [self.barArray jx_quickSortUsingComparator:^NSComparisonResult(id obj1, id obj2) { return [self compareWithBarOne:obj1 andBarTwo:obj2]; } didExchange:^(id obj1, id obj2) { [self exchangePositionWithBarOne:obj1 andBarTwo:obj2]; }]; } |
每一次didExchange的回调，ViewController都会对两个视图的位置进行交换。如此形成不断进行排序的视觉效果。
控制排序速度
为了能够让肉眼感知排序的过程，我们需要放慢排序的过程。这里我的办法是延长两个元素比较操作的耗时，大约延长到0.002秒。结果很明显，当某个算法所需要进行的比较操作越少时，它排序就会越快(根据上面四张图的比较，毫无疑问快排所进行的比较操作是最少啦~)。
那么如何模拟出比较操作的耗时时间呢？
这里我的办法是借助信号量，在两条线程间通讯。
1.让排序在子线程中进行，当需要进行比较操作时，阻塞线程，等待信号的到来。这里的思想是得到一个信号才能进行一次比较。
|
1 2 3 4 5 6 7 8 9 10 11 |
- (NSComparisonResult)compareWithBarOne:(UIView *)barOne andBarTwo:(UIView *)barTwo { // 模拟进行比较所需的耗时 dispatch_semaphore_wait(self.sema, DISPATCH_TIME_FOREVER); CGFloat height1 = CGRectGetHeight(barOne.frame); CGFloat height2 = CGRectGetHeight(barTwo.frame); if (height1 == height2) { return NSOrderedSame; } return height1 < height2 ? NSOrderedAscending : NSOrderedDescending; } |
2.主线程启用定时器，每隔0.002秒发出一个信号，唤醒排序线程。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
self.sema = dispatch_semaphore_create(0); NSTimeInterval nowTime = [[NSDate date] timeIntervalSince1970]; // 定时器信号 __weak typeof(self) weakSelf = self; self.timer = [NSTimer scheduledTimerWithTimeInterval:0.002 repeats:YES block:^(NSTimer * _Nonnull timer) { // 发出信号量，唤醒排序线程 dispatch_semaphore_signal(weakSelf.sema); // 更新计时 NSTimeInterval interval = [[NSDate date] timeIntervalSince1970] - nowTime; weakSelf.timeLabel.text = [NSString stringWithFormat:@"耗时(秒):%2.3f", interval]; }]; |
源码
https://github.com/JiongXing/JXSort
参考
Swift算法俱乐部中文版 — 插入排序
算法笔记－排序01:选择排序,插入排序,希尔排序
算法笔记－排序02:归并排序,快速排序
1.2-交换排序-快速排序
原文出处： 梁炯幸
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- 排序算法--冒泡排序
- 冒泡排序——重温排序（三）
- 【一起学习排序算法】1.冒泡排序
- 排序算法之冒泡排序改进算法
- 算法之常见排序算法-冒泡排序、归并排序、快速排序
- 【JS面试向】选择排序、桶排序、冒泡排序和快速排序简介
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
编程之美：微软技术面试心得
《编程之美》小组 / 电子工业出版社 / 2018-9 / 79
《编程之美：微软技术面试心得》收集了约60道算法和程序设计的题目，这些题目大部分在微软的笔试、面试中出现过，有的曾被微软员工热烈地讨论过。作者试图从书中各种有趣的问题出发，引导读者发现问题、分析问题、解决问题，寻找更优的解法。《编程之美：微软技术面试心得》内容分为以下几个部分。 游戏之乐：从游戏和其他有趣问题出发，化繁为简，分析总结。 数字之魅：编程的过程实际上就是和数字及字符打交道的......一起来看看 《编程之美：微软技术面试心得》 这本书的介绍吧!
