图解快排：Objective-C实现

原理

一组数字，我们选取一个数字p，每一次都将小于p的数字放在左边，大于p的数字放在右边，那边一遍下来就会保证p的位置正确的。

我们知道冒泡排序是通过每一趟交换而将数字归位的，那么我们可以通过交换达到目的。

图解

给定一个数组[9, 6, 1, 5, 2, 4, 3, 8 , 7, 0]，我们进行从小到大排序。

快速排序_01.png

代码

- (void)quickSortWithArray:(NSMutableArray<NSNumber *> **)array leftIndex:(NSInteger)leftIndex rightIndex:(NSInteger)rightIndex {
   if (leftIndex > rightIndex) {
     return;
   }

   int privot = [(*array)[leftIndex] intValue];
   NSInteger i = leftIndex;
   NSInteger j = rightIndex;
   while (i != j) {
     int iValue = [(*array)[i] intValue];
     int jValue = [(*array)[j] intValue];
     while (i < j && jValue >= privot) {
       j--;
       jValue = [(*array)[j] intValue];
     }
     while (i < j && iValue <= privot) {
       i++;
       iValue = [(*array)[i] intValue];
     }

     if (i < j) {
       NSNumber *temp = (*array)[i];
       (*array)[i] = (*array)[j];
       (*array)[j] = temp;
     }
   }

   (*array)[leftIndex] = (*array)[i];
   (*array)[i] = @(privot);

   [self quickSortWithArray:array leftIndex:leftIndex rightIndex:i - 1];
   [self quickSortWithArray:array leftIndex:i + 1 rightIndex:rightIndex];
}

复杂度

由上面图解和代码可知，每一次排序我们用到递归分治的思想。快速排序的最差时间复杂度和冒泡排序是一样的都是 O(N2)，它的平均时间复杂度为 O(NlogN)。

数组大小(n)	耗时(s)
1000	0.000538
10000	0.005773
100000	0.072908
1000000	0.831501
10000000	9.630642

可以看到，快速排序比冒泡排序快了很多