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

LinwoodBlac 2年前
   <p>用Objective-C实现几种基本的排序算法,并把排序的过程图形化显示。其实算法还是挺有趣的 ^ ^.</p>    <ul>     <li>选择排序</li>     <li>冒泡排序</li>     <li>插入排序</li>     <li>快速排序</li>    </ul>    <h2>选择排序</h2>    <p>以升序为例。</p>    <p>选择排序比较好理解,一句话概括就是依次按位置挑选出适合此位置的元素来填充。</p>    <ol>     <li>暂定第一个元素为最小元素,往后遍历,逐个与最小元素比较,若发现更小者,与先前的”最小元素”交换位置。达到更新最小元素的目的。</li>     <li>一趟遍历完成后,能确保刚刚完成的这一趟遍历中,最的小元素已经放置在前方了。然后缩小排序范围,新一趟排序从数组的第二个元素开始。</li>     <li>在新一轮排序中重复第1、2步骤,直到范围不能缩小为止,排序完成。</li>    </ol>    <p><img src="https://simg.open-open.com/show/6a1a767949a88c92648d97c75f10dc78.gif"></p>    <p>选择排序.gif</p>    <p>以下方法在 NSMutableArray+JXSort.m 中实现</p>    <pre>  <code class="language-objectivec">- (void)jx_selectionSortUsingComparator:(JXSortComparator)comparatordidExchange:(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) {                  [selfjx_exchangeWithIndexA:iindexB:jdidExchange:exchangeCallback];              }          }      }  }  </code></pre>    <h2>冒泡排序</h2>    <ol>     <li>在一趟遍历中,不断地对相邻的两个元素进行排序,小的在前大的在后,这样会造成大值不断沉底的效果,当一趟遍历完成时,最大的元素会被排在后方正确的位置上。</li>     <li>然后缩小排序范围,即去掉最后方位置正确的元素,对前方数组进行新一轮遍历,重复第1步骤。直到范围不能缩小为止,排序完成。</li>    </ol>    <p><img src="https://simg.open-open.com/show/71a8ef63f2ca68ea99aefaca97a62ea8.gif"></p>    <p>冒泡排序.gif</p>    <pre>  <code class="language-objectivec">- (void)jx_bubbleSortUsingComparator:(JXSortComparator)comparatordidExchange:(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) {                  [selfjx_exchangeWithIndexA:jindexB:j + 1didExchange:exchangeCallback];              }          }      }  }  </code></pre>    <h2>插入排序</h2>    <p>插入排序是从一个乱序的数组中依次取值,插入到一个已经排好序的数组中。这看起来好像要两个数组才能完成,但如果只想在同一个数组内排序,也是可以的。此时需要想象出两个区域:前方有序区和后方乱序区。</p>    <ol>     <li>分区。开始时前方有序区只有一个元素,就是数组的第一个元素。然后把从第二个元素开始直到结尾的数组作为乱序区。</li>     <li>从乱序区取第一个元素,把它正确插入到前方有序区中。把它与前方无序区的最后一个元素比较,亦即与它的前一个元素比较。      <ul>       <li>如果比前一个元素要大,则不需要交换,这时有序区扩充一格,乱序区往后缩减一格,相当于直接拼在有序区末尾。</li>       <li>如果和前一个元素相等,则继续和前二元素比较、再和前三元素比较……如果往前遍历到头了,发现前方所有元素值都长一个样的话(囧),那也可以,不需要交换,这时有序区扩充一格,乱序区往后缩减一格,相当于直接拼在有序区末尾。如果比前一个元素大呢?对不起作为有序区不可能出现这种情况。如果比前一个元素小呢,请看下一点。</li>       <li>如果比前一个元素小,则交换它们的位置。交换完后,继续比较取出元素和它此时的前一个元素,若更小就交换,若相等就比较前一个,直到遍历完成。<br> 至此,把乱序区第一个元素正确插入到前方有序区中。</li>      </ul> </li>     <li>往后缩小乱序区范围,继续取缩小范围后的第一个元素,重复第2步骤。直到范围不能缩小为止,排序完成。</li>    </ol>    <p><img src="https://simg.open-open.com/show/570a3ae86fa60e4186cf1f80462ca1d9.gif"></p>    <p>插入排序.gif</p>    <pre>  <code class="language-objectivec">- (void)jx_insertionSortUsingComparator:(JXSortComparator)comparatordidExchange:(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 --) {              [selfjx_exchangeWithIndexA:jindexB:j - 1didExchange:exchangeCallback];          }      }  }  </code></pre>    <h2>快速排序</h2>    <p>快排的版本有好几种,粗略可分为:</p>    <ul>     <li>原始的快排。</li>     <li>为制造适合高效排序环境而事先打乱数组顺序的快排。</li>     <li>为数组内大量重复值而优化的三向切分快排。</li>    </ul>    <p>这里只讨论原始的快排。</p>    <p>关于在快排过程中何时进行交换以及交换谁的问题,我看见两种不同的思路:</p>    <ol>     <li>当左右两个游标都停止时,交换两个游标所指向元素。枢轴所在位置暂时不变,直到两个游标相遇重合,才更新枢轴位置,交换枢轴与游标所指元素。</li>     <li>当右游标找到一个比枢轴小的元素时,马上把枢轴交换到游标所在位置,而游标位置的元素则移到枢轴那里。完成一次枢轴更新。然后左游标再去寻找比枢轴大的元素,同理。</li>    </ol>    <p>第1种思路可以有效降低交换频率,在游标相遇后再对枢轴进行定位,这步会导致略微增加了比较的次数;第2种思路交换操作会比较频繁,但是在交换的过程中同时也把枢轴的位置不断进行更新,当游标相遇时,枢轴的定位也完成了。</p>    <p>在两种思路都尝试实现过后,我还是喜欢第2种,即便交换操作会多一些,但实质上的交换只是对数组特定位置的赋值,这种操作还是挺快的。</p>    <ol>     <li>从待排序数组中选一个值作为分区的参考界线,一般选第一个元素即可。这个选出来的值可叫做枢轴 pivot ,它将会在一趟排序中不断被移动位置,只终移动到位于整个数组的正确位置上。</li>     <li>一趟排序的目标是把小于枢轴的元素放在前方,把大于枢轴的元素放在后方,枢轴放在中间。这看起来一趟排序实质上所干的事情就是把数组分区。接下来考虑怎么完成一次分区。</li>     <li>记一个游标 i ,指向待排序数组的首位,它将会不断向后移动;<br> 再记一个游标 j ,指向待排序数组的末位,它将会不断向前移动。<br> 这样可以预见的是, i 、 j 终有相遇时,当它们相遇的时候,就是这趟排序完成时。</li>     <li>现在让游标 j 从后往前扫描,寻找比枢轴小的元素 x ,找到后停下来,准备把这个元素扔到前方去。</li>     <li>在同一个数组内排序并不能扩大数组的容量,那怎么扔呢?<br> 因为刚才把首位元素选作为 pivot ,所以当前它们的位置关系是 pivot ... x 。<br> 又排序目标是升序, x 是个小值却放在了 pivot 的后方,不妥,需要交换它们的位置。</li>     <li>交换完后,它们的位置关系变成了 x ... pivot 。此时 j 指向了 pivot , i 指向了 x 。</li>     <li>现在让游标 i 向后扫描,寻找比枢轴大的元素 y ,找到后停下来,与 pivot 进行交换。<br> 完成后的位置关系是 pivot ... y ,此时 i 指向pivot,即pivot移到了 i 的位置。</li>     <li>这里有个小优化,在 i 向后扫描开始时, i 是指向 x 的,而在上一轮 j 游标的扫描中我们已经知道 x 是比 pivot 小的,所以完全可以让 i 跳过 x ,不需要拿着 x 和 pivot 再比较一次。<br> 结论是在 j 游标的交换完成后,顺便把 i 往后移一位, i ++ 。<br> 同理,在 i 游标的交换完成后,顺便把 j 往前移一位, j -- 。</li>     <li>在扫描的过程中如果发现与枢轴相等的元素怎么办呢?<br> 因我们不讨论三向切分的快排优化算法,所以这里答案是:不理它。<br> 随着一趟一趟的排序,它们会慢慢被更小的元素往后挤,被更大的元素往前挤,最后的结果就是它们都会和枢轴一起移到了中间位置。</li>     <li>当 i 和 j 相遇时, i 和 j 都会指向 pivot 。在我们的分区方法里,把 i 返回,即在分区完成后把枢轴位置返回。</li>     <li>接下来,让分出的两个数组分别按上述步骤各自分区,这是个递归的过程,直到数组不能再分时,排序完成。</li>    </ol>    <p><a href="/misc/goto?guid=4959723813724284969" rel="nofollow,noindex">快速排序</a> 是很天才的设计,实现不复杂,关键是它真的很快~</p>    <p><img src="https://simg.open-open.com/show/19f91787f387dd8a71813110ba1c192b.gif"></p>    <p>快速排序.gif</p>    <pre>  <code class="language-objectivec">- (void)jx_quickSortUsingComparator:(JXSortComparator)comparatordidExchange:(JXSortExchangeCallback)exchangeCallback {      if (self.count == 0) {          return;      }      [selfjx_quickSortWithLowIndex:0highIndex:self.count - 1usingComparator:comparatordidExchange:exchangeCallback];  }     - (void)jx_quickSortWithLowIndex:(NSInteger)lowhighIndex:(NSInteger)highusingComparator:(JXSortComparator)comparatordidExchange:(JXSortExchangeCallback)exchangeCallback {      if (low >= high) {          return;      }      NSInteger pivotIndex = [selfjx_quickPartitionWithLowIndex:lowhighIndex:highusingComparator:comparatordidExchange:exchangeCallback];      [selfjx_quickSortWithLowIndex:lowhighIndex:pivotIndex - 1usingComparator:comparatordidExchange:exchangeCallback];      [selfjx_quickSortWithLowIndex:pivotIndex + 1highIndex:highusingComparator:comparatordidExchange:exchangeCallback];  }     - (NSInteger)jx_quickPartitionWithLowIndex:(NSInteger)lowhighIndex:(NSInteger)highusingComparator:(JXSortComparator)comparatordidExchange:(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的元素。交换。              [selfjx_exchangeWithIndexA:iindexB:jdidExchange:exchangeCallback];              i ++;          }             /// 略过小于等于pivot的元素          while (i < j && comparator(self[i], pivot) != NSOrderedDescending) {              i ++;          }          if (i < j) {              // i、j未相遇,说明找到了大于pivot的元素。交换。              [selfjx_exchangeWithIndexA:iindexB:jdidExchange:exchangeCallback];              j --;          }      }      return i;  }  </code></pre>    <h2>UI实现</h2>    <p>现在讲下UI的实现思路。</p>    <p>NSMutableArray+JXSort.h</p>    <p>从前面的排序代码可以看到,我是给 NSMutableArray 写了个分类,排序逻辑写在分类里面,完全与视图无关。</p>    <pre>  <code class="language-objectivec">typedef NSComparisonResult(^JXSortComparator)(id obj1, id obj2);  typedef void(^JXSortExchangeCallback)(id obj1, id obj2);     @interface NSMutableArray (JXSort)     // 选择排序  - (void)jx_selectionSortUsingComparator:(JXSortComparator)comparatordidExchange:(JXSortExchangeCallback)exchangeCallback;     // 冒泡排序  - (void)jx_bubbleSortUsingComparator:(JXSortComparator)comparatordidExchange:(JXSortExchangeCallback)exchangeCallback;     // 插入排序  - (void)jx_insertionSortUsingComparator:(JXSortComparator)comparatordidExchange:(JXSortExchangeCallback)exchangeCallback;     // 快速排序  - (void)jx_quickSortUsingComparator:(JXSortComparator)comparatordidExchange:(JXSortExchangeCallback)exchangeCallback;     @end  </code></pre>    <p>外部调用者只需要传入两个参数:</p>    <ul>     <li>comparator 代码块。这是遵循苹果原有API的风格设计,在需要比较数组内的两个元素时,排序方法将会调用这个代码块,回传需要比较的两个元素给外部调用者,由外部调用者实现比较逻辑,并返回比较结果给排序方法。</li>     <li>exchangeCallback 代码块。这个参数是实现视图变化的关键。排序方法在每次完成两个元素的交换时,都会调用这个代码块。外部调用者,比如ViewController就可以知道排序元素每一次变换位置的时机,从而同步视图的变化。</li>    </ul>    <pre>  <code class="language-objectivec">- (void)jx_exchangeWithIndexA:(NSInteger)indexAindexB:(NSInteger)indexBdidExchange:(JXSortExchangeCallback)exchangeCallback {      id temp = self[indexA];      self[indexA] = self[indexB];      self[indexB] = temp;         if (exchangeCallback) {          exchangeCallback(temp, self[indexA]);      }  }  </code></pre>    <p>ViewController.m</p>    <p>视图控制器持有待排序的数组,这个数组是100条细长的矩形,长度随机。</p>    <pre>  <code class="language-objectivec">@property (nonatomic, strong) NSMutableArray<UIView *> *barArray;  </code></pre>    <p>由于我们加强了 NSMutableArray ,它现在可以支持多种指定类型的排序了,同时也可以把排序过程反馈给我们,当需要给 barArray 排序时,只需要这样调用:</p>    <pre>  <code class="language-objectivec">- (void)quickSort {      [self.barArrayjx_quickSortUsingComparator:^NSComparisonResult(id obj1, id obj2) {          return [selfcompareWithBarOne:obj1andBarTwo:obj2];      }didExchange:^(id obj1, id obj2) {          [selfexchangePositionWithBarOne:obj1andBarTwo:obj2];      }];  }  </code></pre>    <p>每一次didExchange的回调,ViewController都会对两个视图的位置进行交换。如此形成不断进行排序的视觉效果。</p>    <p>控制排序速度</p>    <p>为了能够让肉眼感知排序的过程,我们需要放慢排序的过程。这里我的办法是延长两个元素比较操作的耗时,大约延长到0.002秒。结果很明显,当某个算法所需要进行的比较操作越少时,它排序就会越快(根据上面四张图的比较,毫无疑问快排所进行的比较操作是最少啦~)。</p>    <p>那么如何模拟出比较操作的耗时时间呢?</p>    <p>这里我的办法是借助信号量,在两条线程间通讯。</p>    <p>1.让排序在子线程中进行,当需要进行比较操作时,阻塞线程,等待信号的到来。这里的思想是得到一个信号才能进行一次比较。</p>    <pre>  <code class="language-objectivec">- (NSComparisonResult)compareWithBarOne:(UIView *)barOneandBarTwo:(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;  }  </code></pre>    <p>2.主线程启用定时器,每隔0.002秒发出一个信号,唤醒排序线程。</p>    <pre>  <code class="language-objectivec"> self.sema = dispatch_semaphore_create(0);      NSTimeInterval nowTime = [[NSDate date]timeIntervalSince1970];         // 定时器信号      __weak typeof(self) weakSelf = self;      self.timer = [NSTimerscheduledTimerWithTimeInterval:0.002repeats:YESblock:^(NSTimer * _Nonnulltimer) {          // 发出信号量,唤醒排序线程          dispatch_semaphore_signal(weakSelf.sema);          // 更新计时          NSTimeInterval interval = [[NSDate date]timeIntervalSince1970] - nowTime;          weakSelf.timeLabel.text = [NSStringstringWithFormat:@"耗时(秒):%2.3f", interval];      }];  </code></pre>    <h2>源码</h2>    <p><a href="/misc/goto?guid=4959723813829448917" rel="nofollow,noindex">https://github.com/JiongXing/JXSort</a></p>    <h2>参考</h2>    <p><a href="/misc/goto?guid=4959723813913821815" rel="nofollow,noindex">Swift算法俱乐部中文版 — 插入排序</a></p>    <p><a href="/misc/goto?guid=4959723813997575826" rel="nofollow,noindex">算法笔记-排序01:选择排序,插入排序,希尔排序</a></p>    <p><a href="/misc/goto?guid=4959723814082142598" rel="nofollow,noindex">算法笔记-排序02:归并排序,快速排序</a></p>    <p><a href="/misc/goto?guid=4959723814172242527" rel="nofollow,noindex">1.2-交换排序-快速排序</a></p>    <p> </p>