时间复杂度分析
最好的情况
注意：划分的时候我们忽略了-1操作，本来应该划分为n/2,n/2-1，我们简化成n/2,n/2,并且我们假定n/2都是整数
令数组A[n],最好的情况是，每一轮都可以做到等分数组,左边A[n/2]，右边A[n/2],以此类推......
令层数为k，有1*2k-1 = n,则k = ，每层的和都是n，所以遍历的总次数为n
平均情况
快速排序的平均请接近于最好情况，而不是最坏情况
例如，加入划分算法总是按照9：1的情况划分，此时，我们得到的快速排序的时间复杂度的递归公式为
T(n) = T(9n/10)+T(n/10)+cn
图示如下
从图示我们看到时间复杂度应该为cn*
对对数进行换底，底数变为2，并且省去常数项变为n
令c1，c2为常数，由换底公式可以推导出,
属于同一时间复杂度，所以只要划分是按照常数比例的，那么快排的时间复杂度都为n
最坏的情况
快速排序退化成冒泡排序，时间复杂度为
code
- (void)quickSortArr:(NSMutableArray *)array withLeftIndex:(NSInteger )leftIndex andRightIndex:(NSInteger )rightIndex{
if (leftIndex > rightIndex) {
return;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
NSInteger key = [array[i]integerValue];
while (i < j) {
while (i < j && key <= [array[j] integerValue]) {
j --;
}
array[i] = array[j];
while (i < j && key >= [array[i] integerValue]) {
i ++;
}
array[j] = array[i];
}
array[i] = @(key);
//前面排序
[self quickSortArr:array withLeftIndex:leftIndex andRightIndex:i -1];
//后面排序
[self quickSortArr:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
