關(guān)于算法的想法

由于面試可能需要手寫算法丧荐，網(wǎng)上搜羅了一些資料，整理了下算法的OC的實(shí)現(xiàn)代碼，雖然平時(shí)開發(fā)中一般用不到未斑，但是多積累一些技術(shù)知識(shí)，還是對(duì)以后發(fā)展大有裨益的

CSDN八大內(nèi)部排序算法介紹

github上搜集的幾大算法原理和實(shí)現(xiàn)代碼币绩，只有JavaScript蜡秽、Python、Go缆镣、Java的實(shí)現(xiàn)代碼

github上搜集的幾大算法時(shí)間復(fù)雜度和空間復(fù)雜度比較

iOS 開發(fā)中常用的排序（冒泡载城、選擇、快速费就、插入诉瓦、希爾、歸并力细、基數(shù)）算法 幾種常用算法OC實(shí)現(xiàn)(他的歸并排序好像寫的有點(diǎn)問題)

幾大算法文字理解和OC代碼實(shí)現(xiàn)

1. 冒泡排序算法(Bubble Sort)

相鄰元素進(jìn)行比較睬澡，按照升序或者降序，交換兩個(gè)相鄰元素的位置 是一種“穩(wěn)定排序算法”

1.1 網(wǎng)上文字理論

是一種簡(jiǎn)單直觀的排序算法眠蚂。它重復(fù)地走訪過要排序的數(shù)列煞聪，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來逝慧。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換昔脯，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端笛臣。
作為最簡(jiǎn)單的排序算法之一云稚，冒泡排序給我的感覺就像 Abandon 在單詞書里出現(xiàn)的感覺一樣，每次都在第一頁第一位沈堡，所以最熟悉静陈。冒泡排序還有一種優(yōu)化算法，就是立一個(gè) flag诞丽，當(dāng)在一趟序列遍歷中元素沒有發(fā)生交換鲸拥，則證明該序列已經(jīng)有序。但這種改進(jìn)對(duì)于提升性能來說并沒有什么太大作用僧免。

1.2 算法步驟

1. 比較相鄰的元素刑赶。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)懂衩。
2. 對(duì)每一對(duì)相鄰元素作同樣的工作撞叨，從開始第一對(duì)到結(jié)尾的最后一對(duì)金踪。這步做完后，最后的元素會(huì)是最大的數(shù)谒所。
3. 針對(duì)所有的元素重復(fù)以上的步驟热康，除了最后一個(gè)。
4. 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟劣领，直到?jīng)]有任何一對(duì)數(shù)字需要比較姐军。

1.3 動(dòng)圖演示

bubbleSort.gif

1.4 什么時(shí)候最快

當(dāng)輸入的數(shù)據(jù)已經(jīng)是正序時(shí)。

1.5 什么時(shí)候最慢

當(dāng)輸入的數(shù)據(jù)是反序時(shí)尖淘。

1.6 冒泡排序代碼示例

- (void)bubbleSortWithArray:(NSMutableArray *)array {
    for (int i = 0; i < array.count - 1; i++) {
         //外層for循環(huán)控制循環(huán)次數(shù)
        for (int j = 0; j < array.count - 1 - i; j++) {
            //內(nèi)層for循環(huán)控制交換次數(shù)
            if ([array[j] integerValue] > [array[j + 1] integerValue]) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
            }
        }
    }
}

2. 快速排序算法(quick sort)

快速排序圖文理解奕锌，通過哨兵站崗理解快速排序

2.1 網(wǎng)上文字理解

快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下村生，排序 n 個(gè)項(xiàng)目要 Ο(nlogn) 次比較惊暴。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見趁桃。事實(shí)上辽话，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來卫病。

快速排序使用分治法（Divide and conquer）策略來把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）油啤。

快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來看蟀苛，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法益咬。

快速排序的名字起的是簡(jiǎn)單粗暴，因?yàn)橐宦牭竭@個(gè)名字你就知道它存在的意義帜平，就是快幽告，而且效率高！它是處理大數(shù)據(jù)最快的排序算法之一了裆甩。雖然 Worst Case 的時(shí)間復(fù)雜度達(dá)到了 O(n2)冗锁，但是人家就是優(yōu)秀，在大多數(shù)情況下都比平均時(shí)間復(fù)雜度為 O(n logn) 的排序算法表現(xiàn)要更好淑掌，可是這是為什么呢蒿讥，我也不知道。好在我的強(qiáng)迫癥又犯了抛腕，查了 N 多資料終于在《算法藝術(shù)與信息學(xué)競(jìng)賽》上找到了滿意的答案： 快速排序的最壞運(yùn)行情況是 O(n2)，比如說順序數(shù)列的快排媒殉。但它的平攤期望時(shí)間是 O(nlogn)担敌，且 O(nlogn) 記號(hào)中隱含的常數(shù)因子很小，比復(fù)雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多廷蓉。所以全封，對(duì)絕大多數(shù)順序性較弱的隨機(jī)數(shù)列而言马昙，快速排序總是優(yōu)于歸并排序。

2.2 算法步驟

1. 從數(shù)列中挑出一個(gè)元素刹悴，稱為 “基準(zhǔn)”（pivot）;
2. 重新排序數(shù)列行楞，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）土匀。在這個(gè)分區(qū)退出之后子房，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作就轧；
3. 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序证杭；

遞歸的最底部情形，是數(shù)列的大小是零或一妒御，也就是永遠(yuǎn)都已經(jīng)被排序好了解愤。雖然一直遞歸下去，但是這個(gè)算法總會(huì)退出乎莉，因?yàn)樵诿看蔚牡╥teration）中送讲，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

2.3 動(dòng)圖演示

quickSort.gif

2.4 快速排序代碼示例

- (void)quickSortArray:(NSMutableArray *)array
            leftIndex:(NSInteger)left
           rightIndex:(NSInteger)right {
   if (left > right) {
       return;
   }
   NSInteger i = left;
   NSInteger j = right;
   //記錄基準(zhǔn)數(shù) pivoty
   NSInteger key = [array[i] integerValue];
   while (i < j) {
       //首先從右邊j開始查找(從最右邊往左找)比基準(zhǔn)數(shù)(key)小的值<---
       while (i < j && key <= [array[j] integerValue]) {
           j--;
       }
       //如果從右邊j開始查找的值[array[j] integerValue]比基準(zhǔn)數(shù)小惋啃，則將查找的小值調(diào)換到i的位置
       if (i < j) {
           array[i] = array[j];
       }
       
       //從i的右邊往右查找到一個(gè)比基準(zhǔn)數(shù)小的值時(shí)哼鬓，就從i開始往后找比基準(zhǔn)數(shù)大的值 --->
       while (i < j && [array[i] integerValue] <= key) {
           i++;
       }
       //如果從i的右邊往右查找的值[array[i] integerValue]比基準(zhǔn)數(shù)大，則將查找的大值調(diào)換到j(luò)的位置
       if (i < j) {
           array[j] = array[i];
       }
   }
   //將基準(zhǔn)數(shù)放到正確的位置肥橙，----改變的是基準(zhǔn)值的位置(數(shù)組下標(biāo))---
   array[i] = @(key);
   //遞歸排序
   //將i左邊的數(shù)重新排序
   [self quickSortArray:array leftIndex:left rightIndex:i - 1];
   //將i右邊的數(shù)重新排序
   [self quickSortArray:array leftIndex:i + 1 rightIndex:right];
}

3. 選擇排序算法(select sort)

它的改進(jìn)(相比較冒泡算法)在于：先并不急于調(diào)換位置魄宏，先從A[0]開始逐個(gè)檢查，看哪個(gè)數(shù)最小就記下該數(shù)所在的位置P存筏，等一躺掃描完畢宠互，再把A[P]和A[0]對(duì)調(diào)，這時(shí)A[0]到A[n]中最小的數(shù)據(jù)就換到了最前面的位置椭坚。是一個(gè)“不穩(wěn)定排序算法”

它是一種簡(jiǎn)單直觀的排序算法予跌，無論什么數(shù)據(jù)進(jìn)去都是 O(n2) 的時(shí)間復(fù)雜度。所以用到它的時(shí)候善茎，數(shù)據(jù)規(guī)模越小越好券册。唯一的好處可能就是不占用額外的內(nèi)存空間。

選擇排序算法一： 直接選擇排序(straight select sort)

3.1 算法步驟

1. 首先在未排序序列中找到最写寡摹（大）元素烁焙，存放到排序序列的起始位置
2. 再從剩余未排序元素中繼續(xù)尋找最小（大）元素耕赘，然后放到已排序序列的末尾骄蝇。
3. 重復(fù)第二步，直到所有元素均排序完畢操骡。

3.2 動(dòng)圖演示

selectionSort.gif

3.3 直接選擇排序示例代碼

- (void)selectSortWithArray:(NSMutableArray *)array {
    for (int i = 0; i < array.count; i++) {
        for (int j = i + 1; j < array.count; j++) {
            if (array[i] > array[j]) {
                [array exchangeObjectAtIndex:i withObjectAtIndex:j];
            }
        }
    }
}

選擇排序算法二：堆排序(heap sort 涉及到完全二叉樹的概念)

參考了網(wǎng)上搜羅的java堆排序?qū)懛ê透拍罹呕穑?jì)算機(jī)語言通用赚窃，OC也能實(shí)現(xiàn)
堆排序理解(java例子)

網(wǎng)上文字理解

堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)岔激，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)勒极。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：

1. 大頂堆：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值虑鼎，在堆排序算法中用于升序排列辱匿；
2. 小頂堆：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于降序排列震叙；
   堆排序的平均時(shí)間復(fù)雜度為 Ο(nlogn)掀鹅。

算法步驟

1. 創(chuàng)建一個(gè)堆 H[0……n-1]；
2. 把堆首（最大值）和堆尾互換媒楼；
3. 把堆的尺寸縮小 1乐尊，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置划址；
4. 重復(fù)步驟 2扔嵌，直到堆的尺寸為 1夺颤。

動(dòng)圖演示

heapSort.gif

堆排序代碼示例

- (void)heapSortWithArray:(NSMutableArray *)array {
    //循環(huán)建立初始堆
    for (NSInteger i = array.count * 0.5; i >= 0; i--) {
        [self heapAdjustWithArray:array parentIndex:i length:array.count];
    }
    //進(jìn)行n-1次循環(huán)痢缎，完成排序
    for (NSInteger j = array.count - 1; j > 0; j--) {
        //最后一個(gè)元素和第一個(gè)元素進(jìn)行交換
        [array exchangeObjectAtIndex:j withObjectAtIndex:0];
        //篩選R[0]結(jié)點(diǎn)，得到i-1個(gè)結(jié)點(diǎn)的堆
        [self heapAdjustWithArray:array parentIndex:0 length:j];
        NSLog(@"第%ld趟:", array.count - j);
        [self printHeapSortResult:array begin:0 end:array.count - 1];
    }
}

- (void)heapAdjustWithArray:(NSMutableArray *)array
                parentIndex:(NSInteger)parentIndex
                     length:(NSInteger)length {
    NSInteger temp = [array[parentIndex] integerValue]; //temp保存當(dāng)前父結(jié)點(diǎn)
    NSInteger child = 2 * parentIndex + 1; //先獲得左孩子
    
    while (child < length) {
        //如果有右孩子結(jié)點(diǎn)世澜，并且右孩子結(jié)點(diǎn)的值大于左孩子結(jié)點(diǎn)独旷，則選取右孩子結(jié)點(diǎn)
        if (child + 1 < length && [array[child] integerValue] < [array[child + 1] integerValue]) {
            child++;
        }
        
        //如果父結(jié)點(diǎn)的值已經(jīng)大于孩子結(jié)點(diǎn)的值，則直接結(jié)束
        if (temp >= [array[child] integerValue]) {
            break;
        }
        
        //把孩子結(jié)點(diǎn)的值賦值給父結(jié)點(diǎn)
        array[parentIndex] = array[child];
        
        //選取孩子結(jié)點(diǎn)的左孩子結(jié)點(diǎn)寥裂，繼續(xù)向下篩選
        parentIndex = child;
        child = 2 * child + 1;
    }
    array[parentIndex] = @(temp);
}

- (void)printHeapSortResult:(NSMutableArray *)array
                      begin:(NSInteger)begin
                        end:(NSInteger)end {
    for (NSInteger i = 0; i < begin; i++) {

    }
    for (NSInteger i = begin; i <= end; i++) {
        
    }
    //打印堆排序
    NSLog(@"堆排序升序結(jié)果是--->%@",array);
}

4. 插入排序(insert sort)

4.1 網(wǎng)上文字理解

插入排序的代碼實(shí)現(xiàn)雖然沒有冒泡排序和選擇排序那么簡(jiǎn)單粗暴嵌洼，但它的原理應(yīng)該是最容易理解的了，因?yàn)橹灰蜻^撲克牌的人都應(yīng)該能夠秒懂封恰。插入排序是一種最簡(jiǎn)單直觀的排序算法麻养，它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)诺舔，在已排序序列中從后向前掃描鳖昌，找到相應(yīng)位置并插入。

插入排序和冒泡排序一樣低飒，也有一種優(yōu)化算法许昨，叫做拆半插入。

4.2 算法步驟

1. 將第一待排序序列第一個(gè)元素看做一個(gè)有序序列褥赊，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列车要。
2. 從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置崭倘。（如果待插入的元素與有序序列中的某個(gè)元素相等翼岁，則將待插入元素插入到相等元素的后面）

4.3 動(dòng)圖演示

insertionSort.gif

4.4 插入排序代碼示例

- (void)insertSortWithArray:(NSMutableArray *)array {
    NSInteger j;
    for (NSInteger i = 1; i < array.count; i++) {
        //取出每一個(gè)待插入的數(shù)據(jù)，從array[1]開始查找
        NSInteger temp = [array[i] integerValue];
        
        for (j = i - 1; j >= 0 && temp < [array[j] integerValue]; j--) {
            //如果之前的數(shù)比temp大司光，就將這個(gè)數(shù)往后移動(dòng)一個(gè)位置琅坡，留出空來讓temp插入，和整理撲克牌類似
            [array[j + 1]  integerValue] = [array[j] integerValue]];
            array[j] = [NSNumber numberWithInteger:temp];
        }
    }
}

歸并排序残家、希爾排序榆俺、基數(shù)排序、桶排序坞淮、計(jì)數(shù)排序幾個(gè)不常用的算法茴晋，算是高級(jí)算法吧，具體是不是菜鳥本人覺得還是只看得懂文字回窘，具體文字理論和實(shí)現(xiàn)原理還有待進(jìn)一步學(xué)習(xí)诺擅，網(wǎng)上搜羅了很多資料說，一般需要掌握幾種常用的算法冒泡啡直、快速烁涌、插入、選擇就夠了酒觅，我覺得技術(shù)還是多多益善撮执，當(dāng)然前提是最好掌握了，能夠手寫舷丹，并且能夠說出道理是最好的抒钱，不然都是臨時(shí)記憶，好吧颜凯，我目前理解的也是不夠深透谋币，還是網(wǎng)上記錄一些筆記，自己也好臨摹學(xué)習(xí)下装获，方便日后能消化這些計(jì)算機(jī)常用的算法

5. 歸并排序(merge sort)

5.1 網(wǎng)上文字理解

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法瑞信。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

作為一種典型的分而治之思想的算法應(yīng)用穴豫，歸并排序的實(shí)現(xiàn)由兩種方法：

• 自上而下的遞歸（所有遞歸的方法都可以用迭代重寫凡简，所以就有了第 2 種方法）；
• 自下而上的迭代精肃；

在《數(shù)據(jù)結(jié)構(gòu)與算法 JavaScript 描述》中秤涩，作者給出了自下而上的迭代方法。

和選擇排序一樣司抱，歸并排序的性能不受輸入數(shù)據(jù)的影響筐眷，但表現(xiàn)比選擇排序好的多，因?yàn)槭冀K都是 O(nlogn) 的時(shí)間復(fù)雜度习柠。代價(jià)是需要額外的內(nèi)存空間匀谣。

5.2 算法步驟

1. 申請(qǐng)空間照棋，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列武翎；
2. 設(shè)定兩個(gè)指針烈炭，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；
3. 比較兩個(gè)指針?biāo)赶虻脑乇Χ瘢x擇相對(duì)小的元素放入到合并空間符隙，并移動(dòng)指針到下一位置；
4. 重復(fù)步驟 3 直到某一指針達(dá)到序列尾垫毙；
5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾霹疫。

5.3 動(dòng)圖演示

mergeSort.gif

5.4 歸并排序代碼示例 參考簡(jiǎn)書作者OC代碼

//自頂向下的歸并排序
/**
 遞歸使用歸并排序,對(duì)array[left...right]的范圍進(jìn)行排序
 @param array 數(shù)組
 @param left 左邊界
 @param right 右邊界
 */
- (void)mergeSortWithArray:(NSMutableArray *)array
                      left:(NSInteger)left
                     right:(NSInteger)right {
    //判斷遞歸到底的情況
    if (left >= right) {
        //這時(shí)候只有一個(gè)元素或者是不存在的情況
        return;
    }
    //中間索引的位置
    NSInteger middle = (right + left) / 2;
    //對(duì) left --- middle 區(qū)間的元素進(jìn)行排序操作
    [self mergeSortWithArray:array left:left right:middle];
    //對(duì) middle + 1 ---- right 區(qū)間的元素進(jìn)行排序操作
    [self mergeSortWithArray:array left:middle + 1 right:right];
    //兩邊排序完成后進(jìn)行歸并操作
    [self mergeSortWithArray:array left:left middle:middle right:right];
}

/**
 對(duì) [left middle] 和 [middle + 1 right]這兩個(gè)區(qū)間歸并操作
 @param array 傳入的數(shù)組
 @param left 左邊界
 @param middle 中間位置
 @param right 右邊界
 */
- (void)mergeSortWithArray:(NSMutableArray *)array
                      left:(NSInteger)left
                    middle:(NSInteger)middle
                     right:(NSInteger)right {
    //拷貝一個(gè)數(shù)組出來
    NSMutableArray *copyArray = [NSMutableArray arrayWithCapacity:right - left + 1];
    for (NSInteger i = left; i <= right; i++) {
        //這里要注意有l(wèi)eft的偏移量，所以copyArray賦值的時(shí)候要減去left
        copyArray[i - left] = array[i];
    }
    
    NSInteger i = left, j = middle + 1;
    //循環(huán)從left開始到right區(qū)間內(nèi)給數(shù)組重新賦值综芥，注意賦值的時(shí)候也是從left開始的丽蝎，不要習(xí)慣寫成了從0開始，還有都是閉區(qū)間
    for (NSInteger k = left; k <= right; k++) {
        //當(dāng)左邊界超過中間點(diǎn)時(shí) 說明左半部分?jǐn)?shù)組越界了 直接取右邊部分的數(shù)組的第一個(gè)元素即可
        if (i > middle) {
            //給數(shù)組賦值 注意偏移量left 因?yàn)檫@里是從left開始的
            array[k] = copyArray[j - left];
            //索引++
            j++;
        } else if (j > right) {//當(dāng)j大于右邊的邊界時(shí)證明有半部分?jǐn)?shù)組越界了毫痕，直接取左半部分的第一個(gè)元素即可
            array[k] = copyArray[i - left];
            //索引++
            i++;
        } else if (copyArray[i - left] > copyArray[j - left]) {//左右兩半部分?jǐn)?shù)組比較
            //當(dāng)右半部分?jǐn)?shù)組的第一個(gè)元素要小時(shí) 給數(shù)組賦值為右半部分的第一個(gè)元素
            array[k] = copyArray[j - left];
            //右半部分索引加1
            j++;
        } else {//右半部分?jǐn)?shù)組首元素大于左半部分?jǐn)?shù)組首元素
            array[k] = copyArray[i - left];
            i++;
        }
    }
}

6. 希爾排序(shell sort)

6.1 網(wǎng)上文字理解

希爾排序征峦，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本消请。但希爾排序是非穩(wěn)定排序算法栏笆。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

• 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高臊泰，即可以達(dá)到線性排序的效率蛉加；
• 但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位缸逃；

希爾排序的基本思想是：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序针饥，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序需频。

6.2 算法步驟

1. 選擇一個(gè)增量序列 t1丁眼，t2，……昭殉，tk苞七，其中 ti > tj, tk = 1；
2. 按增量序列個(gè)數(shù) k挪丢，對(duì)序列進(jìn)行 k 趟排序蹂风；
3. 每趟排序，根據(jù)對(duì)應(yīng)的增量 ti乾蓬，將待排序列分割成若干長(zhǎng)度為 m 的子序列惠啄，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為 1 時(shí)，整個(gè)序列作為一個(gè)表來處理撵渡，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度融柬。

6.4 希爾排序代碼示例

- (void)shellAscendingOrderSort:(NSMutableArray *)ascendingArr {
    NSMutableArray *buckt = [self createBucket];
    NSNumber *maxnumber = [self listMaxItem:ascendingArr];
    NSInteger maxLength = numberLength(maxnumber);
    for (int digit = 1; digit <= maxLength; digit++) {
        // 入桶
        for (NSNumber *item in ascendingArr) {
            NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];
            NSMutableArray *mutArray = buckt[baseNumber];
            [mutArray addObject:item];
        }
        NSInteger index = 0;
        for (int i = 0; i < buckt.count; i++) {
            NSMutableArray *array = buckt[i];
            while (array.count != 0) {
                NSNumber *number = [array objectAtIndex:0];
                ascendingArr[index] = number;
                [array removeObjectAtIndex:0];
                index++;
            }
        }
    }
    NSLog(@"希爾升序排序結(jié)果：%@", ascendingArr);
}

- (NSMutableArray *)createBucket {
    NSMutableArray *bucket = [NSMutableArray array];
    for (int index = 0; index < 10; index++) {
        NSMutableArray *array = [NSMutableArray array];
        [bucket addObject:array];
    }
    return bucket;
}

- (NSNumber *)listMaxItem:(NSArray *)list {
    NSNumber *maxNumber = list[0];
    for (NSNumber *number in list) {
        if ([maxNumber integerValue] < [number integerValue]) {
            maxNumber = number;
        }
    }
    return maxNumber;
}

NSInteger numberLength(NSNumber *number) {
    NSString *string = [NSString stringWithFormat:@"%ld", (long)[number integerValue]];
    return string.length;
}

- (NSInteger)fetchBaseNumber:(NSNumber *)number digit:(NSInteger)digit {
    if (digit > 0 && digit <= numberLength(number)) {
        NSMutableArray *numbersArray = [NSMutableArray array];
        NSString *string = [NSString stringWithFormat:@"%ld", [number integerValue]];
        for (int index = 0; index < numberLength(number); index++) {
            [numbersArray addObject:[string substringWithRange:NSMakeRange(index, 1)]];
        }
        NSString *str = numbersArray[numbersArray.count - digit];
        return [str integerValue];
    }
    return 0;
}

7. 基數(shù)排序(radix sort)

7.1 文字理解

基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字姥闭，然后按每個(gè)位數(shù)分別比較丹鸿。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)棚品。

7.2 基數(shù)排序 vs 計(jì)數(shù)排序 vs 桶排序

基數(shù)排序有兩種方法：
這三種排序算法都利用了桶的概念，但對(duì)桶的使用方法上有明顯差異：

• 基數(shù)排序：根據(jù)鍵值的每位數(shù)字來分配桶廊敌；
• 計(jì)數(shù)排序：每個(gè)桶只存儲(chǔ)單一鍵值铜跑；
• 桶排序：每個(gè)桶存儲(chǔ)一定范圍的數(shù)值；

7.3 動(dòng)圖演示

radixSort.gif

7.4 基數(shù)排序代碼示例

- (void)radixAscendingOrderSort:(NSMutableArray *)ascendingArr {
    NSMutableArray *buckt = [self createBucket];
    NSNumber *maxnumber = [self listMaxItem:ascendingArr];
    NSInteger maxLength = numberLength(maxnumber);
    for (int digit = 1; digit <= maxLength; digit++) {
        // 入桶
        for (NSNumber *item in ascendingArr) {
            NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];
            NSMutableArray *mutArray = buckt[baseNumber];
            [mutArray addObject:item];
        }
        NSInteger index = 0;
        for (int i = 0; i < buckt.count; i++) {
            NSMutableArray *array = buckt[i];
            while (array.count != 0) {
                NSNumber *number = [array objectAtIndex:0];
                ascendingArr[index] = number;
                [array removeObjectAtIndex:0];
                index++;
            }
        }
    }
    NSLog(@"基數(shù)升序排序結(jié)果：%@", ascendingArr);
}

8. 計(jì)數(shù)排序(counting sort)

8.1 文字理解

計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中骡澈。作為一種線性時(shí)間復(fù)雜度的排序锅纺，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

8.2 動(dòng)圖演示

countingSort.gif

8.3 計(jì)數(shù)排序代碼示例（無）

9. 桶排序(bucket sort)

9.1 文字理解

桶排序是計(jì)數(shù)排序的升級(jí)版肋殴。它利用了函數(shù)的映射關(guān)系囤锉，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。為了使桶排序更加高效护锤，我們需要做到這兩點(diǎn)：

1. 在額外空間充足的情況下官地，盡量增大桶的數(shù)量
2. 使用的映射函數(shù)能夠?qū)⑤斎氲?N 個(gè)數(shù)據(jù)均勻的分配到 K 個(gè)桶中

同時(shí)，對(duì)于桶中元素的排序烙懦，選擇何種比較排序算法對(duì)于性能的影響至關(guān)重要驱入。

9.2 什么時(shí)候最快

當(dāng)輸入的數(shù)據(jù)可以均勻的分配到每一個(gè)桶中。

9.3 什么時(shí)候最慢

當(dāng)輸入的數(shù)據(jù)被分配到了同一個(gè)桶中氯析。

9.4 桶排序示例代碼（無）

如果要搞懂計(jì)算機(jī)算法亏较，建議還是多看書和資料，網(wǎng)上摘抄的都是別人總結(jié)的部分掩缓，代碼驗(yàn)證是沒有問題雪情，原理搞懂還需要實(shí)際去運(yùn)用，末尾給出很早的一個(gè)分享數(shù)據(jù)結(jié)構(gòu)與算法的云盤地址你辣，作者結(jié)合實(shí)際例子講解的很深動(dòng)

小甲魚大神講解數(shù)據(jù)結(jié)構(gòu)和算法

鏈接:https://pan.baidu.com/s/1ufZfdMcTbY4QNytUeWSBZw

密碼: 3ne3