在眾多的排序方法中，有一種快速排序。如果你讀了我的Objective-C實(shí)現(xiàn)冒泡排序,那么你一定會覺得冒泡排序的實(shí)現(xiàn)雖然很簡單，但是它的效率真的是太慢了。接下來我將介紹一種更為高效的排序方法－－快速排序。
1,什么是快速排序
快速排序由 C. A. R. Hoare(東尼·霍爾,Charles Antony Richard Hoare)在 1960 年提出,之后又有許多人做了進(jìn)一步的優(yōu)化。這種排序方法是基于二分的思想來實(shí)現(xiàn)的，簡單的說就是將一個大的問題通過不斷的一分為二化簡為較小的問題來解決。通過二分化簡了問題的規(guī)模來提高解決問題的效率。因此我們將發(fā)現(xiàn)快速排序的平均時間復(fù)雜度是O(nlogn),最差時間復(fù)雜度是O(n^2)。是不是發(fā)現(xiàn)快速排序真的很快速呢？
2,快速排序描述
快速排序圖解
作者比較懶??，圖片來自《啊哈！算法》
從上面的圖片我們可以發(fā)現(xiàn)
(1),快速排序的思想就是從無序數(shù)組中找出一個基準(zhǔn)數(shù)，并且設(shè)定兩個哨兵值分別放置于數(shù)組的左右兩端。
(2),接下來我們讓右邊的哨兵值先向左邊移動，當(dāng)我們發(fā)現(xiàn)有值小于基準(zhǔn)數(shù)時我們讓哨兵值停下來。(因?yàn)槲覀兊幕鶞?zhǔn)數(shù)找的是最左邊的數(shù)，因此我們需要先移動右邊的哨兵值，否則基準(zhǔn)數(shù)將無法回到正確的位置。)
(3), 然后我們需要讓左邊的哨兵值向右移動，當(dāng)發(fā)現(xiàn)數(shù)值大于基準(zhǔn)數(shù)時停下來。
(4), 交換左右哨兵值指向的數(shù)值，繼續(xù)以上的移動直到兩個哨兵值指向同一個位置。
(5),將基準(zhǔn)數(shù)與哨兵值指向的數(shù)值進(jìn)行交換。這樣我們就講基準(zhǔn)值放到了正確的位置。
(6),以基準(zhǔn)數(shù)現(xiàn)在的位置為中心，將數(shù)組分為左右兩部分，分別設(shè)定基準(zhǔn)數(shù)和哨兵值。重復(fù)1到6中描述的步驟。
從以上的步驟描述當(dāng)中我們將會發(fā)現(xiàn)，每次移動我們動能將基準(zhǔn)數(shù)放到正確的位置，基準(zhǔn)數(shù)比較的范圍變大了，因此也提高了算法的效率。而冒泡排序每次只是比較相鄰兩個數(shù)的大小。
3,Objective-C實(shí)現(xiàn)快速排序
- (void) quickSortFromLeft:(NSInteger)leftIndex toRight:(NSInteger)rightIndex {
if (leftIndex >= rightIndex) {
return;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
NSInteger base = [self.mutableArray[leftIndex] integerValue];
while (i != j) {
while ([self.mutableArray[j] integerValue] >= base && i < j) {
j --;
}
while ([self.mutableArray[i] integerValue] <= base && i < j) {
i ++;
}
if (i < j) {
NSInteger temp = [self.mutableArray[j] integerValue];
self.mutableArray[j] = self.mutableArray[i];
self.mutableArray[i] = [NSNumber numberWithInteger:temp];
}
}
NSInteger temp = [self.mutableArray[j] integerValue];
self.mutableArray[j] = [NSNumber numberWithInteger:base];
self.mutableArray[leftIndex] = [NSNumber numberWithInteger:temp];
[self quickSortFromLeft:leftIndex toRight:i-1];
[self quickSortFromLeft:i+1 toRight:rightIndex];
}
