用Objective-C实现几种基本排序算法，图形化展示排序过程。其实这个算法挺有意思的^^。选择排序冒泡排序插入排序快速排序选择排序以升序为例。选择排序更容易理解。一句话，就是选择适合这个位置的元素来填补。暂定第一个元素为最小元素，向后遍历，与最小元素一个一个比较，如果找到较小的，则与前一个“最小元素”交换位置。达到更新最小元素的目的。一次遍历完成后，可以保证在刚刚完成的遍历中，最小的元素已经排在前面。然后缩小排序范围，从数组的第二个元素开始新的排序。在新一轮排序中重复步骤1和2，直到范围不能缩小，排序完成。NSMutableArray+JXSort.m中实现了以下选择排序的方法-(void)jx_selectionSortUsingComparator:(JXSortComparator)comparatordidExchange:(JXSortExchangeCallback)exchangeCallback{if(self.count==0){return;}for(NSIntegeri=0;i0;i--){for(NSIntegerj=0;j0&&comparator(self[j],self[j-1])==NSOrderedAscending;j--){[selfjx_exchangeWithIndexA:jindexB:j-1didExchange:exchangeCallback];}}}快排的版本不错有有几种，大致可以分为：原始快排。一种预先打乱数组顺序以使其适合高效排序环境的快速排序。针对数组中大量重复值优化的三向拆分快速排序。这里只讨论原始的快速排序。关于quicksort过程中什么时候和谁交换的问题，我看到两种不同的思路：当左右游标都停止时，交换两个游标指向的元素。枢轴位置暂时保持不变，直到两个光标相遇重合，更新枢轴位置，交换枢轴和光标指向的元素。当右游标找到比枢轴小的元素时，立即将枢轴交换到光标位置，将光标位置的元素移动到枢轴。完成枢轴更新。然后移动左光标找到比枢轴大的元素，方法相同。第一种思路可以有效降低交换频率，然后在游标相遇后定位pivot，这样会导致比较次数略有增加；第二种思路会更频繁地交换操作，但是同时在交换过程中不断更新pivot的位置，当游标相遇时，pivot的定位也完成了。在尝试实现这两种想法之后，我仍然喜欢第二种。虽然swap操作会比较多，但swap其实只是数组中特定位置的赋值，而且这个操作还是比较快的。从待排序数组中选择一个值作为分区的参考边界，一般选择第一个元素。这个被选中的值可以称为pivot枢轴，它会在一个排序过程中不断移位，直到最终移动到整个数组中的正确位置。一次排序的目标是将小于枢轴的元素放在前面，将大于枢轴的元素放在后面，将枢轴放在中间。貌似sort实际做的就是对数组进行分区。接下来考虑如何完成分区。记录一个游标i，指向待排序数组的第一个位置，会一直向后移动；记录另一个游标j，指向待排序数组的末尾，它会继续向前移动。这样就可以预测到i和j最终相遇的时候，当他们相遇的时候，就是排序完成的时候。现在让游标j从后往前扫描，寻找比pivot小的元素x，找到后停止，准备把这个元素扔到前面。在同一个数组中排序并没有扩大数组的容量，那怎么扔掉呢？因为刚才选择了第一个元素作为pivot，所以他们当前的位置关系是pivot...x。还有，排序目标是升序，x是一个很小的值但是放在pivot后面，也不合适，需要调换位置。交换后，他们的位置关系变成了x...pivot。此时j指向pivot，i指向x。现在让游标i向后扫描，寻找一个比pivot大的元素y，找到就停止，和pivot交换。完成后的位置关系为pivot...y，此时i指向pivot，即pivot已经移动到i的位置。这里有一个小的优化。在i的反向扫描开始时，i指向x，而在上一轮j游标扫描中，我们已经知道x小于pivot，所以完全可以让i跳过x，不需要再次与x和pivot进行比较。结论是j游标交换完成后，顺便把i往后移一位，i++。同理，第i个游标交换完成后，顺便将j向前移动一位，j--。扫描过程中发现有等于pivot的元素怎么办？由于我们不是在讨论三路分割的快速排序优化算法，所以这里的答案是：忽略它。当它们被一个接一个地排序时，它们将慢慢地被较小的元素推回并被较大的元素向前推。最后的结果是，他们都会随着枢轴移动到中间的位置。当i和j相遇时，i和j都指向枢轴。在我们的分区方法中，返回的是i，也就是分区完成后返回的pivot位置。接下来让分割后的两个数组按照上面的步骤进行分区。这是一个递归的过程，直到数组不能再划分，排序完成。快速排序是一个很天才的设计，实现起来并不复杂，关键是真的很快~0){return;}[selfjx_quickSortWithLowIndex:0highIndex:self.count-1usingComparator:comparatordidExchange:exchangeCallback];}-(void)jx_quickSortWithLowIndex:(NSInteger)lowhighIndex:(NSInteger)highusingComparator:(exchangeSortComparator)comparatordidExchange:(ExchangeCallback>(JXlow)=high){return;}NSIntegerpivotIndex=[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{idpivot=self[low];NSIntegeri=low;NSIntegerj=high;while(i
