知 識 點 / 超 人

數(shù)據(jù)結(jié)構(gòu)算法排序是比較枯燥的知識，學(xué)習(xí)一定要耐著性子看掀亥，不然很容易理解錯誤撩扒。本文比較適合自學(xué)和基礎(chǔ)較差的讀者學(xué)習(xí)，文字都比較白話簡單易于理解逛尚。
文章目錄:
1.冒泡排序
2.選擇排序
3.堆排序
4.快速排序
5.(插入排序)直接插入排序
6.(插入排序)希爾排序
7.歸并排序
8.基數(shù)排序

八大基本排序分別是：冒泡排序垄惧，選擇排序，堆排序黑低，快速排序赘艳，直接插入排序酌毡，希爾排序，歸并排序蕾管，基數(shù)排序

冒泡排序

冒泡排序的基本思想是枷踏，從頭到尾，相鄰的兩個元素進行比較掰曾，如果出現(xiàn)反序就交換旭蠕，否則就執(zhí)行下一次比較。
例：@[5,4,3,6,1]; 第一次拿出數(shù)組下坐標(biāo)0和1位置的數(shù)進行比較旷坦， 5 和 4進行比較掏熬，發(fā)現(xiàn)5大于4，則把5和4位置進行交換秒梅，交換后數(shù)組為@[4,5,3,6,1];旗芬，然后進行第二次比較拿出下坐標(biāo)1和2位置的數(shù)進行比較，5和3進行比較捆蜀，發(fā)現(xiàn)5大于3疮丛，則把5和3進行交換，交換后的數(shù)組為@[4,3,5,6,1];辆它，接著進行第三次比較拿出下坐標(biāo)2和3位置的數(shù)進行比較誊薄，5和6進行比較，發(fā)現(xiàn)5小于6锰茉，則不進行交換呢蔫，直接執(zhí)行下一次比較。

冒泡排序的代碼

/**
 冒泡排序

 @param array 需要進行排序的數(shù)據(jù)源
 @param isMax YES表示從大到小排序 NO表示從小到大排序
 @return 排序好的數(shù)組
 */
- (NSMutableArray *)bubbleSortWithDataSource:(NSMutableArray *)array isMaxToMin:(BOOL)isMax
{
    /* 標(biāo)記最外層循環(huán)的循環(huán)次數(shù) */
    NSUInteger count = 0;
    /* 標(biāo)記交換次數(shù) */
    NSUInteger exchangeCount = 0;
    
    NSMutableArray *changeArray = [array mutableCopy];
    /* 最外層的循環(huán)次數(shù)取決于數(shù)組的長度 */
    /* 冒泡排序中飒筑，最外層的每一次循環(huán)都能在未排列好的數(shù)（沒有找到自己在數(shù)組中準(zhǔn)確位置的數(shù)）中找到最大的那個數(shù) */
    /* 所以數(shù)組的長度就是最外層的循環(huán)次數(shù) */
    for (int i =0; i < changeArray.count; i++) {
        /* 最外層循環(huán)次數(shù)累加 */
        count ++;
        /* 標(biāo)記是否已無需排序片吊，當(dāng)某一次最外層（最外層是指 i 這一層）循環(huán)沒有產(chǎn)生任何一次交換時，則說明該數(shù)組已經(jīng)排序成功 */
        BOOL isFinish = YES;
        /* 數(shù)組的首數(shù)下坐標(biāo)是從0開始 */
        /* 最外層的每一次循環(huán)中协屡，最內(nèi)層都需要把數(shù)組中所有數(shù)據(jù)進行兩兩比較 */
        for (int j = 0; j < changeArray.count -1;j++) {
            /* 判斷是從大到小排序還是從小到大排序 */
            if (isMax) {
                /* 冒泡排序的核心是相鄰的兩個數(shù)據(jù)進行比較定鸟，所以比較的數(shù)一定是相鄰的 */
                if ([changeArray[j] intValue] < [changeArray[j+1] intValue]) {
                    /* 進行交換 */
                    [changeArray exchangeObjectAtIndex:j withObjectAtIndex:j+1];
                    /* 如果有產(chǎn)生交換，說明還未排序成功 */
                    isFinish = NO;
                    /* 交換次數(shù)累加 */
                    exchangeCount ++;
                }
            }else
            {
                /* 冒泡排序的核心是相鄰的兩個數(shù)據(jù)進行比較著瓶，所以比較的數(shù)一定是相鄰的 */
                if ([changeArray[j] intValue] > [changeArray[j+1] intValue]) {
                    /* 進行交換 */
                    [changeArray exchangeObjectAtIndex:j withObjectAtIndex:j+1];
                    /* 如果有產(chǎn)生交換联予，說明還未排序成功 */
                    isFinish = NO;
                    /* 交換次數(shù)累加 */
                    exchangeCount ++;
                }
            }
        }
        if (isFinish) {
            //結(jié)束最外層的循環(huán)
            break;
        }
    }
    NSLog(@"最外層循環(huán)次數(shù):%lu",count);
    NSLog(@"交換次數(shù):%lu",exchangeCount);
    return changeArray;
}

冒泡排序時間復(fù)雜度

冒泡排序中最好的情況是數(shù)組本身就是正序排列的，并不需要交換材原，例如：@[1,2,3,4,5]; 當(dāng)正序數(shù)組放入冒泡排序中的時候沸久，只會進行4次比較，分別是1和2余蟹，2和3卷胯，3和4，4和5威酒。比較完后發(fā)現(xiàn)沒有任何數(shù)需要交換窑睁，那么說明數(shù)組已經(jīng)排序正確挺峡，不要在進行最外層循環(huán)。當(dāng)正序數(shù)組中有N個數(shù)的時候担钮，那么只需要N-1次比較橱赠。 而正序數(shù)組在冒泡排序中的時間復(fù)雜度為O(n)，因為n-1中箫津，在n的基數(shù)很大的情況狭姨，比如n為1000時，1其實可以忽略不計苏遥。所以 冒泡排序中最短的時間復(fù)雜度為O(n)饼拍。
冒泡排序中最壞的情況是數(shù)組本身就是逆序排列的，需要每兩個數(shù)都進行交換田炭，例如：@[5,4,3,2,1];當(dāng)逆序數(shù)組放入冒泡排序中师抄，最外層的每一次循環(huán)都要進行n-1次比較，而逆序數(shù)組需要進行n次最外層循環(huán)才能正確排序教硫，最終比較次數(shù)為(n-1)n/2司澎，所以冒泡排序中最長的時間復(fù)雜度為(n2)，因為當(dāng)n基數(shù)很大時栋豫，(n-1)n/2 = (n2 - n)/2； n2與n谚殊、1/2的差距越大丧鸯，n與1/2可以忽略不計。

選擇排序

選擇排序的基本思想是嫩絮，從數(shù)組第一個下坐標(biāo)一直比較到最后一個下坐標(biāo)丛肢。每一次的外層循環(huán)都能確定一個下坐標(biāo)的數(shù)。
例如@[5剿干，4蜂怎，3，6置尔，1]; 第一次拿出數(shù)組下坐標(biāo)首位的數(shù)5杠步，用5與數(shù)組里其余的數(shù)兩兩進行比較，首先5于4比較榜轿，發(fā)現(xiàn)4比5小幽歼，那么就把4在數(shù)組的下坐標(biāo)記錄下來，然后用4去與數(shù)組后面的數(shù)進行比較谬盐，4與3比較甸私，發(fā)現(xiàn)3比4小，那么就把4在數(shù)組的下坐標(biāo)記錄下來飞傀，又用3與6比較皇型，發(fā)現(xiàn)3比6小诬烹，那么就進行下次比較保持記錄3的下坐標(biāo)。然后用3與1比較弃鸦，發(fā)現(xiàn)1比3小绞吁，那么就把1在數(shù)組的下坐標(biāo)記錄下來。當(dāng)次循環(huán)把最終下記錄的下坐標(biāo)數(shù)與當(dāng)前的循環(huán)次數(shù)所對應(yīng)的首坐標(biāo)進行交換寡键。

選擇排序的代碼

/**
 選擇排序
 
 @param array 選擇排序
 @param isMax YES表示從大到小排序 NO表示從小到大
 @return 選擇排序后的結(jié)果
 */
+ (NSMutableArray *)selectionSortWithDataSource:(NSMutableArray *)array isMaxToMin:(BOOL)isMax
{
    /* 標(biāo)記最外層循環(huán)的循環(huán)次數(shù) */
    NSUInteger count = 0;
    /* 標(biāo)記下坐標(biāo)交換次數(shù) */
    NSUInteger exchangeCount = 0;
    
    /* 選擇排序的最外層循環(huán)次數(shù)是固定的掀泳，取決于數(shù)組的長度 */
    /* 選擇排序是一個比較特殊的排序，它的時間復(fù)雜度是固定的O(n2) */
    for (int i = 0; i < array.count; i++) {
        //累加最外層執(zhí)行次數(shù)
        count ++;
        //創(chuàng)建一個新數(shù)組用于存放每次需要比較的數(shù)據(jù)
        NSMutableArray *newArray = [NSMutableArray new];
        //最外層每次都能正確排序出一個數(shù)的位置西轩，所以已經(jīng)排序好的位置不需要在加入比較
        //j = i +1的原因是员舵，排除拿出來比較的第一個數(shù)，減少計算次數(shù)
        for (int j = i+1; j < array.count ; j++) {
            [newArray addObject:array[j]];
        }
        //取出需要比較的數(shù)
        int a = [array[i] intValue];
        //minIndex用于記錄每輪比較的數(shù)據(jù)中最大數(shù)據(jù)的下坐標(biāo)
        int minIndex = i;
        //進行比較
        for (int m = 0; m < newArray.count; m++) {
            //從新的數(shù)據(jù)源中取出比較的數(shù)
            int b = [newArray[m] intValue];
            //判斷是從大到小排序還是從小到大
            if (isMax) {
                if (b > a) {
                    a = b;
                    //minIndex = i+m+1之所以 加1 是因為newArray中已經(jīng)排除了第一個比較的數(shù)藕畔，所以下坐標(biāo)相比于最外層array少了1
                    minIndex = i+m+1;
                    //累加交換次數(shù)
                    exchangeCount++;
                }
            }else
            {
                if (b < a) {
                    a = b;
                    minIndex = i+m+1;
                    //累加交換次數(shù)
                    exchangeCount++;
                }
            }
        }
        [array exchangeObjectAtIndex:i withObjectAtIndex:minIndex];
    }
    NSLog(@"選擇排序-最外層循環(huán)次數(shù):%lu",count);
    NSLog(@"選擇排序-交換次數(shù):%lu",exchangeCount);
    
    return array;
}

選擇排序的時間復(fù)雜度

選擇排序中是一個比較特殊的排序马僻，它的時間復(fù)雜度是固定的O(n2)。 當(dāng)數(shù)組是正序的時候注服，例如@[1,2,3,4,...,n]韭邓，第一次拿1與n-1個數(shù)進行比較，比較次數(shù)是n-1溶弟。只能確定下來1的位置是當(dāng)前最小的女淑，其他的無法確定。所以后續(xù)依然要逐步進行比較辜御。而當(dāng)數(shù)組是反序的時候也一樣鸭你。所以選擇排序他的時間復(fù)雜度是固定的O(n2)， (n-1)+(n-2)+(n-3)+1 = n *(n- 1) / 2 = (n2 - n)/2擒权。當(dāng)n基數(shù)越大 n 與 1/2 可以忽略不計袱巨。所以時間復(fù)雜度為O(n2)

(n2 - n)/2

堆排序

堆排序說明比較多，需要耐心看看碳抄。如果文字上表達得不是很清楚或者不明白愉老。最好結(jié)合代碼一起。代碼注釋非常詳細剖效。耐著性子完整看完哈嫉入。要說堆排序，還需要了解二叉樹璧尸，大家可以先看看我二叉樹的文章

堆排序排序過程說明

堆排序的基本思想是劝贸，將數(shù)組轉(zhuǎn)換為大頂堆或小頂堆二叉樹，取出二叉樹中的根(即最大最小值)逗宁。然后對剩余的元素遞歸重構(gòu)轉(zhuǎn)換為新的二叉樹映九。直到所有元素遞歸完畢。就能得到正確的排序

堆排序主要分為兩步驟：
1.首先把原數(shù)組重構(gòu)成為一個大頂堆或者小頂堆二叉樹(下面都按照大頂堆舉例說明)
2.把重構(gòu)后的二叉樹的根節(jié)點與數(shù)組最末尾的數(shù)進行交換瞎颗，這樣當(dāng)前重構(gòu)后的二叉樹中最大值就到了數(shù)組最末尾件甥。然后將當(dāng)前交換后的數(shù)組中除最末尾的元素以外的元素進行大頂堆的重構(gòu)捌议，在進行步驟2的操作進行遞歸，每次都要在上次交換后的數(shù)組上減少1的長度引有，來忽略交換后最末尾的最大值瓣颅，這樣每次遞歸就能找到當(dāng)前數(shù)組中的最大值。一直遞歸將剩下沒有進行重構(gòu)交換的元素全部重構(gòu)交換譬正，直到所有元素遞歸完成宫补。(可能表達得不是很清楚明了，建議結(jié)合下面舉例和代碼看曾我。)

根節(jié)點與數(shù)組最末尾的數(shù)進行交換

堆排序流程演示

如果重構(gòu)數(shù)組為一個大頂堆舉例:排序前原數(shù)組為 @"5",@"3",@"8",@"10",@"2",@"32"粉怕，那么它在堆中表示為

舉例:原數(shù)組堆

首先我們需要對原數(shù)組進行重構(gòu)崇决，重構(gòu)為一個符合條件大頂堆或小頂堆的新堆费坊。這里以大頂堆為例。數(shù)組中有6個元素殖氏，那么取第一次重構(gòu)時取出來進行重構(gòu)排序的元素是下坐標(biāo)為3的元素蛉谜。因為數(shù)組的一半稚晚，能保證前一半的數(shù)據(jù)中所有值都是父節(jié)點，都擁有子節(jié)點型诚。而后根據(jù)父節(jié)點去遞歸子節(jié)點客燕。

(數(shù)組下坐標(biāo)是從0開始的)
第一次對原始數(shù)據(jù)進行堆創(chuàng)建，發(fā)現(xiàn)下坐標(biāo)3對應(yīng)10狰贯，并且沒有子節(jié)點也搓。所以忽略，數(shù)組順序不變暮现。
第二次發(fā)現(xiàn)下坐標(biāo)2對應(yīng)8，擁有左子樹節(jié)點32.發(fā)現(xiàn)左子樹節(jié)點值32大于父節(jié)點值8楚昭，進行交換并修改遞歸父節(jié)點的下坐標(biāo)為其替換的左子樹節(jié)點5栖袋，然后進行遞歸，發(fā)現(xiàn)遞歸的節(jié)點沒有子樹抚太，直接結(jié)束

第二次后堆結(jié)構(gòu)

第三次后堆結(jié)構(gòu)

image.png

堆排序的代碼

#pragma mark - 選擇排序(堆排序)

/**
 將數(shù)組按照完全二叉樹方式進行重新構(gòu)造成一個新堆（構(gòu)造成一個標(biāo)準(zhǔn)的）
 
 @param array 源數(shù)組
 @param parent 當(dāng)前需要判斷的父節(jié)點(根據(jù)需要判斷的父節(jié)點，去判斷其左右樹是否滿足堆結(jié)構(gòu)带膀，不滿足就進行交換)
 @param length 數(shù)組的長度
 */
+ (void)HeapAdjust:(NSMutableArray *)array parent:(int)parent length:(int)length
{
    //根據(jù)父節(jié)點parent的位置去計算其左子樹在數(shù)組中的下坐標(biāo)
    //因為在二叉樹中志珍，必須有左子樹才會有右子樹。
    //如果沒有左子樹說明這個父節(jié)點是最下層的子樹垛叨，這種情況就可以不用再做判斷了
    /*
     為什么 2*parent+1 就是左子樹的下坐標(biāo)呢伦糯。 因為二叉樹是按照第一排顯示1個，第二排顯示2個嗽元，
     第三排顯示3個以此類推的方式顯示的敛纲。
     例如{@(3), @(8), @(15), @(31), @(25)}是一個典型的小根堆。
     堆中有兩個父結(jié)點剂癌，元素3和元素8(因為15沒有子樹所以不是父節(jié)點)淤翔。
     元素3在數(shù)組中以array[0]表示，它的左孩子結(jié)點是array[1]佩谷，右孩子結(jié)點是array[2]旁壮。
     元素8在數(shù)組中以array[1]表示，它的左孩子結(jié)點是array[3]谐檀，右孩子結(jié)點是array[4]抡谐，
     它的父結(jié)點是array[0]⊥┾可以看出麦撵，它們滿足以下規(guī)律：
     設(shè)當(dāng)前元素在數(shù)組中以array[i]表示，那么，
     (1) 它的左孩子結(jié)點是：array[2*i+1];
     (2) 它的右孩子結(jié)點是：array[2*i+2];
     (3) 它的父結(jié)點是：array[(i-1)/2];
     (4) array[i] <= array[2*i+1] 且 array[i] <= array[2i+2]厦坛。
     */
    int l_child = 2*parent + 1;//左子樹下坐標(biāo)
    int r_child = l_child + 1;//右子樹下坐標(biāo)
    
    /*
     判斷當(dāng)前計算出來的右子樹下標(biāo)有沒有超過數(shù)組的長度五垮，如果沒有超過說明該父節(jié)點擁有左右子樹。
     如果超過且該節(jié)點擁有左子樹節(jié)點則說明該節(jié)點是最下層的最后一個父節(jié)點杜秸，
     如果超過且沒有左子樹放仗，則說明該節(jié)點不是父節(jié)點且是數(shù)組最后一個元素。
     
     這里之所以用while進行判斷而不是if撬碟，因為判斷當(dāng)前節(jié)點后诞挨，還要繼續(xù)向當(dāng)前節(jié)點的子樹節(jié)點之下進行篩選判斷。所以用while
     */
    while (r_child < length) {
        //如果右子樹的值大于左子樹的值呢蛤，則選取右子樹的值來與父節(jié)點進行判斷
        if ([[array objectAtIndex:l_child] intValue] < [[array objectAtIndex:r_child] intValue]) {
            //當(dāng)右子樹的值大于父節(jié)點時惶傻，需要把右子樹的值與父節(jié)點進行交換
            if ([[array objectAtIndex:parent] intValue] < [[array objectAtIndex:r_child] intValue]) {
                //把右子樹的值與父節(jié)點進行交換
                [array exchangeObjectAtIndex:parent withObjectAtIndex:r_child];
            }
            //重新選取當(dāng)前已經(jīng)判斷過的父節(jié)點的右子樹當(dāng)做父節(jié)點,繼續(xù)向下遞歸篩選判斷
            parent = r_child;
        }else
        {
            //當(dāng)左子樹值大于右子樹值時，用左子樹與父節(jié)點進行判斷
            if ([[array objectAtIndex:parent] intValue] < [[array objectAtIndex:l_child] intValue]) {
                //當(dāng)左子樹值大于父節(jié)點是其障，把左子樹的值與父節(jié)點進行交換
                [array exchangeObjectAtIndex:parent withObjectAtIndex:l_child];
            }
            //重新選取當(dāng)前已經(jīng)判斷過的父節(jié)點的左子樹當(dāng)做父節(jié)點,繼續(xù)向下遞歸篩選判斷
            parent = l_child;
        }
        //重新選取左右子樹下坐標(biāo)
        l_child = 2 * parent + 1;
        r_child = l_child + 1;
    }
    
    //判斷左子樹是否存在银室，并判斷左子樹是否超過父節(jié)點
    //這里不進行遞歸是因為如果只有左子樹，則表明該左子樹為數(shù)組最后一個數(shù)励翼。不需要進行遞歸了
    if (l_child < length && [[array objectAtIndex:l_child] intValue] > [[array objectAtIndex:parent] intValue]) {
        [array exchangeObjectAtIndex:l_child withObjectAtIndex:parent];
    }
}


/**
 對數(shù)組進行堆排序方法

 @param array 需要進行排序的數(shù)組
 @param isFromMaxToMin 數(shù)組排序的方式蜈敢，為YES是表示數(shù)組從大到小排序，為NO則從小到大排序
 */
+ (void)heapSort:(NSMutableArray *)array isFromMaxToMin:(BOOL)isFromMaxToMin
{
    if (!array) {
        return;
    }
    if (array.count < 2) {
        return;
    }
    //firstIndex表示從哪一個下坐標(biāo)開始去進行節(jié)點排序
    //為什么是array.count/2汽抚，因為數(shù)組的一半抓狭，能保證前一半的數(shù)據(jù)中所有值都是父節(jié)點，都擁有子節(jié)點造烁。而后根據(jù)父節(jié)點去遞歸子節(jié)點
    int firstIndex = (int)(array.count/2);
    int arrayCount = (int)array.count;
    //1.首先將原數(shù)組排序為一個初始堆
    for (int i = firstIndex; i >= 0; i--) {
        [self HeapAdjust:array parent:i length:arrayCount];
    }
    NSLog(@"初始堆%@",array);
    while (arrayCount > 0) {
        //將根節(jié)點最大的值與數(shù)組最末尾的值進行交換
        [array exchangeObjectAtIndex:arrayCount -1 withObjectAtIndex:0];
        arrayCount--;
        [self HeapAdjust:array parent:0 length:arrayCount];
    }
    NSLog(@"堆排序結(jié)果%@",array);
if (isFromMaxToMin) {//如果是需要從大到小排序否过，將數(shù)組逆序
        array = [NSMutableArray arrayWithArray:[[array reverseObjectEnumerator] allObjects]];
    }
}

堆排序時間復(fù)雜度

下面是網(wǎng)上找的一段說明
假設(shè)高度為k，則從倒數(shù)第二層右邊的節(jié)點開始惭蟋，這一層的節(jié)點都要執(zhí)行子節(jié)點比較然后交換（如果順序是對的就不用交換）苗桂；倒數(shù)第三層呢，則會選擇其子節(jié)點進行比較和交換告组，如果沒交換就可以不用再執(zhí)行下去了煤伟。如果交換了，那么又要選擇一支子樹進行比較和交換
那么總的時間計算為：s = 2^( i - 1 ) * ( k - i )其中 i 表示第幾層惹谐，2^( i - 1) 表示該層上有多少個元素持偏，( k - i) 表示子樹上要比較的次數(shù)驼卖，如果在最差的條件下氨肌，就是比較次數(shù)后還要交換；因為這個是常數(shù)酌畜，所以提出來后可以忽略

S = 2^(k-2) * 1 + 2^{(k-3)*2.....+2*(k-2)+2}(0)*(k-1) ===> 因為葉子層不用交換怎囚，所以i從 k-1 開始到 1

這個等式求解，我想高中已經(jīng)會了：等式左右乘上2，然后和原來的等式相減恳守，就變成了：

S = 2^(k - 1) + 2^(k - 2) + 2^(k - 3) ..... + 2 - (k-1)

除最后一項外考婴，就是一個等比數(shù)列了，直接用求和公式：S = { a1[ 1- (q^n) ] } / (1-q S = 2^k -k -1催烘；又因為k為完全二叉樹的深度沥阱，所以 (2^k) <= n < (2^k -1 )，總之可以認(rèn)為：k = logn （實際計算得到應(yīng)該是 log(n+1) < k <= logn ）

綜上所述得到：S = n - longn -1伊群，所以時間復(fù)雜度為：O(n)
上面看著會有點不易理解考杉，但是說法上沒問題。簡單的就是舰始，堆排序第一步將原始數(shù)組轉(zhuǎn)為一個大頂堆二叉樹崇棠，所需要做的比較次數(shù)為(n - logn -1)次，當(dāng)n趨于無窮大時丸卷，logn與1可以忽略枕稀。所以時間復(fù)雜度為O(n)

而當(dāng)把原始數(shù)組轉(zhuǎn)為大頂堆后，以后每次遞歸將剩余未排序的數(shù)組進行新的大頂堆重構(gòu)谜嫉。就需要分別n-1次萎坷，n-2次，.....骄恶，1次食铐。這樣堆排序整個過程需要的時間復(fù)雜度為 n+(n-1)+(n-2)+...+1 = (n+1)n/2 = (n2+n)/2。當(dāng)n趨于無窮大時僧鲁，n與1/2可以忽略不急虐呻。所以堆排序的最終時間復(fù)雜度為O(n2)。
正序逆序的時間復(fù)雜度都一樣

快速排序

基本思想：在數(shù)組隨機選擇一個元素(一般以數(shù)組第一個元素開始)寞秃，當(dāng)做基準(zhǔn)數(shù)斟叼。用基準(zhǔn)數(shù)與數(shù)組其他元素進行比較。將數(shù)組中比基準(zhǔn)數(shù)大的放在右邊春寿，比基準(zhǔn)數(shù)小的放在左邊朗涩。然后把數(shù)組根據(jù)基準(zhǔn)數(shù)分成2個數(shù)組。稱之為基準(zhǔn)數(shù)左邊數(shù)組和基準(zhǔn)數(shù)右邊數(shù)組绑改。對左右數(shù)組遞歸重復(fù)上面的操作谢床。直到判斷的數(shù)組只有一個元素了，就表示排序已經(jīng)完成

快速排序流程演示

舉例：數(shù)組@[5,9,2,15,46,3,8]厘线。

原數(shù)組

下坐標(biāo)5與基準(zhǔn)數(shù)交換后

下坐標(biāo)1與基準(zhǔn)數(shù)交換后

下坐標(biāo)為2的元素與基準(zhǔn)數(shù)發(fā)生位置交換后

此時已經(jīng)對數(shù)組所有元素遍歷了一次砾脑。本輪基準(zhǔn)數(shù)的判斷已經(jīng)完成。接著根據(jù)基準(zhǔn)數(shù)5當(dāng)前所在位置把數(shù)組分為左右兩個數(shù)組艾杏。分別是左數(shù)組@[3韧衣，2]，右數(shù)組@[15,46,9,8]购桑。對左右數(shù)組重復(fù)上面的步驟畅铭。直到拆分出來的數(shù)組沒有元素了。就表示所有元素遍歷完成勃蜘，排序完成硕噩。

快速排序的代碼

#pragma mark - 快速排序

/**
 快速排序的調(diào)用方法

 @param array 原始數(shù)組
 @param isFromMaxToMin YES表示從大到小排序 NO表示從小到大排序
 */
+ (void)quickSort:(NSMutableArray *)array isFromMaxToMin:(BOOL)isFromMaxToMin
{
    [self quickSort:array LeftIndex:0 rightIndex:array.count-1];
    if (isFromMaxToMin) {
        array = [NSMutableArray arrayWithArray:[[array reverseObjectEnumerator] allObjects]];
    }
    NSLog(@"快速排序結(jié)果:%@",array);
}

/**
 快速排序的核心方法

 基本思想：在數(shù)組隨機選擇一個元素，當(dāng)做基準(zhǔn)數(shù)元旬。用基準(zhǔn)數(shù)與數(shù)組其他元素進行比較榴徐。將數(shù)組中比基準(zhǔn)數(shù)大的放在右邊，比基準(zhǔn)數(shù)小的放在左邊匀归。然后把數(shù)組根據(jù)基準(zhǔn)數(shù)分成2個數(shù)組坑资。稱之為基準(zhǔn)數(shù)左邊數(shù)組和基準(zhǔn)數(shù)右邊數(shù)組。對左右數(shù)組遞歸重復(fù)上面的操作穆端。直到判斷的數(shù)組只有一個元素了袱贮，就表示排序已經(jīng)完成
 
 @param array 需要排序的數(shù)組
 @param leftIndex 需要排序的數(shù)組最開始的數(shù)在原數(shù)組中的下坐標(biāo)
 @param rightIndex 需要排序的數(shù)組最末尾的數(shù)在原數(shù)組中的下坐標(biāo)
 */
+ (void)quickSort:(NSMutableArray *)array LeftIndex:(NSInteger)leftIndex rightIndex:(NSInteger)rightIndex
{
    if (rightIndex <= leftIndex) {//如果排序長度是1則忽略
        return;
    }
    
    //i表示排序開始時的基準(zhǔn)數(shù)在數(shù)組中的下坐標(biāo)
    NSInteger i = leftIndex;
    //j表示排序是從i到j(luò)結(jié)束。整個排序的長度為j-i体啰。是排序最右邊元素的下坐標(biāo)
    NSInteger j = rightIndex;
    //key是記錄比較基準(zhǔn)數(shù)的值
    NSInteger key = [[array objectAtIndex:i] integerValue];
    
    /*
     i < j 說明當(dāng)前基準(zhǔn)數(shù)的遞歸排序還未完成
     while內(nèi)部是根據(jù)基準(zhǔn)數(shù)先從右向左比較(這里的從右開始位置是根據(jù)j開始的)攒巍，如果發(fā)現(xiàn)了比基準(zhǔn)數(shù)小的數(shù)，則進行位置交換荒勇。
     然后又根據(jù)基準(zhǔn)數(shù)與i+1下坐標(biāo)開始柒莉，從左向右比較，如果發(fā)現(xiàn)了比基準(zhǔn)數(shù)大的數(shù)沽翔，則與當(dāng)前交換后的基準(zhǔn)數(shù)位置進行交換兢孝。
     接著根據(jù)基準(zhǔn)數(shù)與j-1下坐標(biāo)開始，從右向左比較仅偎，如果發(fā)現(xiàn)了比基準(zhǔn)數(shù)小的數(shù)跨蟹，則進行位置交換
     這樣一直遞歸。直到i >= j發(fā)生完成本次的遞歸橘沥。
     */
    while (i < j) {
        while (i < j && key <= [[array objectAtIndex:j] integerValue]) {
            ////當(dāng)j == i 則說明i已經(jīng)是i到j(luò)這段數(shù)組中最小的數(shù)窗轩。不需要交換。所以i < j
            //如果當(dāng)前j下坐標(biāo)表示的值大于等于基準(zhǔn)數(shù)座咆，那么就將j比較的下坐標(biāo)減1.讓基準(zhǔn)數(shù)從右往左依次比較痢艺，直到遇見比基準(zhǔn)數(shù)小的數(shù)
            j--;
        }
        if (j != i) {//當(dāng)j == i 則說明i已經(jīng)是i到j(luò)這段數(shù)組中最小的數(shù)。不需要交換
            [array exchangeObjectAtIndex:j withObjectAtIndex:i];
        }

        while (i < j && key >= [[array objectAtIndex:i] integerValue]) {
            //如果i+1下坐標(biāo)表示的值小于基準(zhǔn)數(shù)介陶，那么就將比較的下坐標(biāo)加1腹备，讓基準(zhǔn)數(shù)從左往右依次比較，直到遇見比基準(zhǔn)數(shù)大的值
            i++;
        }
        if (j != i) {//當(dāng)j == i 則說明j已經(jīng)是i+1到j(luò)這段數(shù)組中最大的數(shù)了斤蔓。不需要交換
            [array exchangeObjectAtIndex:j withObjectAtIndex:i];
        }
    }//完成一次基準(zhǔn)數(shù)的判斷排序
    
    //根據(jù)當(dāng)下基準(zhǔn)數(shù)的下坐標(biāo)把數(shù)組分為左右兩部分進行左右兩部分的分別遞歸排序
    
    //基準(zhǔn)數(shù)右邊部分
    [self quickSort:array LeftIndex:i+1 rightIndex:rightIndex];
    //基準(zhǔn)數(shù)左邊部分
    [self quickSort:array LeftIndex:leftIndex rightIndex:i-1];
    
}

快速排序的時間復(fù)雜度

平均為O(nlogn)植酥，最好為O(nlogn)，最差為O(logn2)

(插入排序)直接插入排序

基本思路：每輪排序把數(shù)組分為2部分弦牡，一部分為已排序好的數(shù)組友驮，一部分為還未排序好的數(shù)組。每次取出還未排序好的數(shù)組中首元素與已排序好的數(shù)組從右往左比較驾锰。如果發(fā)現(xiàn)從未排序中取出的元素比從已排序中取出的元素大卸留，就把該未排序的元素插入到從已排序中取出元素的后面。這樣每一輪就能確定一個未排序元素在已排序數(shù)組中的準(zhǔn)確位置

直接插入排序的流程演示

流程舉例: 紅色的為已排序部分椭豫，藍色的為未排序部分
首先把原數(shù)組從下坐標(biāo)1開始拆分為2部分耻瑟， 已排序部分(紅色)旨指，未排序部分(藍色)。默認(rèn)原數(shù)組首元素為已排序元素喳整。

原數(shù)組

接著用后面未排序部分的第一個元素與已排序部分的最后一個元素進行比較谆构，這里發(fā)現(xiàn)已排序最末尾元素5小于未排序元素第一個元素9.且元素5余元素9的位置是相鄰的。不發(fā)生插入框都。把元素9列入已排序數(shù)組中搬素。此時已排序好的元素多了一個。

第一輪排序結(jié)束后結(jié)果

第二輪排序結(jié)束后結(jié)果

第三輪排序結(jié)束后結(jié)果

第四輪排序，用后面未排序部分的第一個元素與已排序部分的最后一個元素進行比較兵扬，這里發(fā)現(xiàn)已排序最末尾元素15小于未排序元素第一個元素46麻裳。且兩個元素相鄰。不發(fā)生插入器钟，把元素46加入已排序部分津坑。

第四輪排序結(jié)束后結(jié)果

最終結(jié)果

直接插入排序的代碼

#pragma mark - (插入排序)直接插入排序

/**
 直接插入排序

 基本思想：每輪排序把數(shù)組分為2部分疆瑰，一部分為已排序好的數(shù)組，一部分為還未排序好的數(shù)組昙啄。每次取出還未排序好的數(shù)組中首元素與已排序好的數(shù)組從右往左比較穆役。如果發(fā)現(xiàn)從未排序中取出的元素比從已排序中取出的元素大，就把該未排序的元素插入到從已排序中取出元素的后面梳凛。這樣每一輪就能確定一個未排序元素在已排序數(shù)組中的準(zhǔn)確位置
 
 @param array 原數(shù)組
 @param isFromMaxToMin YES表示從大到小排序 NO表示從小到大
 */
+ (void)insertSort:(NSMutableArray *)array isFromMaxToMin:(BOOL)isFromMaxToMin
{
    //i從1開始耿币，因為第一次插入排序操作時，假設(shè)的是數(shù)組第一個元素所組成的是一個有序數(shù)組韧拒。所以需要用后面無序數(shù)組的元素與第一個元素進行插入比較
    for (int i = 1; i <= array.count-1; i++) {
        //Temp_i是當(dāng)前未排序數(shù)組的首個元素淹接，需要用該元素與已排序數(shù)組中的所有元素比較
        NSInteger Temp_i = [[array objectAtIndex:i] integerValue];
        //j是已排序數(shù)組的最末尾(即最右邊十性，從右往左比較)的元素下坐標(biāo)
        NSInteger j = i - 1;
        //j必須大于0 否則數(shù)組越界，當(dāng)j=0的時候說明Temp_i已經(jīng)與已排序數(shù)組所有元素進行比較
        while (j >= 0) {
            //從已排序數(shù)組中取出的元素
            NSInteger Temp_j = [[array objectAtIndex:j] integerValue];

            //當(dāng)已排序數(shù)組中元素比未排序數(shù)組元素小時塑悼，說明需要把未排序元素插入到該已排序元素的后面劲适。
            if (Temp_i > Temp_j) {
                //當(dāng)j == (1-1)時，說明已排序最末尾元素與未排序最前面元素排序時正常的拢肆。
                //這種情況下不需要交換位置，直接退出while循環(huán)
                if ( j == (i - 1)) {
                    j = -1;
                }else
                {
                    //進行插入操作靖诗。先把元素從數(shù)組中移除郭怪，再把元素插入到已排序元素的后面位置
                    [array removeObjectAtIndex:i];
                    [array insertObject:[NSString stringWithFormat:@"%zd",Temp_i] atIndex:j+1];
                }
            }else
            {//當(dāng)已排序數(shù)組中元素比未排序數(shù)組元素大時則忽略本次，讓該未排序元素與下一個已排序元素進行比較刊橘。直到j(luò)=0或發(fā)現(xiàn)比未排序元素小的元素
                
                //等j==0時鄙才，說明該未排序元素與已排序數(shù)組所有元素都進行比較了，且改未排序元素小于所有已排序元素
                //那么就應(yīng)該把該元素插入到已排序數(shù)組的最前面促绵。
                if (j == 0) {
                    //進行插入操作攒庵。先把元素從數(shù)組中移除，再把元素插入到已排序元素的后面位置
                    [array removeObjectAtIndex:i];
                    [array insertObject:[NSString stringWithFormat:@"%zd",Temp_i] atIndex:0];
                }
                j--;
            }
        }
    }
    
    if (isFromMaxToMin) {
        array = [NSMutableArray arrayWithArray:[[array reverseObjectEnumerator] allObjects]];
    }
    NSLog(@"直接插入排序結(jié)果:%@",array);
}

插入排序時間復(fù)雜度

最優(yōu)情況：當(dāng)數(shù)組本身就是正序時败晴，每一輪排序都只是已排序末尾元素與未排序首位元素進行一次比較后就進行下一輪排序浓冒。一共n-1輪排序。當(dāng)n趨于無窮大時尖坤，1可以忽略稳懒。所以插入排序最優(yōu)情況的時間復(fù)雜度是O(n)

最差情況:最差就是逆序。每一輪都需要用未排序元素的首位與已排序的所有元素進行比較慢味。一共要進行n-1輪排序场梆，每次排序從1到n-1，所以插入排序的最壞情況的時間復(fù)雜度為O(n2)

(插入排序)希爾排序

基本思想:希爾排序相當(dāng)于直接插入排序的加強版纯路，在直接插入排序的概念之上加入了增量這個概念或油。什么是增量？插入排序只能與相鄰的元素進行比較驰唬，而希爾排序則是進行跳躍比較顶岸，而增量就是跳躍的間隔數(shù)。所謂增量即是把數(shù)組按照一定間隔數(shù)分組成不同的數(shù)組叫编。例如:@{1,2,3,4,5,6},一共有6個元素蜕琴，假設(shè)把數(shù)組按照增量3進行分組呜叫，那么就是@{1,4},@{2,5},@{3,6}各分為一組搬瑰。因為增量是3啰劲，所以每間隔3個下坐標(biāo)為一組幔戏。直到取到數(shù)組末尾响迂，如果數(shù)組還有第7個元素7，那么按照增量分組的第一組數(shù)據(jù)是@{1,4,7}晤锹。按照增量分組后驼唱，把每一組的元素按照插入排序進行排序。當(dāng)按照一個增量分組完成并每組數(shù)據(jù)按照插入排序完成后凸郑，將增量設(shè)為原本的二分之一裳食，然后重復(fù)上面的步驟進行插入排序。直到增量為1芙沥，按照增量為1的最后一次進行分組插入排序诲祸。即完成了排序。

希爾排序的流程演示

繪圖舉例說明（這里為了更加詳細的說明流程而昨，步驟比較多救氯，大家耐心看）:
例：@{11,10,9,8,5,6,7,4,3,2,1}

原數(shù)組

分組后

排序結(jié)果

分組后

排序結(jié)果

分組后

最終結(jié)果

希爾排序代碼

#pragma mark - (插入排序)希爾排序

/**
 希爾排序
 
 基本思想:希爾排序相當(dāng)于直接插入排序的加強版，在直接插入排序的概念之上加入了增量這個概念粱栖。
 什么是增量话浇？插入排序只能與相鄰的元素進行比較，而希爾排序則是進行跳躍比較查排，而增量就是跳躍的間隔數(shù)凳枝。
 所謂增量即是把數(shù)組按照一定間隔數(shù)分組成不同的數(shù)組抄沮。例如:@{1,2,3,4,5,6},一共有6個元素跋核，假設(shè)把數(shù)組按照增量3進行分組，
 那么就是@{1,4},@{2,5},@{3,6}各分為一組叛买。因為增量是3砂代，所以每間隔3個下坐標(biāo)為一組。
 直到取到數(shù)組末尾率挣，如果數(shù)組還有第7個元素7刻伊，那么按照增量分組的第一組數(shù)據(jù)是@{1,4,7}。
 按照增量分組后椒功，把每一組的元素按照插入排序進行排序捶箱。
 當(dāng)按照一個增量分組完成并每組數(shù)據(jù)按照插入排序完成后，將增量設(shè)為原本的二分之一动漾，然后重復(fù)上面的步驟進行插入排序丁屎。
 直到增量為1，按照增量為1的最后一次進行分組插入排序旱眯。即完成了排序晨川。

 @param array 原數(shù)組
 @param isFromMaxToMin YES表示從大到小排序 NO表示從小到大
 */
+ (void)shellSort:(NSMutableArray *)array isFromMaxToMin:(BOOL)isFromMaxToMin
{
    // l 是增量大小 標(biāo)記當(dāng)前數(shù)組是按照l長度間隔分段數(shù)據(jù)的
    //例如：@{@"1",@"23",@"12",@"45",@"5",@"18",@"9"} 當(dāng)l = 2
    //@"1",@"45",@"9"為一組。@"23","5",為一組删豺。@"12",@"18"為一組共虑。每間隔l個數(shù)取出元素組成一個新數(shù)組
    NSInteger l = array.count/2;
    //標(biāo)記按照l增量大小分段數(shù)組，indexCount表示數(shù)組被分為幾組
    NSInteger indexCount = array.count%2 > 0 ? array.count/2+1 : array.count/2;
    while (l >= 1) {
        //根據(jù)indexCount呀页，對每組里包含的元素進行比較
        for (int i = 0; i < indexCount; i++) {
            //進行直接插入排序妈拌，默認(rèn)比較數(shù)組第一個元素為已排序，所以從i+l開始蓬蝶，i表示當(dāng)前數(shù)組第一個元素供炎，i+l表示當(dāng)前數(shù)組第二個元素
            for (NSInteger j = i+l; j < array.count; j += l) {
                //標(biāo)記當(dāng)前比較元素的下坐標(biāo)
                NSInteger index_j = j;
                //用當(dāng)前j元素與前面已排序的所有元素進行比較渴逻，不能越界所以數(shù)組的下坐標(biāo)比大于0
                if (j-l >= 0) {
                    //temp_i是記錄當(dāng)前未排序元素的前一個元素(即已排序元素中最末尾一個元素)
                    NSInteger temp_i = [[array objectAtIndex:j-l] integerValue];
                    //temp_j是記錄當(dāng)前需要比較的未排序元素
                    NSInteger temp_j = [[array objectAtIndex:j] integerValue];
                    //當(dāng)已排序數(shù)組最末尾元素大于未排序元素時，需要用未排序元素與已排序元素的下一個元素進行比較
                    //如果已排序數(shù)組最末尾元素小于未排序元素時音诫，則直接進行下一個未排序元素的比較
                    if (temp_i > temp_j) {
                        //交換位置
                        [array exchangeObjectAtIndex:j withObjectAtIndex:j-l];
                        //重新記錄當(dāng)前需要比較的未排序元素的下坐標(biāo)
                        index_j = j-l;
                        //x 是記錄的是已排序元素的下一個元素下坐標(biāo)
                        NSInteger x = j-l-l;
                        //數(shù)組下坐標(biāo)不能越界惨奕，所以x>0
                        while (x >= 0) {
                            //temp_x記錄的下一個需要比較的已排序元素
                            NSInteger temp_x = [[array objectAtIndex:x] integerValue];
                            //只要發(fā)生已排序元素大于未排序元素就進行交換
                            if (temp_x > temp_j) {
                                [array exchangeObjectAtIndex:x withObjectAtIndex:index_j];
                                //重新記錄未排序元素在數(shù)組的下坐標(biāo)
                                index_j = x;
                                //讓x進行下一個元素的比較
                                x -= l;
                            }else
                            {
                                //如果發(fā)現(xiàn)已排序元素小于未排序元素，則說明未排序元素已經(jīng)找到在已排序數(shù)組中的位置竭钝。
                                //則使x=-1.跳出while循環(huán)
                                x = -1;
                            }
                        }
                    }
                }
            }
        }
        //重新計算下一次的組數(shù)
        indexCount = l%2 > 0 ? l/2+1 : l/2;
        //每次增量的比較計算完畢后梨撞，對增量繼續(xù)除以2
        l = l/2;
    }
    if (isFromMaxToMin) {
        array = [NSMutableArray arrayWithArray:[[array reverseObjectEnumerator] allObjects]];
    }
    NSLog(@"希爾排序結(jié)果:%@",array);
}

希爾排序時間復(fù)雜度

希爾排序的時間復(fù)雜度與增量的選取有關(guān)。例如香罐，當(dāng)增量為1時卧波，希爾排序退化成了直接插入排序，此時的時間復(fù)雜度為O(N2)庇茫，而Hibbard增量的希爾排序的時間復(fù)雜度為O(N3/2)港粱。

歸并排序

歸并排序的基本思想:歸并排序的遞歸方式就類似與一個完全二叉樹。把數(shù)組每次分成左右兩組旦签，然后左右兩組遞歸分組操作查坪，左右兩組分別又再一次分為左右兩組。直到子樹只有一個數(shù)為止宁炫。然后把子樹從下向上進行比較偿曙，先從最底層只有一個數(shù)的子樹進行左右比較。如果發(fā)現(xiàn)順序不對就交換羔巢。交換后又對子樹的父節(jié)點層左右子樹進行比較望忆。此時的比較方式與只有一個數(shù)的子樹不一樣。因為現(xiàn)在比較的左右子樹都是數(shù)組竿秆。首先需要先創(chuàng)建一個新數(shù)組启摄，這個新數(shù)組是用于保存2個數(shù)組比較排序后的正確順序，需要先用左右數(shù)組首個數(shù)比較找到左右兩組中最小的元素并把最小元素加入新數(shù)組中幽钢，然后用另一個較大的元素與較小元素的其他數(shù)進行比較歉备，直到找到下一個較小的元素加入新數(shù)組中，這樣重復(fù)比較搅吁，直到比較到一個數(shù)組中所有元素比較完成后威创，把另一個數(shù)組剩余的數(shù)按照順序加入到新數(shù)組中，此時新數(shù)組中就包含了2個比較數(shù)組的所有元素谎懦。把新數(shù)組與比較的左右數(shù)組在原數(shù)組中的位置元素進行替換肚豺。這樣重復(fù)操作。直到?jīng)]有上層了界拦。此時數(shù)組就完成了排序吸申。

歸并排序流程演示

歸并排序的分組流程借用大佬的一張圖:

分組流程

看了上面的分組圖，那么最后是如何把@{4,5,7,8}與@{1,2,3,6}正確排序成@{1,2,3,4,5,6,7,8}的呢。

待排序的左右數(shù)組

首先我們?nèi)〕鲎笥覕?shù)組的首個元素截碴，因為左右數(shù)組時已排序好的數(shù)組梳侨。所有左右數(shù)組的首個元素必然有一個是整個數(shù)組中最小的。我們發(fā)現(xiàn)左邊首位元素4大于右邊首位元素1日丹，所以我們把元素1加入到新數(shù)組中

在新數(shù)組中插入當(dāng)前排序數(shù)組中最小的元素

加入元素2

依然用左邊首位元素4與右邊下一個元素比較哲虾，發(fā)現(xiàn)左邊元素4大于右邊元素3丙躏，所以把元素3加入到新數(shù)組中

加入元素3

加入元素4

加入元素5

加入元素6

最終結(jié)果

歸并排序代碼

#pragma mark - 歸并排序

/**
 歸并排序外部調(diào)用方法
 
 基本思想:歸并排序的遞歸方式就類似與一個完全二叉樹扒寄。把數(shù)組每次分成左右兩組鱼鼓，然后左右兩組遞歸分組操作，左右兩組分別又再一次分為左右兩組旗们。直到子樹只有一個數(shù)為止蚓哩。然后把子樹從下向上進行比較构灸，先從最底層只有一個數(shù)的子樹進行左右比較上渴。如果發(fā)現(xiàn)順序不對就交換。交換后又對子樹的父節(jié)點層左右子樹進行比較喜颁。此時的比較方式與只有一個數(shù)的子樹不一樣稠氮。因為現(xiàn)在比較的左右子樹都是數(shù)組。首先需要先創(chuàng)建一個新數(shù)組半开，這個新數(shù)組是用于保存2個數(shù)組比較排序后的正確順序隔披，需要先用左右數(shù)組首個數(shù)比較找到左右兩組中最小的元素并把最小元素加入新數(shù)組中，然后用另一個較大的元素與較小元素的其他數(shù)進行比較寂拆，直到找到下一個較小的元素加入新數(shù)組中奢米，這樣重復(fù)比較，直到比較到一個數(shù)組中所有元素比較完成后纠永，把另一個數(shù)組剩余的數(shù)按照順序加入到新數(shù)組中鬓长，此時新數(shù)組中就包含了2個比較數(shù)組的所有元素。把新數(shù)組與比較的左右數(shù)組在原數(shù)組中的位置元素進行替換尝江。這樣重復(fù)操作涉波。直到?jīng)]有上層了。此時數(shù)組就完成了排序。

 @param array 原始需要排序的數(shù)組
 @param isFromMaxToMin YES表示排序后的數(shù)組時從大到小的
 */
+ (void)mergeSort:(NSMutableArray *)array isFromMaxToMin:(BOOL)isFromMaxToMin
{
    //忽略操作
    if (!array || array.count < 2) {
        return ;
    }
    //進行歸并排序
    [self mergeSort:array leftIndex:0 rightIndex:array.count-1];
    //判斷是否從大到小輸出
    if (isFromMaxToMin) {
        array = [NSMutableArray arrayWithArray:[[array reverseObjectEnumerator] allObjects]];
    }
    NSLog(@"歸并排序結(jié)果:%@",array);
}

/**
 歸并排序之左右分組遞歸方法

 @param array 原始數(shù)組
 @param left 需要分組的數(shù)據(jù)最左邊下坐標(biāo)
 @param right 需要分組的數(shù)據(jù)最右邊下坐標(biāo)
 */
+ (void)mergeSort:(NSMutableArray *)array leftIndex:(NSInteger)left rightIndex:(NSInteger)right
{
    //如果left下坐標(biāo)不小于right下坐標(biāo)啤覆。說明已經(jīng)是最底層子樹苍日。只有左右子樹只有1個元素了。不需要在分組
    if (left < right) {
        //mind是把數(shù)組左右分組后窗声，右邊數(shù)組第一個元素的下坐標(biāo)相恃。如果數(shù)組長度是單數(shù)，則把最中間的數(shù)放在右邊數(shù)組中
        NSInteger mind = (left+right)%2 > 0 ? (left+right)/2+1 : (left+right)/2;
        //循環(huán)遞歸分組
        [self mergeSort:array leftIndex:left rightIndex:mind-1];
        [self mergeSort:array leftIndex:mind rightIndex:right];
        //分組完成后對數(shù)組進行比較排序
        [self merge:array leftIndex:left rightIndex:right MindIndex:mind];
    }
}

/**
 歸并排序的核心比較方法

 @param array 原數(shù)組
 @param left 比較的左邊數(shù)組的首位元素下坐標(biāo)
 @param right 比較的右邊數(shù)組的最末尾元素下坐標(biāo)
 @param mind 比較的右邊數(shù)組的首位元素下坐標(biāo)
 */
+ (void)merge:(NSMutableArray *)array leftIndex:(NSInteger)left rightIndex:(NSInteger)right MindIndex:(NSInteger)mind
{
    //left == mind 說明這是最下層子樹
    if (right == mind) {
        //最下層子樹笨觅，只需要比較后交換位置即可
        if ([[array objectAtIndex:left] integerValue] > [[array objectAtIndex:right] integerValue]) {
            [array exchangeObjectAtIndex:left withObjectAtIndex:right];
        }
    }else
    {
        //非最下層子樹豆茫，需要先創(chuàng)建一個新的數(shù)組，來保存正確排序的結(jié)果
        NSMutableArray *newArray = [NSMutableArray new];
        //臨時記錄原mind值,用作比較
        NSInteger mind_x = mind;
        //臨時記錄原left值,用作比較
        NSInteger left_x = left;
        //循環(huán)操作屋摇，直到左右兩個數(shù)組中有一方的所有元素都比較完成
        while (mind_x <= right && left_x < mind) {
            if ([[array objectAtIndex:left_x] integerValue] > [[array objectAtIndex:mind_x] integerValue]) {
                //如果左邊元素大于右邊元素那么就把小的元素加入新數(shù)組中
                [newArray addObject:[array objectAtIndex:mind_x]];
                //然后把mind_x加1揩魂，讓較大的左邊元素與下一個右邊元素進行比較
                mind_x++;
            }else
            {
                //如果左邊元素小于右邊元素那么就把小的元素加入新數(shù)組中
                [newArray addObject:[array objectAtIndex:left_x]];
                //然后把left_x加1，讓較大的右邊元素與下一個左邊元素進行比較
                left_x++;
            }
        }
        
        //如果左邊的元素沒有比較完炮温，那么把剩下的左邊元素依次加入到新數(shù)組中
        while (left_x < mind) {
            [newArray addObject:[array objectAtIndex:left_x]];
            left_x++;
        }
        //如果右邊的元素沒有比較完火脉，那么把剩下的右邊元素依次加入到新數(shù)組中
        while (mind_x <= right) {
            [newArray addObject:[array objectAtIndex:mind_x]];
            mind_x++;
        }
        //把排序好的正確數(shù)組與比較的左右數(shù)組在原始數(shù)組中對應(yīng)位置的元素進行替換
        NSRange range = NSMakeRange(left, (right-left)+1);
        NSIndexSet *indexSet = [NSIndexSet indexSetWithIndexesInRange:range];
        [array replaceObjectsAtIndexes:indexSet withObjects:newArray];
        
    }
}

歸并排序的時間復(fù)雜度

完全二叉樹的時間復(fù)雜度為O(nlogn)，所以歸并排序的時間復(fù)雜度為O(nlogn)柒啤。歸并排序是非常穩(wěn)定的排序倦挂，因為其利用了完全二叉樹的特性，所以歸并排序的最好担巩，最壞方援，平均時間復(fù)雜度均為O(nlogn)。

基數(shù)排序

基數(shù)排序基本思想:基數(shù)排序最核心思想就是入桶涛癌》赶罚基數(shù)排序主要的步驟有3步
1.找到元素組中最大的元素
2.根據(jù)1找到的元素，把原數(shù)組中所有元素按照最大元素補位拳话，例如：最大元素是1001先匪，而原數(shù)組中有一個元素為2，那么把2按照最大元素補位弃衍，就是把2的長度補到與最大元素長度一樣呀非，前面補0，2補位后就變成了0002镜盯。
3.創(chuàng)建桶岸裙，因為數(shù)字是從0-9的。一共10個桶速缆。把補位后的數(shù)組從個位降允，十位，百位...以此類推激涤。進行每一位的單獨排序拟糕，從桶0開始判呕，只要有比較的位數(shù)是0，就把元素放入桶0中送滞。個位比較完了就比較十位侠草，一直比較到最大位。最后數(shù)組就已經(jīng)成為一個有序數(shù)組了

基數(shù)排序流程演示

舉例數(shù)組:@{57,66,245,44,753,2345,6}

原數(shù)組

1.首先找到數(shù)組中最大的數(shù)犁嗅，發(fā)現(xiàn)是2345
2.根據(jù)最大元素2345對數(shù)組中所有元素進行補位

補位后結(jié)果

創(chuàng)建0-9的10個桶

首先比較個位边涕，根據(jù)比較順序入桶

個位比較后入桶結(jié)果

個位入桶后得到的新數(shù)組

十位比較后入桶結(jié)果

十位入桶后得到的新數(shù)組

百位比較后入桶結(jié)果

根據(jù)百位入桶后獲得的新數(shù)組順序

百位入桶后得到的新數(shù)組

千位比較厚入桶結(jié)果

最終得到的數(shù)組

基數(shù)排序代碼

#pragma mark - 基數(shù)排序

/**
 基數(shù)排序
 基本思想:基數(shù)排序最核心思想就是入桶〕杪欤基數(shù)排序主要的步驟有3步
    1.找到元素組中最大的元素
    2.根據(jù)1找到的元素式撼，把原數(shù)組中所有元素按照最大元素補位，例如：最大元素是1001求厕，而原數(shù)組中有一個元素為2著隆，那么把2按照最大元素補位，就是把2的長度補到與最大元素長度一樣呀癣，前面補0美浦，2補位后就變成了0002。
    3.創(chuàng)建桶项栏，因為數(shù)字是從0-9的浦辨。一共10個桶。把補位后的數(shù)組從個位沼沈，十位流酬，百位...以此類推。進行每一位的單獨排序庆冕，從桶0開始康吵，只要有比較的位數(shù)是0劈榨，就把元素放入桶0中访递。個位比較完了就比較十位，一直比較到最大位同辣。最后數(shù)組就已經(jīng)成為一個有序數(shù)組了

 @param array 原數(shù)組
 @param isFromMaxToMin YES表示從大到小排序
 */
+ (void)radixSort:(NSMutableArray *)array isFromMaxToMin:(BOOL)isFromMaxToMin
{
    //忽略操作
    if (!array || array.count < 2) {
        return ;
    }
    
    /* 進行基數(shù)排序 */
    
    //1.獲取數(shù)組中最大的元素
    NSString *maxNumber = [self getArrayInMaxNumber:array];
    //2.根據(jù)最大元素對數(shù)組進行補位
    [self complementWithArray:array maxNumber:maxNumber];
    //3.入桶比較排序
    array = [self radixSort:array maxNumber:maxNumber];
    
    /* 進行基數(shù)排序 */
    
    
    //判斷是否從大到小輸出
    if (isFromMaxToMin) {
        array = [NSMutableArray arrayWithArray:[[array reverseObjectEnumerator] allObjects]];
    }
    NSLog(@"基數(shù)排序結(jié)果:%@",array);
}
//從數(shù)組中獲取最大值
+ (NSString *)getArrayInMaxNumber:(NSMutableArray *)array
{
    NSString *maxNumber = @"0";
    for (NSString *number in array) {
        if ([maxNumber integerValue] < [number integerValue]) {
            maxNumber = [number copy];
        }
    }
    return maxNumber;
}

/**
 根據(jù)最大元素拷姿，對數(shù)組中所有元素進行補位

 @param array 需要補位的數(shù)組
 @param maxNumber 最大元素，用作補位的參照
 */
+ (void)complementWithArray:(NSMutableArray *)array maxNumber:(NSString *)maxNumber
{
    //我這里元素都是用的NSString旱函。所以補位采用該方法响巢。
    //如果元素是int等可以不用進行這種補位。在比較的時候判斷下長度,長度不夠直接補0比較即可
    for (NSInteger j = 0; j < array.count; j++) {
        NSString *number = [array objectAtIndex:j];
        if (number.length < maxNumber.length) {
            NSInteger len = maxNumber.length-number.length;
            NSString *str = @"";
            for (NSInteger i = 0; i < len; i++) {
                str = [str stringByAppendingString:@"0"];
            }
            array[j] = [NSString stringWithFormat:@"%@%@",str,number];
        }
    }
}

/**
 基數(shù)排序的核心防化服

 @param array 原數(shù)組
 @param maxNumber 原數(shù)組中最大的元素
 @return 返回一個排序完成的新數(shù)組
 */
+ (NSMutableArray *)radixSort:(NSMutableArray *)array maxNumber:(NSString *)maxNumber
{
    //copy一份原數(shù)組棒妨，arrayCopy后面主要是用來記錄重新排序后的最新數(shù)組
    NSMutableArray *arrayCopy = [array mutableCopy];
    //根據(jù)最大元素判斷需要比較多少位
    for (NSInteger i = 0; i < maxNumber.length; i++) {
        //創(chuàng)建裝桶的數(shù)組
        NSMutableArray *bucketArray = [NSMutableArray array];
        //0-9一共10個桶踪古，
        for (NSInteger j = 0; j < 10; j++) {
            //桶含长，當(dāng)前需要放入的元素根據(jù)j定
            NSMutableArray *bucket = [NSMutableArray array];
            //遍歷數(shù)組，找到相應(yīng)位數(shù)的元素是否該放入當(dāng)前桶
            for (NSInteger m = 0; m < arrayCopy.count; m++) {
                //取出數(shù)組每個元素
                NSString *number = [arrayCopy objectAtIndex:m];
                //取出需要比較的位所對應(yīng)的值
                NSInteger num = [[number substringWithRange:NSMakeRange(number.length-1-i, 1)] integerValue];
                //如果比較的位所對應(yīng)的值跟桶的值一樣伏穆，就把該元素加入對應(yīng)桶中
                if (num == j) {
                    [bucket addObject:number];
                }
            }
            //如果桶中有元素才把桶加入存放桶的數(shù)組
            if (bucket.count > 0) {
                //把桶加入數(shù)組
                [bucketArray addObject:bucket];
            }
        }
        //移除上一次記錄的值
        [arrayCopy removeAllObjects];
        //把根據(jù)桶排序好的數(shù)組放入arrayCopy中拘泞，直到每一位都比較完，那么數(shù)組已經(jīng)排序完成了
        for (NSMutableArray *obj in bucketArray) {
            for (NSString *str in obj) {
                [arrayCopy addObject:str];
            }
        }
    }
    return arrayCopy;
}

基數(shù)排序的時間復(fù)雜度

其時間復(fù)雜度為O (nlog(r)m)枕扫，其中r為所采取的基數(shù)陪腌，而m為堆數(shù)，在某些時候烟瞧，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法诗鸭。(摘取之百科)