??在計(jì)算機(jī)領(lǐng)域，算法是永恒的主題。

??在各位同學(xué)平時(shí)的工作中和面試中一定會(huì)涉及到很多算法方面的需求，算法是什么呢？

??算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問(wèn)題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制。也就是說(shuō)，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問(wèn)題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問(wèn)題。不同的算法可能用不同的時(shí)間、空間或效率來(lái)完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來(lái)衡量。

??接下來(lái)我們就常用的一些算法來(lái)做一些討論，文筆拙劣，若有不當(dāng)之處，還請(qǐng)各位看官多多指教！

??正文之中對(duì)一些博客的引用都給出了原文鏈接。侵刪！

排序相關(guān)算法

常用的排序算法有以下幾種：

1. 選擇排序
2. 插入排序
3. 冒泡排序
4. 希爾排序
5. 歸并排序
6. 快速排序
7. 堆排序
8. 計(jì)數(shù)排序
9. 桶排序
10. 基數(shù)排序

以下我們就上市的每種算法一一討論。

選擇排序

??首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。

OC實(shí)現(xiàn)
- (NSMutableArray *)selectionSortByArray:(NSMutableArray *)array{
    for (int index = 0; index < array.count - 1; index++) {
        int pos = index;
        for (int tmpIndex = index + 1; tmpIndex < array.count; tmpIndex++) {
            int posValue = [array[pos] intValue];
            int tmpIndexValue = [array[tmpIndex] intValue];
            if (posValue > tmpIndexValue) {
                pos = tmpIndex;
            }
        }
        
        //將index位置的元素和pos位置的元素互換
        int indexValue = [array[index] intValue];
        int posValue = [array[pos] intValue];
        
        indexValue = indexValue + posValue;
        posValue = indexValue - posValue;
        indexValue = indexValue - posValue;
        
        array[index] = [NSNumber numberWithInt:indexValue];
        array[pos] = [NSNumber numberWithInt:posValue];
    }
    return array;
}

image

??插入排序的時(shí)間復(fù)雜度最好情況下為O(n^{2),最壞情況下為O(n}2),平均時(shí)間復(fù)雜度為 O(n^2)

??空間復(fù)雜度為O(1)

插入排序

??從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)排好序，取下一個(gè)，在已經(jīng)排好序的序列中向前掃描，有元素大于這個(gè)新元素，將已經(jīng)在排好序中的元素移到下一個(gè)位置，依次執(zhí)行。

OC實(shí)現(xiàn)
- (NSMutableArray *)insertionSortByArray:(NSMutableArray *)array{
    for (int index = 1; index < array.count; index ++) {
        int tmpValue = [array[index] intValue];
        
        for (int tmpIndex = index - 1; tmpIndex >= 0 && [array[tmpIndex] intValue] > tmpValue ; tmpIndex --) {
            array[tmpIndex + 1] = array[tmpIndex];
            array[tmpIndex] = [NSNumber numberWithInt:tmpValue];
        }
    }
    return array;
}

image

??插入排序的時(shí)間復(fù)雜度最好情況下為O(n),最壞情況下為O(n^2),平均時(shí)間復(fù)雜度為 O(n^2)

??空間復(fù)雜度為O(1)

冒泡排序

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)
2. 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)
3. 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)
4. 重復(fù)步驟1~3，直到排序完成

OC實(shí)現(xiàn)
- (NSMutableArray *)bubbleSortByArray:(NSMutableArray <NSNumber *> *)array{
    for (int index = 0; index < array.count - 1; index ++) {
        for (int tmpIndex = 0; tmpIndex < array.count - 1; tmpIndex ++) {
            if ([array[tmpIndex] intValue] > [array[tmpIndex + 1] intValue]) {
                NSNumber * tmp = array[tmpIndex];
                array[tmpIndex] = array[tmpIndex + 1];
                array[tmpIndex + 1] = tmp;
            }
        }
    }
    return array;
}

image

??冒泡排序的時(shí)間復(fù)雜度最好情況下為O(n),最壞情況下為O(n^2),平均時(shí)間復(fù)雜度為 O(n^2)

??空間復(fù)雜度為O(1)

希爾排序

??希爾排序是先將整個(gè)待排序的記錄序列分割成為若干子序列，然后分別進(jìn)行直接插入排序。即希爾排序是插入排序的變種或優(yōu)化方案。
??希爾排序的思想是使數(shù)組中任意間隔為h的元素都是有序的，這樣的數(shù)組被稱為h有序數(shù)組，換言之，一個(gè)h有序數(shù)組就是h和互相獨(dú)立的有序數(shù)組編織在一起組成的一個(gè)數(shù)組。如下圖：

        h = 4
        L     E     E     A     M     H     L     E     P     S     O     L     T     S     X     R
        L--------------- M----------------p----------------T
               E----------------H---------------S----------------S
                      E----------------L----------------O----------------X
                              A----------------E----------------L-----------------R

OC實(shí)現(xiàn)
- (NSMutableArray *)shellSortByArray:(NSMutableArray *)array{
    int h = 1;
    
    //定義遞增序列
    while (h < array.count /2) {
        h = h * 2 + 1;
    }
    
    for (h ; h > 0; h = h/2) {
        for (int index  = h; index < array.count; index++) {
            NSNumber * tmp = array[index];
            for (int j = index - h; j >= 0 && [array[j] intValue] > tmp.intValue; j -= h) {
                array[j + h] = array[j];
                array[j] = tmp;
            }
        }
    }
    return array;
}

希爾排序過(guò)程

初始數(shù)組  ： 10, 4, 9, 6, 25, 33, 7, 8, 12, 1, 15, 20

第一趟，增量為7,結(jié)果數(shù)組中，每間隔 7-1 個(gè)元素的元素組成的數(shù)組是有序的

            8, 4, 1, 6, 20, 33, 7, 10, 12, 9, 15, 25  

第二趟，增量為3，結(jié)果數(shù)組中，每間隔 3-1 個(gè)元素的元素組成的數(shù)組是有序的
    
            6, 4, 1, 7, 10, 12, 8, 15, 25, 9, 20, 33

第三趟，增量為1，結(jié)果數(shù)組中，每間隔 1-1 個(gè)元素的元素組成的數(shù)組是有序的
    
            1, 4, 6, 7, 8, 9, 10, 12, 15, 20, 25, 33

??希爾排序的時(shí)間復(fù)雜度最好情況下為O(nlog^{2n),最壞情況下為O(n}2),平均時(shí)間復(fù)雜度為 O(nlogn)

??空間復(fù)雜度為O(1)

拓展

??希爾排序中如何選擇遞增序列呢？有沒(méi)有最優(yōu)的遞增序列？

??事實(shí)上，由于算法的性能不僅僅取決于h，還取決于h之間的數(shù)學(xué)性質(zhì)，比如他們的公因子等。就目前而言很多論文都研究了各不相同的序列，但都無(wú)法證明某一個(gè)序列是最優(yōu)的。但可以證明的是，復(fù)雜的序列在最壞的情況下對(duì)算法帶來(lái)的提升是要優(yōu)于我們所使用的簡(jiǎn)單遞增序列的。
?????????????????????????????《算法(第4版)》

歸并排序

??歸并排序的思想是，當(dāng)我們需要將一個(gè)數(shù)組進(jìn)行排序的時(shí)候，可以先(遞歸的)將它分成兩半分別排序，然后將結(jié)果歸并起來(lái)。

??即使一個(gè)數(shù)組變成若干個(gè)元素有序的數(shù)組，然后在將這些數(shù)組排序合并起來(lái)

??歸并排序優(yōu)勢(shì)在于它能夠保證將任意長(zhǎng)度為N的數(shù)組排序所需要的時(shí)間和NlogN成正比，而它的主要缺點(diǎn)則是它所需要的額外空間和N成正比。

??歸并排序是適用分治思想的典型案例

- (NSMutableArray *)mergeSortByArray:(NSMutableArray *)array{
    
    NSInteger len = array.count;
    if (len < 2) {
        return array;
    }
    
    NSInteger middle = len/2;
    NSMutableArray * leftArr = [NSMutableArray arrayWithArray:[array subarrayWithRange:NSMakeRange(0, middle)]];
    NSMutableArray * rightArr = [NSMutableArray arrayWithArray:[array subarrayWithRange:NSMakeRange(middle, array.count - middle)]];
    
    NSMutableArray * returnArr = [self mergeWithLeft:[self mergeSortByArray:leftArr] right:[self mergeSortByArray:rightArr]];
    return returnArr;
}

- (NSMutableArray *)mergeWithLeft:(NSMutableArray *)leftArr right:(NSMutableArray *)rightArr{
    
    NSMutableArray * auxArray = [NSMutableArray array];
    while (leftArr.count && rightArr.count ) {
        if ([leftArr[0] integerValue] <= [rightArr[0] integerValue]) {
            [auxArray addObject:leftArr.firstObject];
            [leftArr removeObjectAtIndex:0];
        }else{
            [auxArray addObject:rightArr.firstObject];
            [rightArr removeObjectAtIndex:0];
        }
    }
    
    while (leftArr.count) {
        [auxArray addObject:leftArr.firstObject];
        [leftArr removeObjectAtIndex:0];
    }
    while (rightArr.count) {
        [auxArray addObject:rightArr.firstObject];
        [rightArr removeObjectAtIndex:0];
    }
    
    return auxArray;
}

歸并排序的過(guò)程

image

??歸并排序的時(shí)間復(fù)雜度最好情況下為O(nlogn),最壞情況下為O(nlogn),平均時(shí)間復(fù)雜度為 O(nlogn)

??空間復(fù)雜度為O(n)

快速排序

??快速排序是對(duì)冒泡排序的一種優(yōu)化，利用分治和遞歸的思想。它的基本思想是：

??通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)要小，然后按此方法對(duì)這兩部分?jǐn)?shù)據(jù)進(jìn)行快速排序，整個(gè)過(guò)程是遞歸進(jìn)行，最終達(dá)到整個(gè)數(shù)組成為有序狀態(tài)。

- (NSMutableArray *)quickSortByArray:(NSMutableArray *)array{
    if (array.count < 2) {
        return array;
    }
    NSInteger num = array.count / 2;
    NSInteger centerValue = [array[num] integerValue];
    [array removeObjectAtIndex:num];
    
    NSMutableArray * left = [NSMutableArray array];
    NSMutableArray * right = [NSMutableArray array];
    for (NSUInteger index = 0; index < array.count; index ++) {
        if ([array[index] integerValue] < centerValue) {
            [left addObject:array[index]];
        }else{
            [right addObject:array[index]];
        }
    }
    
    NSMutableArray * leftArr = [self quickSortByArray:left];
    NSMutableArray * righArr = [self quickSortByArray:right];
    [leftArr addObject:[NSNumber numberWithInteger:centerValue]];
    [leftArr addObjectsFromArray:[righArr copy]];
    if (leftArr.count == 12) {
        //排序結(jié)束
        NSLog(@"123");
    }
    return leftArr;
}

快速排序過(guò)程

image

??快速排序的時(shí)間復(fù)雜度最好情況下為O(nlogn),最壞情況下為O(n^2),平均時(shí)間復(fù)雜度為 O(nlogn)

??空間復(fù)雜度為O(logn)

堆排序

??堆排序的原理是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一種排序算法。堆是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿足子節(jié)點(diǎn)的鍵值或索引總是大于(或小于)它的父節(jié)點(diǎn)。

??所以，堆排序的過(guò)程就是講一個(gè)無(wú)序序列構(gòu)造成一個(gè)大頂堆(或小頂堆)的過(guò)程

推薦這篇博客?? 堆排序詳解

計(jì)數(shù)排序

??計(jì)數(shù)排序是一個(gè)非基于比較的排序算法，計(jì)數(shù)排序用到一個(gè)額外的數(shù)組B，其原理是遍歷未排序的序列A，結(jié)束后使得B中每一個(gè)元素的下標(biāo)涵蓋A中所有不重復(fù)的元素值，而B(niǎo)中每個(gè)元素值代表元素下標(biāo)值在A中作為元素值的個(gè)數(shù)。即：

         A:   [10, 5, 10, 4, 3, 12, 3, 4, 8, 10 , 6]
    遍歷后得到B
              [ 0, 0, 0, 2, 2, 1, 1, 0, 1, 0, 3, 0, 1]
  再遍歷B更新A得到
              [3, 3, 4, 4, 5, 6, 8, 10, 10, 10, 12]

??以上只是最簡(jiǎn)單的過(guò)程，對(duì)序列B的長(zhǎng)度可以優(yōu)化成A中最大元素max和最小元素min的差值+1.

??B的長(zhǎng)度可以優(yōu)化成 k = max - min + 1 。

??計(jì)數(shù)排序的時(shí)間復(fù)雜度為O(n + k). 空間復(fù)雜度為O(k).

推薦這篇博客?? 漫畫(huà)：什么是計(jì)數(shù)排序？

桶排序

??桶排序是分治思想的典型引用，即將一個(gè)無(wú)序序列中的元素按值大小分成若干個(gè)區(qū)間(桶或箱),然后再對(duì)每一個(gè)區(qū)間進(jìn)行排序。在對(duì)每一個(gè)區(qū)間進(jìn)行排序的時(shí)候可能會(huì)使用其它排序方法或者遞歸的適用桶排序。

??假設(shè)原始無(wú)序序列為。A : [1, 3, 2, 7, 8, 6, 3 , 2, 6 , 10, 12，15，20]

?? 我們發(fā)現(xiàn)序列A的元素值集合并不大，即最小值為1 最大值為20 。我們就可以對(duì)這種序列適用桶排序。

??首先，創(chuàng)建固定量的桶：如何確定桶的區(qū)間呢？

??假定我們把序列分為2份。T0: [a, b) 和 T1 : [c, d)

??序列A中最大值為20，最小值為1 ，則區(qū)間長(zhǎng)度L為

?? ??L = (20 - 1 + 1)/2 = 10

??所以T0 : [1, 10 +1), 即 [1, 11)。 T1 : [10 + 1, 10 + 10 + 1), 即[11, 21）

??然后，遍歷A，計(jì)算元素應(yīng)該被分配在第幾個(gè)桶中：例如第一個(gè)元素1

??Tn = floor((1-1) / L) = 0 即元素1應(yīng)該被放在T0中。

??以此類推，直到所有的元素都被放入對(duì)應(yīng)的桶中。然后在分別對(duì)每一個(gè)

??桶中的元素進(jìn)行排序，最后在合并T0 到 Tn的桶，即得到最終的有序序列。

推薦這篇博客?? 排序算法之桶排序的深入理解以及性能分析

基數(shù)排序

推薦這篇博客?? 算法與數(shù)據(jù)結(jié)構(gòu)(十七) 基數(shù)排序(Swift 3.0版)