算法的个人理解：
基于分治思想，将复杂的问题简单化；具体的做法是在待排序的数组中，选取一个基准数，这个基准数一般情况下就选取数组中的第一个或者最后一个，然后将数组中大于基准数的数放到基准数的右边，小于基准数的放到基准数左边，(这个过程叫做基准数归位)；然后再对基准数左右两边的数组采取相同的做法，也选取数组里面的第一个数为基准数（也可以选取数组里面的最后一个数为基准数），然后让其归位。最后如果左右数组中的基准数都已归位，那么这个数组就是有序的；
具体的实现思路：首先创建三个变量;一个用来存储数组中起始位置，一个用来存储数组中最后的位置，最后一个变量用来存储基准数(这里我们首次使用数组第一个元素作为基准数，也就是基准数在数组的左边)；因为基准数是在数组的左边，所以最先从右边开始查找（相反的，如果基准数是在数组的右边，那么就从最左边开始查找），在i和j不相等且i小于j的情况下，只要没有找到比基准数小的数，那么就要往左边移动（j--），找到比基准数小的数时就停下来，然后保存该数的下标（其实是记录在变量j中的）；当右边停下来之后左边开始查找，只要没找到大于基准数的值，那么就一直往右边移动（i++），找到比基准数大的数时就停下来，然后保存该数的下标（记录在变量i中），比较i和j是否相等，如果不相等：交换下标为i和j的值；如果相等：将基准数的值和下标为i或j的值进行交换，最后递归调用方法让左边和右边的数组的基准数归位，待所有的基准数都已经归位，那么数组就是有序的。
- (void)quickSortWithArray:(NSMutableArray*)array left:(NSInteger)left right:(NSInteger)right{
//数组不需要排序（异常处理）
if(left >= right)return;
//数组第一个位置
NSIntegeri = left;
//数组最后一个位置
NSIntegerj = right;
//将数组中第一个位置的值作为---基准数
NSIntegerpivot = [array[left]integerValue];
while(i != j) {//当i，j不相等的时候：右边的哨兵往左边移动，找出比基准数小的值放到左边（注意：如果选取的基准数是在左边，那么就必须是右边的哨兵先走；反之，基准数取的是右边的话，那么左边的哨兵必须先走）；当右边的哨兵找到小于基准数的时候就停下来，并且记录当前小于基准数的数的下标，接着左边的哨兵向右边移动，找出比基准数大的数放到右边，如果找到比基准数大的值就停止，记录下当前大于基准数的这个数的下标；
//从后往前走,直到找到小于<基准>的数字,此时j保存那个数字的下标位置
while(i < j && pivot <= [array[j]integerValue]) {
j--;
}
//再从前往后走,直到找到大于<基准>的数字,此时i保存那个数字的下标位置
while(i < j && pivot >= [array[i]integerValue]) {
i++;
}
//互换位置
//当右边哨兵找到一个小于基准数的数，同时左边哨兵也找到一个大于基准数的数，并且它们保存的下标数不相等，那么就直接交换他们的值
[arrayexchangeObjectAtIndex:i withObjectAtIndex:j];
}
//当i == j的时候，将基准数归位,将基数所在位置的值与i/j相等时的位置的值进行交换
[arrayexchangeObjectAtIndex:i withObjectAtIndex:left];
//最后递归调用该方法让基准数左边和右边的数组的基准数归位。（这里体现了算法通过使用分治的思想解决问题）
//继续左边的排序
[selfquickSortWithArray:arrayleft:leftright:i -1];
//继续右边的排序
[selfquickSortWithArray:arrayleft:i +1right:right];
}
网友评论