快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据以设定的枢纽位置为基准，分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序是对冒泡排序的优化，要比冒泡排序的效率高出几个数量级。
之所以没打印10万级的排序对比是因为冒泡排序时间太久了，但是可以看一下快速排序的计算时间。
100000个随机数的计算时间是 \ 0.129158秒
1000000个随机数的计算时间是 \ 1.429434秒
差距大的原因很明显，冒泡排序做了很多无用功的数值比较，打印出来看一下就知道了。
可以看到10000个随机数的比较冒泡排序比快速排序多了49873225次的无用比较，差距太悬殊了。
冒泡排序大家都很熟了
NSMutableArray *snums = [NSMutableArray array];
for (int i = 0; i< 10000; i++) {
NSInteger num = arc4random()%10000000;
[snums addObject:@(num)];
}
// 冒泡排序升序
for (int i = 0; i < snums.count -1; i++) {
for (int j=i+1; j < snums.count; j++) {
if ([snums[i] integerValue] > [snums[j] integerValue]) {
[snums exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
// 冒泡排序降序
for (int i = 0; i < snums.count -1; i++) {
for (int j=i+1; j < snums.count; j++) {
if ([snums[i] integerValue] < [snums[j] integerValue]) {
[snums exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
-
快速排序的思路
1 . 设置两个变量i，j，排序开始时i = 0，j = mutableArray.count - 1；
2 . 设置数组的第一个值为比较基准数也叫枢纽key，key = mutableArray.count[0]；
3 . 因为设置key为数组的第一个元素，所以先从数组最右边开始往前查找比key小的值。如果没有找到，执行j-- 然后继续往前搜索；如果找到则将mutableArray[j]的值赋给mutableArray[i]，并且停止往前搜索，进入第4步；
4 . 从i位置开始往后搜索比key大的值，如果没有找到，执行i++继续往后搜索；如果找到则将mutableArray[i]的值赋给mutableArray[j]，并且停止往后搜索；
5 . 将key值赋给mutableArray[i];
6 . 以i为分界线分别对两侧的数递归执行上述步骤，直到i == j停止排序。
举例：
待排序数组是[2,5,4,1,3];那么key=2，这个时候我们可以理解为数组的第一个位置腾出一个坑，成了[(),5,4,1,3],而2由key先代为保管,i=0，j=4；
这个时候我们进行上述步骤的第3步，key=2 依次比较后1<2,所以1就填到了2的坑上成了[1,5,4,(1),3]，因为1赋值给了2那个位置，这时j=3，i=0；
这个时候我们进行上述步骤的第4步，key=2 依次比较后 5>2,所以5就填到了1最开始的位置，数组变成了[1,(5),4,5,3],因为5赋值给了原来1的位置，这时i=1，j=3；
那么接下来也就是第5步了，原来5的位置由我们拿出来的key=2 来填上，数组变成了[1,2,4,5,3]，然后把数组从i的位置分成两部分index范围[0,1],和[1,4]两部分，然后继续递归执行上述步骤。
通过对数组不断的拆分比较最终完成排序。
- (void)quiklookAlgorithm{
NSMutableArray *mnums = [NSMutableArray array];
for (int i = 0; i< 10000; i++) {
NSInteger num = arc4random()%10000000;
[mnums addObject:@(num)];
}
NSDate *start = [NSDate date];
[self quiklookSortWithArray:mnums withLeftIndex:0 withRightIndex:mnums.count-1];
NSDate *end = [NSDate date];
NSTimeInterval timeInterval = [end timeIntervalSinceDate:start];
NSLog(@"%ld个数的快速排序计算时间：%f秒 进行计算的比较次数%ld",mnums.count,timeInterval,_pNum);
}
- (void)quiklookSortWithArray:(NSMutableArray *)mArray
withLeftIndex:(NSInteger)leftIndex
withRightIndex:(NSInteger)rightIndex{
if (leftIndex >= rightIndex) {
return;
}
// 基准数
NSInteger i = leftIndex;
NSInteger j = rightIndex;
// 把key刨出来
NSInteger key = [mArray[i] integerValue];
// // 降序排列
// while (i < j) {
// // 从右边j开始查找比基准数小的值
// while (i<j && [mArray[j] integerValue] <= key) {
// j--;
// }
// // 如果比基准数小
// mArray[i] = mArray[j];
//
// // 从左边i开始查找比基准数大的值
// while (i<j && [mArray[i] integerValue] >= key) {
// i++;
// }
// // 如果比基准数大
// mArray[j] = mArray[i];
// }
// 升序排列
while (i < j) {
// 从右边j开始查找比基准数小的值
while (i<j && [mArray[j] integerValue] >= key) {
j--;
_pNum += 1;
}
// 如果比基准数小
mArray[i] = mArray[j];
// 从左边i开始查找比基准数大的值
while (i<j && [mArray[i] integerValue] <= key) {
i++;
_pNum += 1;
}
// 如果比基准数大
mArray[j] = mArray[i];
}
// 把key填回坑里
mArray[i] = @(key);
/** 递归排序 **/
[self quiklookSortWithArray:mArray withLeftIndex:leftIndex withRightIndex:i-1];
[self quiklookSortWithArray:mArray withLeftIndex:i+1 withRightIndex:rightIndex];
}
