序言

由于快速排序有多個優(yōu)化，所以我今天就就從最開始的快速排序到最終版本的三路快速排序分別給大家呈現(xiàn)出來，優(yōu)化的過程也會逐步帶領(lǐng)大家慢慢的分析，好了，廢話不多說，我們從第一個版本的快速排序開始:

第一個版本的快速排序

講快速排序之前，我還是老規(guī)矩先上一張圖，不然我感覺自己描述不清楚（莫見怪^_）

第一個版本快速排序.png

下面根據(jù)圖片我們，再來總結(jié)一下它的概念和步驟：

1.從數(shù)列中挑出一個元素，稱為"基準"（pivot），
2.重新排序數(shù)列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（相同的數(shù)可以到任一邊）。在這個分區(qū)結(jié)束之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
3.遞歸地（recursively）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。

遞歸到最底部時，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個算法一定會結(jié)束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。說完了概念可能你還是會很迷糊，別急，我再來上一張圖：

第一個版本快排partition過程.png

大家不理解的肯定是這個partition過程，我們設(shè)定一個基準點，一般以數(shù)組的第一個元素為基準點，我們姑且稱之為V，我們將數(shù)組后續(xù)的元素依次與這個基準點V進行比較，當我們發(fā)現(xiàn)當前考察的元素array[i] < V的時候，我們將數(shù)組交換一下位置，也就是將數(shù)組的j+1這個位置的元素與i這個位置的元素進行交換，這時候我們發(fā)現(xiàn)橙色部分的元素新增了一個元素，也就是小于V的部分的元素增加了一個元素，但是當我們發(fā)現(xiàn)array[i] > V的時候我們該怎么辦呢？沒錯，我們壓根就不用懂，只需要讓i繼續(xù)往后走即可，這是因為大于V的部分本身就是在V對應(yīng)的索引后邊的，當我們的數(shù)組元素全部比較完成后，我們發(fā)現(xiàn)，數(shù)組已經(jīng)被分成了兩個部分了，一半是小于V的 ，一半是大于V 的，至此我們的partition過程也就完成了，當然此時我們數(shù)組的首個元素還是存放的V這個基準點，我們只需要將V放到j(luò)對應(yīng)的索引出即可（j是分界的索引位置），下面我們來看下代碼：

#pragma  mark -  第一個版本快速排序
#pragma  mark -
- (void)quickSort1:(NSMutableArray *)array {
    [self __quickSort1:array left:0 right:(int)array.count - 1];
}

- (void)__quickSort1:(NSMutableArray *)array left:(int)left right:(int)right {
    //判斷遞歸到底的情況
    if (left >= right) {
        return;
    }
    
    int p = [self patition1:array left:left right:right];
    [self __quickSort1:array left:left right:p];
    [self __quickSort1:array left:p +1 right:right];
    
}



/**
 對數(shù)組[left...right]部分進行快速排序注意是前后都是閉區(qū)間

 @param array 待排序數(shù)組
 @param left 左區(qū)間
 @param right 右區(qū)間
 @return 找到的中間的位置使得左半部分小于標定點V 右半部分大于V
 */
- (int)patition1:(NSMutableArray *)array left:(int)left right:(int)right {
    //標記變量 小于j的在左邊 大于j的在右邊 默認初始化為left
    int j = left;
    //初始化標定點為數(shù)組的左邊第一個元素
    NSNumber * V = array[left];
    for (int i = left + 1; i <= right; i++) {
        if (array[i] < V) {//只有當比較的當前元素小于標定點V時 交換位置，當array[i] > V時只需要讓i++就可以了，這里i已經(jīng)是++了，所以不用考慮 ，這樣這個當前元素就是在V的右邊部分
            [array exchangeObjectAtIndex:i withObjectAtIndex:j + 1];
            //索引j要++
            j++;
        }
    }
    //當走完上面的循環(huán)后，j就是那個使得標定點V左半部分小于V右半部分大于V的索引 此時將第一個元素也就是V與j所在的位置交換位置即可
    [array exchangeObjectAtIndex:j withObjectAtIndex:left];
    //返回索引J
    return j;
}

我們看到，這里快速排序也是通過遞歸的方式來的，所以這里和我前面說的歸并排序一樣，存在一個優(yōu)化點，那就是當元素范圍比較小的時候，我們可以采用插入排序，所以在遞歸結(jié)束的條件就可以這么寫：

    //判斷遞歸到底的情況
//    if (left >= right) {
//        return;
//    }

    //快速排序第一個優(yōu)化
    if (right - left <= 15) {
        [self insertionSort3:array left:left right:right];
        return;
    }

下面就應(yīng)該要測試一下了，我們通過三組測試用例來進行測試，分別是普通數(shù)組，近乎有序的數(shù)組、大量重復(fù)元素數(shù)組,這里我們用的是十萬的數(shù)量級：

    //生成普通的隨機數(shù)組
    NSMutableArray *normalArray = [self.testHelper generateRandomArray:100000 rangeLeft:1 rangeRight:10000];
    //大量重復(fù)元素
    NSMutableArray *repeatArray = [self.testHelper generateRandomArray:100000 rangeLeft:1 rangeRight:3];
    //生成近乎有序的排序數(shù)組
    NSMutableArray *nearArray = [self.testHelper generateNearlyOrderedArray:100000 swapTimes:10];
    //快速排序第一個版本普通數(shù)組
    NSMutableArray * quickSort1Normal = normalArray.mutableCopy;
    //快速排序第一個版本近乎有序數(shù)組
    NSMutableArray * quickSort1Near = nearArray.mutableCopy;
    //快速排序第一個版本大量重復(fù)數(shù)組
    NSMutableArray * quickSort1Repeat = repeatArray.mutableCopy;

    NSLog(@"============近乎有序的歸并排序耗時============");
    [self.testHelper testSortWithExcuteBlock:^{
        [self mergeSort:mergeSortNear];
    }];
    
    NSLog(@"============普通數(shù)組第一個版本快速排序耗時============");
    [self.testHelper testSortWithExcuteBlock:^{
        [self quickSort1:quickSort1Normal];
    }];
    
    NSLog(@"============近乎有序數(shù)組第一個版本快速排序耗時============");
    [self.testHelper testSortWithExcuteBlock:^{
        [self quickSort1:quickSort1Near];
    }];

下面是測試結(jié)果

第一個版本測試用例對比.png

我們發(fā)現(xiàn)在對近乎有序的數(shù)組以及大量重復(fù)元素的數(shù)組進行排序時，效率相當?shù)牡?，這是問什么呢？別急，我們一個一個來解決，

解決近乎有序數(shù)組的效率問題

我們先來解決第一個問題，那就是對于近乎有序的數(shù)組，采用我們第一個版本快速排序的時候效率很低問題，我們來分析一下原因，我們每次取出的基準點都是我們的第一個元素，當近乎有序的時候，也就是說，每一次右邊的元素都是要比第一個元素要大的，下面可以用一張圖來形容一下：

第一個版本快排退化為O(N^2).png

那我們怎么來解決這個問題呢？其實很簡單，我們采用隨機數(shù)的方式來解決就可以了，每次我們?nèi)〉幕鶞庶c不是第一個元素，而是隨機在數(shù)組中去一個元素作為我們的基準點，這樣就可以做到，每次都不是取到最小的那個元素了，優(yōu)化代碼如下：

    //快速排序第二個優(yōu)化 標定點取隨機數(shù)
    int randonNum = arc4random() % (right - left + 1) + left;
    [array exchangeObjectAtIndex:left withObjectAtIndex:randonNum];

此時再來看一下我們的測試結(jié)果：

第一個版本快速排序優(yōu)化近乎有序數(shù)組測試結(jié)果.png

解決大量重復(fù)元素數(shù)組的效率問題

下面，我們再來解決第二個問題，當我們發(fā)現(xiàn)有大量重復(fù)元素的時候，我們也發(fā)現(xiàn)效率很低，那我們再來分析一下我們在partition過程中的條件：

  if (array[i] < V) {//只有當比較的當前元素小于標定點V時 交換位置，當array[i] > V時只需要讓i++就可以了，這里i已經(jīng)是++了，所以不用考慮 ，這樣這個當前元素就是在V的右邊部分
            [array exchangeObjectAtIndex:i withObjectAtIndex:j + 1];
            //索引j要++
            j++;
        }

我們在這里判斷的是當小于V 的時候交換位置，所以我們就有大于等于V 的元素全部放到了右邊，所以在遞歸的時候會造成遞歸樹相當?shù)牟痪?，右邊部分永遠是大于左邊的部分，聰明的你肯定知道這樣效率是會大打折扣的，至此，我們的第二個版本的快速排序就該出生了。

第二個版本的快速排序

有了上面的分析，我們已經(jīng)知道，正是由于等于V的情況沒有分析，所以導(dǎo)致我們的第一個版本的快速排序就退化到了O (n^ 2)的時間復(fù)雜度，那么我們怎么來優(yōu)化呢？這其實就是我們第二個版本的快速排序要來解決的問題，我們也稱之為雙路快速排序，先來看一張圖:

第二個版本快排partition過程.png

既然我們的問題是等于V的部分過于集中到一邊，那么我們想辦法把等于V的部分分到兩邊不就行了嗎，從圖上看我們也知道了，通過均衡的將等于V的部分分別放置到左右兩邊，就可以達到均衡的目的，下面我們來看代碼：

#pragma  mark -  第二個版本快速排序
#pragma  mark -
/**
 第二個版本快速排序
 
 @param array 待排序數(shù)組
 */
- (void)quickSort2:(NSMutableArray *)array {
    [self __quickSort2:array left:0 right:(int)array.count - 1];
}

- (void)__quickSort2:(NSMutableArray *)array left:(int)left right:(int)right {
    //判斷遞歸到底的情況
    //    if (left >= right) {
    //        return;
    //    }
    
    //快速排序第一個優(yōu)化
    if (right - left <= 15) {
        [self insertionSort3:array left:left right:right];
        return;
    }
    
    int p = [self patition2:array left:left right:right];
    [self __quickSort2:array left:left right:p -1];
    [self __quickSort2:array left:p +1 right:right];
}


/**
 第二個版本的partition過程

 @param array 原數(shù)組
 @param left 左邊界
 @param right 右邊界
 @return 索引j使得左邊界小于等于j對應(yīng)的值右邊界大于等于j對應(yīng)的值
 */
- (int)patition2:(NSMutableArray *)array left:(int)left right:(int)right {
    //i標識小于等于V的索引；j是表示大于等于V的索引
    int i = left + 1,j = right ;
    //快速排序第二個優(yōu)化 標定點取隨機數(shù)
    int randonNum = arc4random() % (right - left + 1) + left;
    [array exchangeObjectAtIndex:left withObjectAtIndex:randonNum];
    //標定點
    int V = [array[left] intValue];
    //不停循環(huán)尋找到一個一個索引 讓前半部分小于等于V后半部分大于等于J
    while (1) {
        //如果左半部分考察的元素現(xiàn)在是小于V的只需要讓i繼續(xù)往后走即可
        while (i <= right && [array[i] intValue] < V) {//注意i最多到right的位置
            i++;
        }
        //當右半部分考察的元素是大于V的只需要讓j遞減即可
        while (j >= left +1 && [array[j] intValue] > V) {//注意j最多能到left + 1的位置
            j--;
        }
        //當i已經(jīng)大于J的時候證明所有已經(jīng)元素考察完畢了
        if (i > j) {
            break;
        }
        //走到這里 證明所有元素尚未考察完畢 且左半部分有一個元素已經(jīng)大于V了、右半部分也有一個元素小于V了 ，此時只需要交換一下兩個位置的元素 繼續(xù)循環(huán)即可
        [array exchangeObjectAtIndex:i withObjectAtIndex:j];
        i++;
        j--;
    }
    //循環(huán)結(jié)束后 將標定點交換到應(yīng)該存放的位置
    [array exchangeObjectAtIndex:left withObjectAtIndex:j];
    return j;
}

這里，我還是來講解一下這部分代碼，照顧下基礎(chǔ)比較弱的朋友，我們這里有兩個索引 i和 j,i初始化為l + 1的位置，j初始化為數(shù)組最后一個位置通過不斷的比較array[i]與V,當發(fā)現(xiàn)比V小時繼續(xù)往前走，當發(fā)現(xiàn)等于V或者是大于V就停下來，而j從右邊開始一直往前走，通過比較array[j]和V，如果發(fā)現(xiàn)比V大，就繼續(xù)往前走，直到等于V或者是小于V的時候，我們也停下來，這時候，i和j這個位置的元素只需要交換一下位置就可以讓數(shù)組維持左邊小于等于V，右邊的大于等于V的性質(zhì)，然后繼續(xù)比較下面的元素?？赐旰?，我們再來測試一下：

第一個版本和第二個版本快速排序?qū)Ρ?png

我們發(fā)現(xiàn)，就算是大量的重復(fù)元素，我們的第二個版本的快速排序也能保持不錯的性能，怎么樣，是不是很佩服前人的智慧，

第三個版本的快速排序

如果你以為這樣就完了，那你就打錯特錯了，前人的智慧那么無窮，當然是不斷在優(yōu)化這些算法的，先說一下，我們的第三個版本的快速排序依然是為了解決大量重復(fù)元素數(shù)組的問題的，下面我們來看一張圖：

第三個版本快速排序partition過程.png

我們可以看到，和第二個版本相比，我們多了一個部分，那就是 ==V的部分，第二個版本是將等于V的部分分攤到兩邊，而我們現(xiàn)在談的三路快速排序則是干脆將等于V的單獨拿出來放置到一個區(qū)域，下面我們來看下代碼實現(xiàn)吧：

#pragma  mark -  第三個版本快速排序
#pragma  mark -
- (void)quickSort3:(NSMutableArray *)array {
    [self __quickSort3:array left:0 right:(int)array.count -1];
}

- (void)__quickSort3:(NSMutableArray *)array left:(int)left right:(int)right{
    //元素比較少時采用插入排序
    if (right - left <= 15) {
        [self insertionSort3:array left:left right:right];
        return;
    }

    //lt是小于V的最后一個元素索引，gt是大于V的第一個索引也就是說lt和gt是分水嶺
    int lt = left,gt = right + 1,i = left + 1;
    //快速排序第二個優(yōu)化 標定點取隨機數(shù)
    int randonNum = arc4random() % (right - left + 1) + left;
    [array exchangeObjectAtIndex:left withObjectAtIndex:randonNum];
    //定義標定點
    NSNumber *V = array[left];
    //當i小于gt時 就一直循環(huán)，當i >= gt證明所有元素考察結(jié)束了
    while (i < gt) {
        if (array[i] < V) {//小于V時將考察的元素放到lt的下一個位置
            [array exchangeObjectAtIndex:lt + 1 withObjectAtIndex:i];
            //繼續(xù)往后走
            i++;
            //維護lt索引
            lt++;
        }else if (array[i] > V){//當大于V時就要元素放置到大于V的部分
            [array exchangeObjectAtIndex:gt - 1 withObjectAtIndex:i];
            //維護gt索引
            gt--;
        }else {//這里就是等于V的部分 ，只需要讓i繼續(xù)往后走即可
            i++;
        }
    }
    //將基準點防止到它合適的位置
    [array exchangeObjectAtIndex:left withObjectAtIndex:lt];
    //繼續(xù)將小于V的
    [self __quickSort3:array left:left right:lt];
    //繼續(xù)大于V的部分
    [self __quickSort3:array left:gt right:right];
}

代碼都有詳細的注釋，我就不再詳細介紹了，下面我們老規(guī)矩還是放上測試結(jié)果吧，測試用例的代碼我就不放出來了，不然文章篇幅是在太長了，下面看下三個版本快速排序的對比：

多種排序耗時對比.png

這里大家可以觀察到，我將歸并排序和插入排序也測試了一番，當然你這里可以不用太關(guān)注，你可以觀察到三路快速排序?qū)τ谟写罅恐貜?fù)元素的數(shù)組進行排序時異常的快，怎么樣，是不是成就感爆棚。