一、冒泡排序

冒泡排序是一種簡單的排序算法藏鹊。它重復(fù)地走訪過要排序的數(shù)列盘寡，一次比較兩個(gè)元素竿痰，如果它們的順序錯(cuò)誤就把它們交換過來影涉。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換常潮，也就是說該數(shù)列已經(jīng)排序完成喊式。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端萧朝。

1.算法過程：

（1）比較相鄰的元素献联。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)里逆；
（2）對每一對相鄰元素作同樣的操作胁镐，從開始第一對到結(jié)尾的最后一對盯漂，這樣在最后的元素應(yīng)該會是最大的數(shù)笨农；
（3）針對所有的元素重復(fù)以上的步驟谒亦，除了最后一個(gè)份招；
（4）重復(fù)步驟1~3，直到?jīng)]有任何一對數(shù)字需要比較。

2.復(fù)雜度

假設(shè)序列有 n 個(gè)元素鄙漏，(n>1)怔蚌，根據(jù)算法步驟桦踊，第 1 輪 需在 n 個(gè)元素中兩兩比較 (n-1) 次籍胯，第 2 輪 需要在剩余的 (n-1) 個(gè)元素中兩兩比較 (n-2) 次杖狼，第(n-1) 輪需在最后 2 個(gè)元素中僅比較 1 次蝶涩。
函數(shù)表達(dá)式為：
f(n) = (n-1) + (n-2) +...+ 2 + 1
f(n) = [1+(n-1)]×(n-1)/2
f(n) = n*(n-1)/2
f(n) = (n2 - n)/2

用 大 O 表示法嗽上，忽略常量兽愤、低階和常數(shù)系數(shù)鲜屏。
時(shí)間復(fù)雜度為：O(n2)
空間復(fù)雜度為：并未開辟額外空間惯殊，所以為 O(1)
穩(wěn)定性: 穩(wěn)定

3.代碼

    NSMutableArray *array = [NSMutableArray arrayWithObjects:@45,@3,@22,@23,@40,@34, nil];
    for (int i = 0; i < array.count - 1; i ++) {//循環(huán)array.count-1次
        for (int j = 0; j < array.count - 1 ; j ++) {
            if ([array[j] integerValue] >[array[j+1] integerValue] ) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
    NSLog(@"%@",array);

這樣寫的冒泡排序需要比對（數(shù)組的個(gè)數(shù)-1）的平方次土思，每一圈內(nèi)循環(huán)都把最大的數(shù)換到最后己儒，如上：第一圈 45 被替換到最后一個(gè)元素位置捆毫，第二圈 40 被替換到倒數(shù)第二個(gè)元素的位置绩卤，那么 40 和 45 還需要比對么，答案是否定的何暇，所以可以對上述方法進(jìn)行第一次優(yōu)化：

    NSMutableArray *array = [NSMutableArray arrayWithObjects:@45,@3,@22,@23,@40,@34, nil];
    for (int i = 0; i < array.count - 1; i ++) {//循環(huán)array.count-1次
        for (int j = 0; j < array.count - 1 - i; j ++) {
            if ([array[j] integerValue] >[array[j+1] integerValue] ) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
    NSLog(@"%@",array);

當(dāng)循環(huán)結(jié)束前，數(shù)組已經(jīng)排好順序了宏胯，那么后面的比較就沒有必要了胳嘲，可以跳出循環(huán)了牛。繼續(xù)優(yōu)化結(jié)果：

    for (int i = 0; i < array.count - 1; i ++) {//循環(huán)array.count-1次
        BOOL isEnd = NO;//判斷是否已排序完成
        for (int j = 0; j < array.count -1 -i; j++) {
            if ([array[j] integerValue] >[array[j+1] integerValue] ) {
                isEnd = YES;
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
        if (!isEnd) {
            break;
        }

    }
    NSLog(@"%@",array);

二鹰祸、選擇排序

選擇排序是一種簡單直觀的排序算法粗井，無論什么數(shù)據(jù)進(jìn)去都是 O(n2) 的時(shí)間復(fù)雜度浇衬。所以用到它的時(shí)候耘擂，數(shù)據(jù)規(guī)模越小越好醉冤。唯一的好處可能就是不占用額外的內(nèi)存空間了吧蚁阳。

1.算法過程

（1）首先在未排序序列中找到最新菥琛（大）元素定血，存放到排序序列的起始位置糠悼。
（2）再從剩余未排序元素中繼續(xù)尋找最星城恰（大）元素靖苇，然后放到已排序序列的末尾。
（3）重復(fù)第二步脾拆，直到所有元素均排序完畢名船。

2.復(fù)雜度

假設(shè)序列有 n 個(gè)元素（n>1）渠驼，根據(jù)算法步驟百揭，第 1 輪 需在 n 個(gè)元素中遍歷 n 次查找到最小的元素器一，第2輪 需在剩余的 (n-1) 個(gè)元素中遍歷 (n-1) 次找到最小的元素盹舞，… 第 n-1 輪 需在剩余的 2 個(gè)元素中找到最小的元素，第 n 輪剩余 1 個(gè)元素放在已排序元素的末尾隘庄。

函數(shù)表達(dá)式為：
f(n) = n+(n-1)+…+2+1
f(n) = (n+1)*n/2
f(n) = (n2+n)/2

用 大 O 表示法踢步，忽略常量、低階和常數(shù)系數(shù)丑掺。
時(shí)間復(fù)雜度為：O(n2)
空間復(fù)雜度為：并未開辟額外空間获印，所以為 O(1)
穩(wěn)定性: 不穩(wěn)定

3.代碼

    int count = 0;
    NSMutableArray *array = [NSMutableArray arrayWithObjects:@3,@2,@9,@1,@6,@7,@4,@5,@8,nil];
        for (int i = 0; i<array.count - 1; i++) {
            NSInteger min = [array[i] integerValue];
            NSInteger index = i;
            for (NSInteger j= i+1; j< array.count; j++) {
                
                if (min > [array[j] integerValue]) {
                    min = [array[j] integerValue];
                    index = j;
                }
                count ++;
            }
            [array exchangeObjectAtIndex:index withObjectAtIndex:i];
        }
    NSLog(@"排序后的數(shù)組===%@",array);
    NSLog(@"循環(huán)次數(shù)count=%d",count);

優(yōu)化：在循環(huán)選取時(shí)，每次掃描未排序區(qū)間分別選擇最小街州、最大值放于數(shù)組始兼丰、末位置

    NSMutableArray *array = [NSMutableArray arrayWithObjects:@3,@2,@9,@1,@6,@7,@4,@5,@8,@5,nil];
    for (int i = 0; i<array.count - 1; i++) {
        NSInteger min = [array[i] integerValue];
        NSInteger max = [array[array.count - 1 - i] integerValue];
                
        NSInteger minIndex = i;
        NSInteger maxIndex = array.count - 1 - i;

        if(minIndex +1 == maxIndex||minIndex == maxIndex){
            break;
        }
        for (NSInteger j= i+1; j< array.count-i; j++) {

            if (min > [array[j] integerValue]) {
                min = [array[j] integerValue];
                minIndex = j;
            }
            if (max < [array[j] integerValue]) {
                max = [array[j] integerValue];
                maxIndex = j;
            }
        }

        [array exchangeObjectAtIndex:minIndex withObjectAtIndex:i];
        [array exchangeObjectAtIndex:maxIndex withObjectAtIndex:array.count - i - 1];

    }
    NSLog(@"排序后的數(shù)組===%@",array);

4.不穩(wěn)定性

選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的，比如給第一個(gè)位置選擇最小的唆缴，在剩余元素里面給第二個(gè)元素選擇第二小的艳丛，依次類推戴差，直到第 n-1個(gè)元素，第 n 個(gè)元素不用選擇了，因?yàn)橹皇Ｏ滤粋€(gè)最大的元素了爽航。那么衷佃，在一趟選擇惯悠，如果一個(gè)元素比當(dāng)前元素小情萤，而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面睁宰，那么交換后穩(wěn)定性就被破壞了硫兰。比較拗口泳赋，舉個(gè)例子，序列 5,8,5,3,6，我們知道第一遍選擇第 1 個(gè)元素 5 會和 3 交換，那么原序列中兩個(gè) 5 的 相對前后順序就被破壞了盘榨，所以選擇排序是一個(gè)不穩(wěn)定的排序算法捷犹。

三憔晒、插入排序

插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法从撼。它的工作原理是通過構(gòu)建有序序列啃奴，對于未排序數(shù)據(jù)揖膜，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。可以形象地比喻成打撲克牌的時(shí)候整理牌的順序的方法刁愿。

1.算法過程描述

（1）從第一個(gè)元素開始叔遂，該元素可以認(rèn)為已經(jīng)被排序；
（2）取出下一個(gè)元素作為新元素呢蔫，在已經(jīng)排序的元素序列中從后向前掃描爷贫；
（3）如果該元素（已排序）大于新元素，將該元素移到下一位置箫津；
（4）重復(fù)步驟3叨吮，直到找到已排序的元素小于或者等于新元素的位置围肥；
（5）將新元素插入到該位置后；
（6）重復(fù)步驟2~5诬烹。

2.復(fù)雜度

假設(shè)序列有 n 個(gè)元素（n>1）门粪，根據(jù)算法步驟，第 1 輪取第2個(gè)元素插入到已排序數(shù)列（1個(gè)元素）中，第 2 輪取 第3個(gè)元素插入到已排序數(shù)列（有2個(gè)元素）中嫉入，… 第 (n-1) 輪取第n個(gè)元素插入到已排序數(shù)列（有(n-1)` 個(gè)元素）中徐裸。

函數(shù)表達(dá)式為：
f(n) = 1+2+…+(n-1)
f(n) = n*(n-1)/2
f(n) = (n2-n)/2

用 大 O 表示法贫贝，忽略常量、低階和常數(shù)系數(shù)。
時(shí)間復(fù)雜度為：O(n2)
空間復(fù)雜度為：并未開辟額外空間摸柄，所以為O(1)
穩(wěn)定性: 穩(wěn)定

3.代碼

    NSMutableArray *array = [NSMutableArray arrayWithObjects:@3,@2,@9,@1,@6,@7,@4,@5,@8,@5,nil];
    for (int i = 0; i<array.count ; i++) {
        NSInteger valueI = [array[i] integerValue];
        for (int j= i - 1; j >= 0; j--) {
            
            NSInteger valueJ = [array[j] integerValue];
            if(valueI < valueJ){
                [array exchangeObjectAtIndex:i withObjectAtIndex:j];
                i = j;
            }
        }
    }
    NSLog(@"排序后的數(shù)組===%@",array);

四捞稿、快速排序

快速排序使用分治法（Divide and conquer）策略來把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）咧七。
本質(zhì)上來看澈蟆，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法疲憋。
基本思想是旁壮，通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小谐檀，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序抡谐，以達(dá)到整個(gè)序列有序。

1.算法過程描述

（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ù)組中下標(biāo)從 p 到 r 之間的一組數(shù)據(jù)厨钻，我們選擇 p 到 r之間的任意一個(gè)數(shù)據(jù)作為 pivot(分區(qū)點(diǎn)), 我們遍歷 p 到r之間的數(shù)據(jù)扼雏，將小于 pivot 的放到左邊坚嗜，將大于 pivot 的放到右邊，將 pivot 放到中間诗充。經(jīng)過這一步驟之后惶傻，數(shù)組 p 到 r 之間的數(shù)據(jù)就被分成了三個(gè)部分，前面 p 到 q-1 之間都是小于 pivot 的其障，中間是 pivot银室，后面的 q+1 到r 之間是大于 pivot 的。
剩下励翼，可以用遞歸排序下標(biāo)從 p 到 q-1 之間的數(shù)據(jù)和下標(biāo)從 q+1 到 r之間的數(shù)據(jù)蜈敢，直到區(qū)間縮小為 1，就說明所有的數(shù)據(jù)都有序了汽抚。

2.復(fù)雜度

用 大O 表示法抓狭，忽略常量、低階和常數(shù)系數(shù)造烁。
時(shí)間復(fù)雜度為：最壞 O(n2) 否过， 最好 O(nlogn)
空間復(fù)雜度為：并未開辟額外空間，所以為 O(1)
穩(wěn)定性: 不穩(wěn)定

3.代碼

- (void)viewDidLoad {
    [super viewDidLoad];
    self.view.backgroundColor = [UIColor whiteColor];

    NSMutableArray *array = [NSMutableArray arrayWithObjects:@3,@2,@9,@1,@6,@7,@4,@5,@8,@5,nil];
    [self quickSortArray:array withLeftIndex:0 andRightIndex:(int)array.count - 1];
    NSLog(@"排序后的數(shù)組===%@",array);
}

 
//快速排序
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex{
    if (leftIndex >= rightIndex) {//如果數(shù)組長度為0或1時(shí)返回
        return ;
    }
    NSInteger i = leftIndex;
    NSInteger j = rightIndex;
    //記錄比較基準(zhǔn)數(shù)
    NSInteger key = [array[i] integerValue];
    while (i < j) {
        /**** 首先從右邊j開始查找比基準(zhǔn)數(shù)小的值 ***/
        while (i < j && [array[j] integerValue] >= key) {//如果比基準(zhǔn)數(shù)大惭蟋，繼續(xù)查找
            j--;
        }
        //如果比基準(zhǔn)數(shù)小苗桂，則將查找到的小值調(diào)換到i的位置
        array[i] = array[j];
        /**** 當(dāng)在右邊查找到一個(gè)比基準(zhǔn)數(shù)小的值時(shí)，就從i開始往后找比基準(zhǔn)數(shù)大的值 ***/
        while (i < j && [array[i] integerValue] <= key) {//如果比基準(zhǔn)數(shù)小告组，繼續(xù)查找
            i++;
        }
        //如果比基準(zhǔn)數(shù)大煤伟，則將查找到的大值調(diào)換到j(luò)的位置
        array[j] = array[i];
    }
    //將基準(zhǔn)數(shù)放到正確位置
    array[i] = @(key);
    /**** 遞歸排序 ***/
    //排序基準(zhǔn)數(shù)左邊的
    [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
    //排序基準(zhǔn)數(shù)右邊的
    [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}

4.穩(wěn)定性

如果數(shù)組中有兩個(gè)相同的元素，比如測試的序列 6木缝，8便锨，7，6我碟，3放案，5，9矫俺，4 在經(jīng)過第一次分區(qū)操作之后吱殉，兩個(gè) 6 的相對先后順序就會改變。所以恳守，快速排序并不是一個(gè)穩(wěn)定的排序算法考婴。

5.快速排序的性能分析

最好的情況下, 選擇的 pivot 都很合適，正好能將大區(qū)間對等地一分為二催烘。這時(shí)快排的時(shí)間復(fù)雜度遞推求解公式跟歸并是相同的沥阱。即為 O(nlogn)。

最壞的情況下伊群，有序數(shù)組中考杉，每次選擇最后一個(gè)元素作為 pivot策精，那每次分區(qū)得到的兩個(gè)區(qū)間都是不均等的。我們需要進(jìn)行大約 n 次分區(qū)操作崇棠，才能完成快排的整個(gè)過程咽袜。每次分區(qū)我們平均要掃描大約 n/2 個(gè)元素，快排的時(shí)間復(fù)雜度就從 O(nlogn) 退化成了 O(n2)枕稀。

T(n) 在大部分情況下的時(shí)間復(fù)雜度都可以做到 O(nlogn)询刹，只有在極端情況下，才會退化到 O(n2)萎坷。