简单的了解了一下快速排序的原理，并自己实现了一下。下面以升序排列为例。
其实快速排序就是这么几个步骤：
- 先从数列中取出一个数作为基准，一般都是取数组的第一个数。
- 所有小于“基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区操作。（分区操作结束后，基准元素所处的位置就是最终排序后它的位置）
- 对”基准”左边和右边子区间不断重复第一步和第二步，直到各区间只有一个数。
说是这么说，但是真正在代码中实现起来也并没有像说的那样简单。
取基准值这个简单，重要的是怎么样把小于基准的放到左边，大于基准的放到右边。其实方法有很多种，但是要尽量高效和尽量少占内存。
我最开始觉得这个特别的容易实现，因为我们的iOS的可变数组已经给出了很多的API，交换位置，插入，删除等，我们直接在一个可变数组里本着小的向左大的向右的原则执行插入删除还不行吗？后来一想这些方法应该是通过遍历存储数据的链表实现的，大量的进行查询操作很耗时的，所以我就放弃了这个想法，着重看了网上的那个”哨兵“实现方法。
叫”哨兵“，其实就是用了i,j两个标识，看一下下面这些图片吧，我们一边看图一边讲解实现原理。
从图中可以看出来这个数组无序的存了10个数值，排序第一次找基准值是相对于整个数组的，我们通常用第一个元素（下标0）当做基准值，也就是6。
然后我们给要排序的区间设置两个标识，i代表最左边（下标最小），j代表最右边（下标最大），然后开始遍历数组。
开始
一定是要j先开始，原因下面再说
//baseNum就是我们取的基准值
while ([array[j] integerValue]>=baseNum && i<j) {
j --;
}
while ([array[i] integerValue]<=baseNum && i<j) {
i ++;
}
在用j遍历的时候，找到比基准值小的就停止，然后再用i进行遍历，找到比基准值大的也停止，同时要限制j>i。然后交互i和j两个位置的数值。
第一次交换
第一次交换完成
整个这个过程一直到i和j这两个标识移动到相等的时候才停止。所以i和j要继续移动。
第二次交换
第二次交换完成
i和j在都等于5的时候相遇，这是跳出大循环，然后交换下标为5的这个位置的数值和基准值。
相遇
与基准数交换
完成交换之后，对整个数组区间的位置交换就完成了，我们去的基准值，也就是6，他现在的位置已经是最终的位置了。
完成
然后我们要运行递归思想，刚才的位置i=j=5,所以通过这个下边把整个数组分为了两部分，然后对每一个小区在进行上面的这个过程，直到分隔区域之后，每个区域里只有一个元素。
下面我们来看整体的代码, 很简单就不解释了：
// 正序
- (void)quicklySortArray:(NSMutableArray *)array fromIndex:(int)startIndex toIndex:(int)endIndex {
if (startIndex >= endIndex) {
return;
}
NSInteger baseNum = [array[startIndex] integerValue];
int i = startIndex;
int j = endIndex;
while (i != j) {
while ([array[j] integerValue]>=baseNum && i<j) {
j --;
}
while ([array[i] integerValue]<=baseNum && i<j) {
i ++;
}
if (i < j) {
NSInteger temp = [array[j] integerValue];
array[j] = array[i];
array[i] = [NSNumber numberWithInteger:temp];
}
}
// 当i==j的时候，交换位置
NSInteger temp = [array[j] integerValue];
array[j] = [NSNumber numberWithInteger:baseNum];
array[startIndex] = [NSNumber numberWithInteger:temp];
[self quicklySortArray:array fromIndex:startIndex toIndex:i-1];
[self quicklySortArray:array fromIndex:i+1 toIndex:endIndex];
}
网上还有很多的实现方法，while循环中的代码是这样子的：
while (i != j) {
while ([array[j] integerValue]>=baseNum && i<j) {
j --;
}
array[i] = array[j];
while ([array[i] integerValue]<=baseNum && i<j) {
i ++;
}
array[j] = array[i];
}
// 当i==j的时候
array[i] = @(baseNum);
这种实现不是在等i和j都停止了才去交换位置，他也是先通过j遍历，j停止之后，因为此时i==0,同时0这个位置的值我们已经取出来作为基准值了，所以此时就直接把找到的这个小于基准值的数先放大下标0这个位置了，然后在通过i遍历，找到大于基准的值之后就可以直接赋值到刚才下标为j的位置了。
这种方法最后就不用了交换i==j位置的值和基准值，而是直接把这个基准值赋值给i==j这个位置了
就是这样 ~ 大家有不清楚的地方可以留言讨论，也可以自己debug跟一下数值 ~
为什么一定要j（右边）先开始？
说实话，你要说具体的描述这个原因，我也很难，我只能举个特殊情况来回答这个问题。
加入最开始的时候取得这个基准值就是所有数据里面最小的，如果是从i开始遍历呢，因为基准已经是最小值了，所以就会一直遍历到i==j（这时候j的值还等于数组的最大下标），然后跳出循环交换基准值和i==j这个位置的值，这明显是错的。但是从j开始遍历呢就会避免了这种问题。哎，我也只能是这么解释了 ~ 😆
网友评论