前幾天在碼農(nóng)網(wǎng)看到了一篇文章，關(guān)于講objective-c的幾種排序算法的圖形化操作方式猖败，自己也寫了一份代碼溫習(xí)下排序算法速缆。

代碼鏈接

先添上我的代碼倉庫鏈接 https://github.com/happyte/sort

選擇排序

• 1.排序效果演示如下

  
  

• 2.選擇排序的原理

• 2.1 假定第一個元素是"最小值"，往后遍歷恩闻，發(fā)現(xiàn)比"最小值"要小的元素就兩者進(jìn)行交換,即最終要把找到的最小值放在第一個元素位置上艺糜。
• 2.2 上面保證第一個元素肯定是最小值，接著縮小范圍從第二個元素開始且默認(rèn)為最小值幢尚，不斷往后遍歷交換最小值倦踢。
• 2.3 選擇排序保障每次都能找到一個最小元素放在指定位置

• 3.選擇排序代碼實(shí)現(xiàn)如下

   - (void)zs_selectSort:(ZSCompare)compare withCallback:(ZSExchange)exchange{
   if (self.count == 0) {
       return;
   }
   for (int i = 0; i < self.count; i++) {
       for (int j = i+1; j < self.count; j++) {
           if (compare(self[i],self[j])==NSOrderedDescending) {
               [self zs_exchangeWithIndexA:i indexB:j Change:exchange];
           }
       }
   }
}

冒泡排序

• 1.冒泡排序效果演示

  
  

• 2.冒泡排序原理

• 2.1 從第一個元素開始，比較相鄰兩個元素侠草，如果后面一個元素比前面一個元素小辱挥，則兩者進(jìn)行交換（即小的在前，大的在后）边涕。大的元素不斷往后移動晤碘，最終最大的元素沉到最后一個位置。
• 2.2 去掉最后一個位置功蜓，從第一個元素開始繼續(xù)執(zhí)行上面的操作园爷，不斷循環(huán)直至完成。
• 2.3 冒泡排序保障每一次操作要把最大值放在最后式撼。

• 3.冒泡排序代碼實(shí)現(xiàn)

- (void)zs_bubbleSort:(ZSCompare)compare withCallback:(ZSExchange)exchange{
   if (self.count == 0) {
       return;
   }
   for (NSInteger i = self.count-1; i > 0; i --) {
       for (NSInteger j = 0; j < i; j++) {
           if (compare(self[j],self[j+1])==NSOrderedDescending) {
               [self zs_exchangeWithIndexA:j indexB:j+1 Change:exchange];
           }
       }
   }
}

插入排序

• 1.插入排序效果演示

  
  

• 2.插入排序原理

• 2.1 插入排序用一個數(shù)組實(shí)現(xiàn)的話童社，把數(shù)組分為無序區(qū)和有序區(qū)兩個區(qū)間，開始有序區(qū)只有第一個元素著隆，從第二個元素到最后一個元素都為亂序區(qū)扰楼。
• 2.2 從亂序區(qū)取出第一個元素，與有序區(qū)的最后一個元素（即亂序區(qū)的前一個元素比較）美浦，下面有3種情況弦赖。
  • 2.2.1 如果比前一個元素要大，則有序區(qū)范圍增加1浦辨，亂序區(qū)范圍減去1蹬竖。
  • 2.2.2 如果與前一個元素相等，則可以繼續(xù)與前二個元素比較流酬，大的話就插入在該元素后面币厕，相等繼續(xù)與前三個元素比較吧，不可能比前二個元素小芽腾，因?yàn)槊看闻判蚨际潜ＷC有序區(qū)是按順序排列的旦装。其實(shí)相等可以不繼續(xù)向前比較，直接插入在有序區(qū)末位晦嵌。此時有序區(qū)增加1同辣，無序區(qū)減去1拷姿。
  • 2.2.3 如果比前一個元素要小，則先交換位置旱函，繼續(xù)比較取出的元素與前一個元素响巢，如果還要小繼續(xù)交換位置棒妨，相等則繼續(xù)往前比較踪古。把亂序區(qū)的元素插入到有序區(qū)的正確位置。
• 2.3 經(jīng)過上面的過程券腔，已經(jīng)把亂序區(qū)的第一個元素插入到有序區(qū)伏穆，且有序區(qū)長度增加1，亂序區(qū)長度減去1纷纫，取出縮小范圍后亂序區(qū)的第一個元素繼續(xù)上面操作枕扫，直至范圍不能縮小。

• 3.插入排序代碼實(shí)現(xiàn)

   - (void)zs_insertSort:(ZSCompare)compare withCallback:(ZSExchange)exchange{
    if (self.count == 0) {
        return;
    }
    for (NSInteger i = 0; i < self.count-1; i++) {
        for (NSInteger j = i+1; j > 0; j--) {
            if (compare(self[j],self[j-1])==NSOrderedAscending) {
                [self zs_exchangeWithIndexA:j indexB:j-1 Change:exchange];
            }
            else{
                break;
            }
        }
    }
}

快速排序

• 1.快速排序圖形化演示

  
  

• 2.這里講解下最原始的快速排序方法辱魁，先介紹下三個概念

• 2.1 中間值(pivot)烟瞧，第一次快速排序默認(rèn)第一個值為中間值
• 2.2 左游標(biāo)(i)，排序開始時第一個元素的位置為左游標(biāo)染簇，左游標(biāo)不斷向右移動
• 2.3 右游標(biāo)(j)参滴，排序開始時最后一個元素的位置為右游標(biāo)，右游標(biāo)不斷向左移動
• 2.4 當(dāng)左右游標(biāo)重合的時候锻弓。

• 3.下面解釋下元素是如何進(jìn)行交換的,例如給出一個數(shù)組[37,28,5,14,75,25,89,22,11]

• 3.1 從右邊游標(biāo)(j)開始(即11元素所在位置)砾赔，向前找比中間值(37)小的元素，此時找到的數(shù)就是11,交換中間值(pivot)和右游標(biāo)j對應(yīng)的元素青灼。交換完成后暴心，數(shù)組變?yōu)閇11,28,5,14,75,25,89,22,37]。此時左游標(biāo)指向的元素變?yōu)?1,11肯定比中間值(pivot)即37要小聚至，所以左游標(biāo)可以直接+1往后移動一位酷勺，左游標(biāo)指向28本橙，右游標(biāo)指向37扳躬。
• 3.2 從左邊游標(biāo)(i)開始(即現(xiàn)在的28元素所在位置)，向后找比中間值(37)大的元素甚亭，找到的數(shù)是75贷币，交換中間值(pivot)和左游標(biāo)i對應(yīng)的元素。交換完成后亏狰，數(shù)組變?yōu)閇11,28,5,14,37,25,89,22,75]役纹。左游標(biāo)i此時指向中間值37，此時右游標(biāo)指向的元素變?yōu)?5,75肯定比中間值(pivot)即37要大暇唾，所以右游標(biāo)可以直接-1往前移動一位,右游標(biāo)指向22促脉。
• 3.3 上面兩步的結(jié)論就是從右游標(biāo)j開始找比中間值(pivot)小的辰斋，交換完成后，左游標(biāo)i向后移動一位(i++)瘸味。從左游標(biāo)i開始找比中間值(pivot)大的宫仗，交換完成后，右游標(biāo)j向前移動一位(j--)旁仿。
• 3.4 經(jīng)過上面的排序藕夫，數(shù)組排序成為[11,28,5,14,37,25,89,22,75],左游標(biāo)為中間值37的位置，右游標(biāo)為22指向的位置枯冈。再次開始從右游標(biāo)開始找比中間值37小的元素毅贮，找到的就是22。交換22與37尘奏，數(shù)組成為[11,28,5,14,22,25,89,37,75],左游標(biāo)+1來到25元素位置,右游標(biāo)指向37元素所在位置滩褥。再次從左游標(biāo)開始向后找大的，找到的數(shù)為89炫加，交換左游標(biāo)位置的89和中間值37铸题。數(shù)組成為[11,28,5,14,22,25,37,89,75]，右游標(biāo)減1來到37位置琢感。左游標(biāo)也在37位置丢间，此時左右游標(biāo)重合第一次快速排序結(jié)束。
• 3.5 通過第一次快速排序使得驹针，比中間值37小的數(shù)都在37元素的前面烘挫。比37大的數(shù)都在37元素的后面。第一次快速排序獲得了中間值37元素的位置柬甥，第二次快速排序從第一個元素到37開始進(jìn)行排序饮六，即[11,28,5,14,22,25,37]進(jìn)行排序，同樣取第一個元素11為中間值苛蒲，左游標(biāo)為11所在位置卤橄，右游標(biāo)為37所在位置。
• 快速排序是個遞歸的過程臂外，上述的[11,28,5,14,22,25,37]全部排序完成后窟扑，會執(zhí)行第一次快速排序得到的后面幾個元素，即[89,75]數(shù)組進(jìn)行快速排序漏健。

• 4.快速排序代碼實(shí)現(xiàn)如下:

  - (void)zs_quickSort:(ZSCompare)compare withCallback:(ZSExchange)exchange{
    if (self.count == 0) {
        return;
    }
    [self zs_quickSortWithLow:0 High:self.count-1 Compare:compare Callback:exchange];
}
 //遞歸函數(shù),必須有返回
 - (void)zs_quickSortWithLow:(NSInteger)low High:(NSInteger)high Compare:(ZSCompare)compare Callback:(ZSExchange)exchange{
    if (low >= high) {
        return;
    }
    NSInteger pivotIndex = [self zs_pivotIndexWithLeft:low Right:high Compare:compare Callback:exchange];
    [self zs_quickSortWithLow:low High:pivotIndex-1 Compare:compare Callback:exchange];
    [self zs_quickSortWithLow:pivotIndex+1 High:high Compare:compare Callback:exchange];
}
 - (NSInteger)zs_pivotIndexWithLeft:(NSInteger)left Right:(NSInteger)right Compare:(ZSCompare)compare Callback:(ZSExchange)exchange{
    NSInteger i = left;
    NSInteger j = right;
    id pivot = self[left];
    while (i < j) {
        //從右邊找小的,如果右邊大于等于pivot嚎货，則右游標(biāo)向左移動
        while (i < j && compare(pivot,self[j])!= NSOrderedDescending) {
            j--;
        }
        //右邊的值小于pivot
        if (i < j) {
            [self zs_exchangeWithIndexA:i indexB:j Change:exchange];
            i++;
        }
        //從左邊找大的，如果左邊小于等于pivot,則左游標(biāo)向右移動
        while (i < j && compare(self[i],pivot)!=NSOrderedDescending) {
            i++;
        }
        //左邊的值大于pivot
        if (i < j) {
            [self zs_exchangeWithIndexA:i indexB:j Change:exchange];
            j--;
        }
    
    }
    return i;
}

堆排序

• 1.堆排序圖形化演示

  
  

• 2.首先可以把數(shù)組畫成一個二叉樹的形式蔫浆，還是用[12,28,5,14,75,25,89,22,11]數(shù)組進(jìn)行講解殖属。把數(shù)組畫成二叉樹，如下所示

  
  
• 3.堆排序首先要初始化一個大頂堆或小頂堆瓦盛，大頂堆即父結(jié)點(diǎn)比子左結(jié)點(diǎn)和子右結(jié)點(diǎn)大洗显，反之則為小頂堆外潜。假設(shè)數(shù)組下標(biāo)從0開始，父結(jié)點(diǎn)下標(biāo)為i挠唆，子左結(jié)點(diǎn)下標(biāo)為2i+1,子右結(jié)點(diǎn)下標(biāo)為2i+2橡卤。我在寫程序的時候給數(shù)組下標(biāo)為0的位置添加了一個空值，那么父結(jié)點(diǎn)下標(biāo)為i,子左結(jié)點(diǎn)下標(biāo)為2i,子右結(jié)點(diǎn)下標(biāo)為2i+1损搬。
• 4.下面解釋下如何構(gòu)建大頂堆

  • 4.1 從最后一個非葉子結(jié)點(diǎn)開始碧库，即14開始，如果父結(jié)點(diǎn)(14)比子左右結(jié)點(diǎn)(22和11)中的最大值(22)小巧勤，那么父結(jié)點(diǎn)(14)與子左右結(jié)點(diǎn)的最大值(22)交換嵌灰，交換結(jié)果如下：

    
    

  • 4.2 如果交換后的14比它的子左右結(jié)點(diǎn)還要小的話，要繼續(xù)沉底(交換后一定要滿足大頂堆的特點(diǎn))颅悉，可是這里它已經(jīng)沒有子左右結(jié)點(diǎn)沽瞭。因此從倒數(shù)第二個非葉子結(jié)點(diǎn)(5)開始，5與子左右結(jié)點(diǎn)最大值(89)交換剩瓶，交換結(jié)果如下:

    
    

  • 4.3 接下來從非子結(jié)點(diǎn)28開始驹溃，與子左右結(jié)點(diǎn)最大值(75)交換

    
    

  • 4.4 接下來從非子結(jié)點(diǎn)12開始，與子左右結(jié)點(diǎn)最大值(89)交換

    
    

  • 4.5 交換后的12比子左右結(jié)點(diǎn)的最大值(25)要小延曙，不滿足大頂堆特點(diǎn)豌鹤，需要繼續(xù)沉底

    
    

• 4.6 經(jīng)過上面幾步，大頂堆已經(jīng)構(gòu)造出來了枝缔，最大的那個元素(89)在最頂端布疙，交換第一個元素(89)和最后一個元素(11)，交換效果如下,交換后把89從這個二叉樹中移除:

  
  

• 4.7 現(xiàn)在的二叉樹顯然不滿足大頂堆特點(diǎn)愿卸，則第一個元素11需要繼續(xù)沉底灵临，與子左右結(jié)點(diǎn)的最大值(75)交換，結(jié)果如下:

  
  
  這里寫圖片描述

• 4.8 交換后的11仍然需要繼續(xù)沉底趴荸，與28交換

  
  

• 4.9 現(xiàn)在二叉樹又滿足大頂堆的特點(diǎn)了儒溉，交換第一個元素(75)與最后一個元素(14),交換后把最后一個元素從二叉樹中刪除。

  
  
• 4.10 再繼續(xù)沉底第一個元素发钝，直至范圍不能縮小顿涣，就能得到正確的排序。

• 5.堆排序代碼實(shí)現(xiàn)如下:

  - (void)zs_heapSort:(ZSCompare)compare withCallback:(ZSExchange)exchange{
    if (self.count == 0) {
        return;
    }
    [self insertObject:[[NSNull alloc]init] atIndex:0];
    //初始化最大堆排序
    for (NSInteger index = (self.count-1)/2; index > 0; index--) {
        [self sinkIndex:index bottomIndex:self.count-1 compare:compare Callback:exchange];
    }
    //第一次交換根結(jié)點(diǎn)與最后一個元素,然后不斷沉底第一個元素
    for (NSInteger index = self.count-1; index > 1; index--) {
        [self zs_exchangeWithIndexA:1 indexB:index Change:exchange];
        [self sinkIndex:1 bottomIndex:index-1 compare:compare Callback:exchange];
    }
    [self removeObjectAtIndex:0];
}
//第一個參數(shù)是需要沉底的元素索引值笼平，第二個元素是能允許沉底的最大索引值
 - (void)sinkIndex:(NSInteger)currentIndex bottomIndex:(NSInteger)bottomIndex compare:(ZSCompare)compare Callback:(ZSExchange)exchange{
    //數(shù)組第一個數(shù)為空园骆，就是為了子左結(jié)點(diǎn)剛好是2倍，子右節(jié)點(diǎn)是2倍+1
    for (NSInteger maxIndex = 2*currentIndex; maxIndex <= bottomIndex ; maxIndex *= 2) {
        //找到子左右節(jié)點(diǎn)的最大值寓调，父節(jié)點(diǎn)與這個值比較,首先必須保證右節(jié)點(diǎn)要存在
        if ((maxIndex+1)<=bottomIndex && compare(self[maxIndex],self[maxIndex+1])==NSOrderedAscending) {
            ++ maxIndex;
        }
        //比較父結(jié)點(diǎn)與子左右節(jié)點(diǎn)的最大值，如果小于锄码，則交換夺英，否則break跳出
        if (compare(self[currentIndex],self[maxIndex])==NSOrderedAscending) {
            [self zs_exchangeWithIndexA:currentIndex indexB:maxIndex Change:exchange];
        }
        else{
            break;
        }
        //將當(dāng)前需要改變的節(jié)點(diǎn)位置currentIndex變成maxIndex,這樣就可以繼續(xù)沉底
        currentIndex = maxIndex;
    }
}