算法 | 排序算法图形化比较:快速排序、插入排序、选择排序、冒泡排序

用Objective-C实现几种基本的排序算法,并把排序的过程图形化显示。其实算法还是挺有趣的 。

  • 选择排序
  • 冒泡排序
  • 插入排序
  • 快速排序

01

选择排序

以升序为例。

选择排序比较好理解,一句话概括就是依次按位置挑选出适合此位置的元素来填充。

1.暂定第一个元素为最小元素,往后遍历,逐个与最小元素比较,若发现更小者,与先前的"最小元素"交换位置。达到更新最小元素的目的。

2.一趟遍历完成后,能确保刚刚完成的这一趟遍历中,最的小元素已经放置在前方了。然后缩小排序范围,新一趟排序从数组的第二个元素开始。

3.在新一轮排序中重复第1、2步骤,直到范围不能缩小为止,排序完成。

选择排序.gif

以下方法在NSMutableArray+JXSort.m中实现

- (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];            
                 }         
           }     
     }
 }

02

冒泡排序

1.在一趟遍历中,不断地对相邻的两个元素进行排序,小的在前大的在后,这样会造成大值不断沉底的效果,当一趟遍历完成时,最大的元素会被排在后方正确的位置上。

2. 然后缩小排序范围,即去掉最后方位置正确的元素,对前方数组进行新一轮遍历,重复第1步骤。直到范围不能缩小为止,排序完成。

冒泡排序.gif

- (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];

}

}

}

}

03

插入排序

插入排序是从一个乱序的数组中依次取值,插入到一个已经排好序的数组中。

这看起来好像要两个数组才能完成,但如果只想在同一个数组内排序,也是可以的。此时需要想象出两个区域:前方有序区和后方乱序区。

1.分区。开始时前方有序区只有一个元素,就是数组的第一个元素。然后把从第二个元素开始直到结尾的数组作为乱序区。

2.从乱序区取第一个元素,把它正确插入到前方有序区中。把它与前方无序区的最后一个元素比较,亦即与它的前一个元素比较。

  • 如果比前一个元素要大,则不需要交换,这时有序区扩充一格,乱序区往后缩减一格,相当于直接拼在有序区末尾。
  • 如果和前一个元素相等,则继续和前二元素比较、再和前三元素比较......如果往前遍历到头了,发现前方所有元素值都长一个样的话(囧),那也可以,不需要交换,这时有序区扩充一格,乱序区往后缩减一格,相当于直接拼在有序区末尾。如果比前一个元素大呢?对不起作为有序区不可能出现这种情况。如果比前一个元素小呢,请看下一点。
  • 如果比前一个元素小,则交换它们的位置。交换完后,继续比较取出元素和它此时的前一个元素,若更小就交换,若相等就比较前一个,直到遍历完成。 至此,把乱序区第一个元素正确插入到前方有序区中。

3.往后缩小乱序区范围,继续取缩小范围后的第一个元素,重复第2步骤。直到范围不能缩小为止,排序完成。

插入排序.gif

- (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];

}

}

}

04

快速排序

快排的版本有好几种,粗略可分为:

  • 原始的快排。
  • 为制造适合高效排序环境而事先打乱数组顺序的快排。
  • 为数组内大量重复值而优化的三向切分快排。

这里只讨论原始的快排。

关于在快排过程中何时进行交换以及交换谁的问题,我看见两种不同的思路:

1.当左右两个游标都停止时,交换两个游标所指向元素。枢轴所在位置暂时不变,直到两个游标相遇重合,才更新枢轴位置,交换枢轴与游标所指元素。

2.当右游标找到一个比枢轴小的元素时,马上把枢轴交换到游标所在位置,而游标位置的元素则移到枢轴那里。完成一次枢轴更新。然后左游标再去寻找比枢轴大的元素,同理。

第1种思路可以有效降低交换频率,在游标相遇后再对枢轴进行定位,这步会导致略微增加了比较的次数;

第2种思路交换操作会比较频繁,但是在交换的过程中同时也把枢轴的位置不断进行更新,当游标相遇时,枢轴的定位也完成了。

在两种思路都尝试实现过后,我还是喜欢第2种,即便交换操作会多一些,但实质上的交换只是对数组特定位置的赋值,这种操作还是挺快的。

1.从待排序数组中选一个值作为分区的参考界线,一般选第一个元素即可。这个选出来的值可叫做枢轴pivot,它将会在一趟排序中不断被移动位置,只终移动到位于整个数组的正确位置上。

2.一趟排序的目标是把小于枢轴的元素放在前方,把大于枢轴的元素放在后方,枢轴放在中间。这看起来一趟排序实质上所干的事情就是把数组分区。接下来考虑怎么完成一次分区。

3.记一个游标i,指向待排序数组的首位,它将会不断向后移动; 再记一个游标j,指向待排序数组的末位,它将会不断向前移动。 这样可以预见的是,ij终有相遇时,当它们相遇的时候,就是这趟排序完成时。

4.现在让游标j从后往前扫描,寻找比枢轴小的元素x,找到后停下来,准备把这个元素扔到前方去。

5.在同一个数组内排序并不能扩大数组的容量,那怎么扔呢? 因为刚才把首位元素选作为pivot,所以当前它们的位置关系是pivot ... x

又排序目标是升序,x是个小值却放在了pivot的后方,不妥,需要交换它们的位置。

6.交换完后,它们的位置关系变成了x ... pivot。此时j指向了pivoti指向了x

7.现在让游标i向后扫描,寻找比枢轴大的元素y,找到后停下来,与pivot进行交换。

完成后的位置关系是pivot ... y,此时i指向pivot,即pivot移到了i的位置。

8.这里有个小优化,在i向后扫描开始时,i是指向x的,而在上一轮j游标的扫描中我们已经知道x是比pivot小的,所以完全可以让i跳过x,不需要拿着xpivot再比较一次。

结论是在j游标的交换完成后,顺便把i往后移一位,i ++。 同理,在i游标的交换完成后,顺便把j往前移一位,j --

9.在扫描的过程中如果发现与枢轴相等的元素怎么办呢? 因我们不讨论三向切分的快排优化算法,所以这里答案是:不理它。

10.随着一趟一趟的排序,它们会慢慢被更小的元素往后挤,被更大的元素往前挤,最后的结果就是它们都会和枢轴一起移到了中间位置。

11.当ij相遇时,ij都会指向pivot。在我们的分区方法里,把i返回,即在分区完成后把枢轴位置返回。

12.接下来,让分出的两个数组分别按上述步骤各自分区,这是个递归的过程,直到数组不能再分时,排序完成。

快速排序是很天才的设计,实现不复杂,关键是它真的很快~

快速排序.gif

- (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;
 }

05

UI实现

现在讲下UI的实现思路。

NSMutableArray+JXSort.h

从前面的排序代码可以看到,我是给NSMutableArray写了个分类,排序逻辑写在分类里面,完全与视图无关。

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就可以知道排序元素每一次变换位置的时机,从而同步视图的变化。
- (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条细长的矩形,长度随机。

@property (nonatomic, strong) NSMutableArray<UIView *> *barArray;

由于我们加强了NSMutableArray,它现在可以支持多种指定类型的排序了,同时也可以把排序过程反馈给我们,当需要给barArray排序时,只需要这样调用:

- (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都会对两个视图的位置进行交换。如此形成不断进行排序的视觉效果。

控制排序速度

为了能够让肉眼感知排序的过程,我们需要放慢排序的过程。

这里我的办法是延长两个元素比较操作的耗时,当某个算法所需要进行的比较操作越少时,它排序就会越快(根据上面四张图的比较,毫无疑问快排所进行的比较操作是最少啦~)。

那么如何模拟出比较操作的耗时时间呢?

这里我的办法是借助信号量,在两条线程间通讯。

1.让排序在子线程中进行,当需要进行比较操作时,阻塞线程,等待信号的到来。这里的思想是得到一个信号才能进行一次比较。

- (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.主线程启用定时器,每隔一定时间发出一个信号,唤醒排序线程。

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算法俱乐部中文版 -- 插入排序(http://www.jianshu.com/p/0ab1369e703d)

算法笔记-排序01:选择排序,插入排序,希尔排序(http://www.jianshu.com/p/a7efe0f8e4ab)

算法笔记-排序02:归并排序,快速排序(http://www.jianshu.com/p/655db46e161d)

1.2-交换排序-快速排序(http://www.jianshu.com/p/8773cc691ced)

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2017-09-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

程序员进阶之算法练习(八)附两道搜狐笔试题

前言 前面讲了那么多算法的重要性。口说无凭,这次带上两道搜狐今年的笔试题。 这里先附上两道搜狐题目的大意: 题目一: 《宝石》 有一串宝石首尾相连,用...

3675
来自专栏Script Boy (CN-SIMO)

软件工程个人作业01

题目:      像二柱子那样,花二十分钟写一个能自动生成三十道小学四则运算题目的 “软件”,要求:除了整数以外,还要支持真分数的四则运算(需要验证结果的正确...

1880
来自专栏程序员宝库

移除注释的完善思路:真的可以用正则实现?

网上有很多自称能实现移除JS注释的正则表达式,实际上存在种种缺陷。这使人多少有些愕然,也不禁疑惑到:真的可以用正则实现吗?而本篇文章以使用正则移除JS注释为目标...

1003
来自专栏糊一笑

几个关于js数组方法reduce的经典片段

以下是个人在工作中收藏总结的一些关于javascript数组方法reduce的相关代码片段,后续遇到其他使用这个函数的场景,将会陆续添加,这里作为备忘。 jav...

3359
来自专栏Golang语言社区

厚土Go学习笔记 | 29. 接口

在go语言中,接口类型是由一组方法定义的集合。 一个类型是否实现了一个接口,就看这个类型是否实现了接口中定义的所有方法。在go语言中,无需特别的指明定义一个接口...

3405
来自专栏Golang语言社区

Golang语言--资源自动回收技术

Go语言作为一个现代化的编程语言以及支持垃圾内存的自动回收特性(GC). 我们现在关注的是非内存资源的自动回收技术. 局部资源的管理 在讨论Go语言解决方案之前...

3568
来自专栏C语言及其他语言

【每日一题】问题 1107: 纪念品分组

元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括...

881
来自专栏C/C++基础

八皇后问题

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相...

824
来自专栏Android 研究

Android跨进程通信IPC之4——AndroidIPC基础2

通过 Parcel的writeStrongBinder方法将Binder对象序列化:

734
来自专栏郭耀华‘s Blog

剑指offer 第十天

37.数字在排序数组中出现的次数 统计一个数字在排序数组中出现的次数。 采用二分查找法 /* 方法一:时间复杂度O(n),不可选 */ public cla...

3288

扫描关注云+社区