各大排序算法的Objective-C实现以及图形化演示比较

java一日一条 · 公众号 · Java · 2016-12-03 07:58

正文

请到「今天看啥」查看全文

如果和前一个元素相等，则继续和前二元素比较、再和前三元素比较……如果往前遍历到头了，发现前方所有元素值都长一个样的话(囧)，那也可以，不需要交换，这时有序区扩充一格，乱序区往后缩减一格，相当于直接拼在有序区末尾。如果比前一个元素大呢？对不起作为有序区不可能出现这种情况。如果比前一个元素小呢，请看下一点。

如果比前一个元素小，则交换它们的位置。交换完后，继续比较取出元素和它此时的前一个元素，若更小就交换，若相等就比较前一个，直到遍历完成。
至此，把乱序区第一个元素正确插入到前方有序区中。

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

插入排序.gif

快速排序

快排的版本有好几种，粗略可分为：

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

这里只讨论原始的快排。

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

当左右两个游标都停止时，交换两个游标所指向元素。枢轴所在位置暂时不变，直到两个游标相遇重合，才更新枢轴位置，交换枢轴与游标所指元素。
当右游标找到一个比枢轴小的元素时，马上把枢轴交换到游标所在位置，而游标位置的元素则移到枢轴那里。完成一次枢轴更新。然后左游标再去寻找比枢轴大的元素，同理。

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

第2种思路交换操作会比较频繁，但是在交换的过程中同时也把枢轴的位置不断进行更新，当游标相遇时，枢轴的定位也完成了。
在两种思路都尝试实现过后，我还是喜欢第2种，即便交换操作会多一些，但实质上的交换只是对数组特定位置的赋值，这种操作还是挺快的。

从待排序数组中选一个值作为分区的参考界线，一般选第一个元素即可。这个选出来的值可叫做枢轴 pivot ，它将会在一趟排序中不断被移动位置，只终移动到位于整个数组的正确位置上。
一趟排序的目标是把小于枢轴的元素放在前方，把大于枢轴的元素放在后方，枢轴放在中间。这看起来一趟排序实质上所干的事情就是把数组分区。接下来考虑怎么完成一次分区。
记一个游标 i ，指向待排序数组的首位，它将会不断向后移动；
再记一个游标 j ，指向待排序数组的末位，它将会不断向前移动。
这样可以预见的是， i 、 j 终有相遇时，当它们相遇的时候，就是这趟排序完成时。
现在让游标 j 从后往前扫描，寻找比枢轴小的元素 x ，找到后停下来，准备把这个元素扔到前方去。