快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)以設(shè)定的樞紐位置為基準(zhǔn)逼肯，分割成獨立的兩部分胎围，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小留攒，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序坚洽，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列笛质。
快速排序是對冒泡排序的優(yōu)化泉沾，要比冒泡排序的效率高出幾個數(shù)量級。
之所以沒打印10萬級的排序?qū)Ρ仁且驗槊芭菖判驎r間太久了妇押，但是可以看一下快速排序的計算時間跷究。
100000個隨機數(shù)的計算時間是 \ 0.129158秒
1000000個隨機數(shù)的計算時間是 \ 1.429434秒
差距大的原因很明顯，冒泡排序做了很多無用功的數(shù)值比較敲霍，打印出來看一下就知道了俊马。
可以看到10000個隨機數(shù)的比較冒泡排序比快速排序多了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 . 設(shè)置兩個變量i柴我，j解寝，排序開始時i = 0，j = mutableArray.count - 1艘儒；
2 . 設(shè)置數(shù)組的第一個值為比較基準(zhǔn)數(shù)也叫樞紐key聋伦，key = mutableArray.count[0]；
3 . 因為設(shè)置key為數(shù)組的第一個元素界睁，所以先從數(shù)組最右邊開始往前查找比key小的值觉增。如果沒有找到，執(zhí)行j-- 然后繼續(xù)往前搜索翻斟；如果找到則將mutableArray[j]的值賦給mutableArray[i]逾礁，并且停止往前搜索，進(jìn)入第4步杨赤；
4 . 從i位置開始往后搜索比key大的值敞斋，如果沒有找到截汪，執(zhí)行i++繼續(xù)往后搜索疾牲；如果找到則將mutableArray[i]的值賦給mutableArray[j]，并且停止往后搜索衙解；
5 . 將key值賦給mutableArray[i];
6 . 以i為分界線分別對兩側(cè)的數(shù)遞歸執(zhí)行上述步驟阳柔，直到i == j停止排序。
舉例：
待排序數(shù)組是[2,5,4,1,3];那么key=2蚓峦，這個時候我們可以理解為數(shù)組的第一個位置騰出一個坑舌剂，成了[(),5,4,1,3],而2由key先代為保管,i=0，j=4暑椰；
這個時候我們進(jìn)行上述步驟的第3步霍转，key=2 依次比較后1<2,所以1就填到了2的坑上成了[1,5,4,(1),3]，因為1賦值給了2那個位置一汽，這時j=3避消，i=0；
這個時候我們進(jìn)行上述步驟的第4步召夹，key=2 依次比較后 5>2,所以5就填到了1最開始的位置岩喷，數(shù)組變成了[1,(5),4,5,3],因為5賦值給了原來1的位置，這時i=1监憎，j=3纱意；
那么接下來也就是第5步了，原來5的位置由我們拿出來的key=2 來填上鲸阔，數(shù)組變成了[1,2,4,5,3]偷霉，然后把數(shù)組從i的位置分成兩部分index范圍[0,1],和[1,4]兩部分迄委，然后繼續(xù)遞歸執(zhí)行上述步驟。
通過對數(shù)組不斷的拆分比較最終完成排序腾它。
- (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個數(shù)的快速排序計算時間：%f秒 進(jìn)行計算的比較次數(shù)%ld",mnums.count,timeInterval,_pNum);
}
- (void)quiklookSortWithArray:(NSMutableArray *)mArray
withLeftIndex:(NSInteger)leftIndex
withRightIndex:(NSInteger)rightIndex{
if (leftIndex >= rightIndex) {
return;
}
// 基準(zhǔn)數(shù)
NSInteger i = leftIndex;
NSInteger j = rightIndex;
// 把key刨出來
NSInteger key = [mArray[i] integerValue];
// // 降序排列
// while (i < j) {
// // 從右邊j開始查找比基準(zhǔn)數(shù)小的值
// while (i<j && [mArray[j] integerValue] <= key) {
// j--;
// }
// // 如果比基準(zhǔn)數(shù)小
// mArray[i] = mArray[j];
//
// // 從左邊i開始查找比基準(zhǔn)數(shù)大的值
// while (i<j && [mArray[i] integerValue] >= key) {
// i++;
// }
// // 如果比基準(zhǔn)數(shù)大
// mArray[j] = mArray[i];
// }
// 升序排列
while (i < j) {
// 從右邊j開始查找比基準(zhǔn)數(shù)小的值
while (i<j && [mArray[j] integerValue] >= key) {
j--;
_pNum += 1;
}
// 如果比基準(zhǔn)數(shù)小
mArray[i] = mArray[j];
// 從左邊i開始查找比基準(zhǔn)數(shù)大的值
while (i<j && [mArray[i] integerValue] <= key) {
i++;
_pNum += 1;
}
// 如果比基準(zhǔn)數(shù)大
mArray[j] = mArray[i];
}
// 把key填回坑里
mArray[i] = @(key);
/** 遞歸排序 **/
[self quiklookSortWithArray:mArray withLeftIndex:leftIndex withRightIndex:i-1];
[self quiklookSortWithArray:mArray withLeftIndex:i+1 withRightIndex:rightIndex];
}
