快速排序(Quicksort)作為二十世紀(jì)最偉大的算法之一碌燕。快速排序的是一個(gè)時(shí)間復(fù)雜度平均為O(nlog2n)的不穩(wěn)定算法修壕。
快速排序的思想是從數(shù)組中任意選取一個(gè)元素v遏考。然后將v放到它排序好后應(yīng)該所在的正確位置，此時(shí)青团，元素v會(huì)將數(shù)組分割成兩部分督笆，
v左邊一部分都比v要小诱贿，v右邊的都比v要大珠十，之后對(duì)分割出的兩個(gè)子數(shù)組遞歸進(jìn)行此分割操作，遞歸完成時(shí)晒杈，整個(gè)數(shù)組就排好序了壳嚎。
比如烟馅，我們?nèi)我膺x擇此數(shù)組第一個(gè)元素4。
然后將4放到他排序好后的應(yīng)該所在的位置刊驴，并使4前面的都小于四捆憎，后邊的都大于4。
之后對(duì)前后兩部分繼續(xù)進(jìn)行此操作致份，即可完成整個(gè)的排序氮块。
所以對(duì)于快速排序算法來(lái)說(shuō)诡宗，最重要的就是塔沃，如何把一個(gè)選定的元素挪到正確的位置上，并且使前后兩部分的都滿足要求螃概。這也是快速排序算法的核心名扛。
在這個(gè)過(guò)程中肮韧，我們通常都選擇第一個(gè)元素來(lái)作為我們分界的標(biāo)識(shí)。我們給它起名叫v超燃，同時(shí)用索引L記錄他的位置拘领。
之后我們?cè)趯?duì)v后面的元素一個(gè)一個(gè)的遍歷過(guò)程中约素，我們將逐漸的整理出一部分是小于v的圣猎，一部分是大于v的。兩部分的分界點(diǎn)我們用J來(lái)標(biāo)識(shí)慢显。
而當(dāng)前訪問(wèn)的元素e我們用索引i來(lái)標(biāo)識(shí)荚藻。
此時(shí)數(shù)組[L+1应狱，J]這個(gè)區(qū)間都是小于v的，[J+1落塑，i-1]這個(gè)區(qū)間都是大于v的,
之后我們看i這個(gè)位置的元素e罐韩，他怎么放到兩個(gè)區(qū)間的某一個(gè)里去散吵。
我們將e與v進(jìn)行比較蟆肆，如果比v大炎功，說(shuō)明它屬于圖中紫色的大于v的區(qū)間內(nèi)，此時(shí)我們直接i自增1赁温，直接指向下一個(gè)需要與v比較的元素股囊，而e就已經(jīng)是屬于紫色的大于v的區(qū)間內(nèi)了更啄。
如果e比v小呢祭务，我們就將元素e與J索引的下一個(gè)位置也就是J+1位置的元素交換。
此時(shí)e就屬于藍(lán)色小于v的區(qū)間內(nèi)了，然后將J索引自增1偎行，指向新的邊界，i索引自增1熄云，進(jìn)行下一個(gè)元素的判斷妙真。
當(dāng)所有的元素遍歷完時(shí)珍德，大于v和小于v的兩部分就分完了锈候。
最后泵琳，我們要將元素v挪到正確的位置上，只需將索引L位置的v與索引J位置的元素進(jìn)行交換谷市。
整個(gè)操作就完成了迫悠。之后對(duì)藍(lán)色的小于v部分和紫色大于v部分的子數(shù)組重復(fù)以上操作巩梢，整個(gè)快速排序就完成了且改。
接下來(lái)，我們用代碼實(shí)現(xiàn)一下快速排序碍拆。
NSMutableArray * array = [NSMutableArray arrayWithObjects:@8,@7,@6,@5,@4,@3,@2,@1, nil];
//調(diào)用排序
[self quickSortArray:array];
- (void)quickSortArray:(NSMutableArray *)array {
[self quickSort:array low:0 high:array.count - 1];
}
- (void)quickSort:(NSMutableArray *)array low:(int)low high:(int)high {
//遞歸退出條件判斷
if (low>=high) {
return;
}
//對(duì)數(shù)組進(jìn)行分割操作感混，返回分界處索引index
int index = [self quick:array low:low high:high];
//對(duì)從最低位索引low到分界處索引index前一位的元素遞歸進(jìn)行分割操作
[self quickSort:array low:low high:index-1];
//對(duì)分界處索引index的后一位到末尾索引high進(jìn)行遞歸分割操作
[self quickSort:array low:index + 1 high:high];
}
- (int)quick:(NSMutableArray *)array low:(int)low high:(int)high {
//分界處索引j的初始值為數(shù)組第一個(gè)元素的索引---low
int j = low;
//記錄第一個(gè)元素的大小礼烈，方便與之后遍歷的元素比較
NSInteger key = [array[low] integerValue];
for (int i = low + 1; i <= high; i++) {
//如果當(dāng)前元素小于開(kāi)始選取的第一個(gè)元素此熬，則交換索引j+1和i的元素滑进，同時(shí)j自增1.
if ([array[i] integerValue] < key) {
[array exchangeObjectAtIndex:j+1 withObjectAtIndex:i];
j++;
}
}
//全部遍歷完成后扶关，交換索引low與j的元素数冬，將第一個(gè)元素放到正確的位置
[array exchangeObjectAtIndex:low withObjectAtIndex:j];
//返回分界點(diǎn)索引
return j;
}
雙路快速排序
當(dāng)數(shù)組中很多重復(fù)的元素時(shí),上文的那種做法會(huì)將數(shù)組中與選定元素v相等的元素極不平衡的分配到前后兩個(gè)部分中,這種情況我們之前快速排序算法就會(huì)退化成趨近于O(n2)級(jí)別的算法拐纱。
解決方式就是秸架，之前我們是單一的從左側(cè)開(kāi)始遍歷元素咕宿，分出兩個(gè)部分，現(xiàn)在我們從數(shù)組左右兩側(cè)分別開(kāi)始遍歷。
我們將小于等于v和大于等于v的分別放在數(shù)組的兩端芽突，用i代表從左向右遍歷的位置寞蚌，J代表從右向左遍歷的位置挟秤。
i向后遍歷時(shí)，如果當(dāng)前元素小于v則繼續(xù)向后遍歷管宵，如果大于等于v則停止箩朴。
J向前遍歷如果當(dāng)前元素大于v則繼續(xù)向前遍歷秋度，如果小于等于v則停止荚斯。
此時(shí)我們將索引i的元素e和索引J處的元素o交換下位置查牌，就好了僧免。
之后i繼續(xù)向后遍歷懂衩，J繼續(xù)向前遍歷浊洞。
直到i和J重合法希，就結(jié)束了靶瘸。
數(shù)組中即使有大量相等的元素，也會(huì)平均分到兩端屋剑。
代碼實(shí)現(xiàn)一下雙路快速排序唉匾。
NSMutableArray * array = [NSMutableArray arrayWithObjects:@8,@7,@6,@5,@4,@3,@2,@1, nil];
//調(diào)用排序
[self quickSortArray:array];
- (void)quickSortArray:(NSMutableArray *)array {
[self quickSort:array low:0 high:array.count - 1];
}
- (void)quickSort:(NSMutableArray *)array low:(int)low high: (int)high {
if (low>=high) {
return;
}
int index = [self quick:array low:low high:high];
[self quickSort:array low:low high:index-1];
[self quickSort:array low:index + 1 high:high];
}
- (int)quick:(NSMutableArray *)array low:(int)low high:(int)high {
int j = high;
int i = low + 1;
NSInteger key = [array[low] integerValue];
while (true) {
while (i <= high && [array[i] integerValue] < key) {
i++;
}
while (j>=low + 1 && [array[j] integerValue] > key) {
j--;
}
if(i > j) {
break;
}
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
i++;
j--;
}
[array exchangeObjectAtIndex:low withObjectAtIndex:j];
return j;
}
如果覺(jué)得作者對(duì)哪里的理解有偏差或者其他的優(yōu)化巍膘，希望不吝賜教芋簿，留言指正与斤。謝謝支持~
