目錄: 手寫這些代碼妹萨，三大排序
1.冒泡排序
2.插入排序(少于20條用插入)
3.選擇排序
4.快速排序
5.歸并
6.堆排序

1贪薪、冒泡排序 .時間復(fù)雜度 O(n2)
冒泡排序是一種用時間換空間的排序方法，最壞情況是把順序的排列變成逆序眠副，或者把逆序的數(shù)列變成順序画切。在這種情況下，每一次比較都需要進行交換運算囱怕。舉個例子來說霍弹，一個數(shù)列 5 4 3 2 1 進行冒泡升序排列，第一次大循環(huán)從第一個數(shù)（5）開始到倒數(shù)第二個數(shù)（2）結(jié)束娃弓，比較過程：先比較5和4典格，4比5小，交換位置變成4 5 3 2 1台丛；比較5和3耍缴，3比5小，交換位置變成4 3 5 2 1……最后比較5和1挽霉，1比5小防嗡，交換位置變成4 3 2 1 5。這時候共進行了4次比較交換運算侠坎，最后1個數(shù)變成了數(shù)列最大數(shù)蚁趁。
第二次大循環(huán)從第一個數(shù)（4）開始到倒數(shù)第三個數(shù)（2）結(jié)束。進行3次比較交換運算实胸。
……
所以總的比較次數(shù)為 4 + 3 + 2 + 1 = 10次
對于n位的數(shù)列則有比較次數(shù)為 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2他嫡，這就得到了最大的比較次數(shù)
而O(N^2)表示的是復(fù)雜度的數(shù)量級。舉個例子來說庐完，如果n = 10000钢属，那么 n(n-1)/2 = (n^2 - n) / 2 = (100000000 - 10000) / 2，相對10^8來說门躯，10000小的可以忽略不計了淆党，所以總計算次數(shù)約為0.5 * N^2。 用O(N^2)就表示了其數(shù)量級（忽略前面系數(shù)0.5）生音。

//冒泡排序
-(void)bubbleSort:(NSMutableArray*)array int:(int)n
{
    for (int i = 0; i<n-1; ++i) {
        for (int j=0; j<n-i-1; ++j) {
            if ([array[j] intValue] > [array[j+1] intValue]) {
                NSNumber* temp = array[j];
                [array replaceObjectAtIndex:j withObject:array[j+1]];
                [array replaceObjectAtIndex:j+1 withObject:temp];
            }
        }
    }
    NSLog(@"%@",array);
}

2宁否、插入排序
O(n2)
—插入排序：插入即表示將一個新的數(shù)據(jù)插入到一個有序數(shù)組中，并繼續(xù)保持有序缀遍。例如有一個長度為N的無序數(shù)組慕匠，進行N-1次的插入即能完成排序；
1）第一次域醇，數(shù)組第1個數(shù)認為是有序的數(shù)組台谊，將數(shù)組第二個元素插入僅有1個有序的數(shù)組中蓉媳；
2）第二次，數(shù)組前兩個元素組成有序的數(shù)組锅铅，將數(shù)組第三個元素插入由兩個元素構(gòu)成的有序數(shù)組中......
3）第N-1次酪呻，數(shù)組前N-1個元素組成有序的數(shù)組，將數(shù)組的第N個元素插入由N-1個元素構(gòu)成的有序數(shù)組中盐须，則完成了整個插入排序玩荠。

-(void)insertSortWithArray:(NSArray *)aData{  
    NSMutableArray *data = [[NSMutableArray alloc]initWithArray:aData];  
    for (int i = 1; i < [data count]; i++) {  
        id tmp = [data objectAtIndex:i];  
        int j = i-1;  
        while (j != -1 && [data objectAtIndex:j] > tmp) {  
            [data replaceObjectAtIndex:j+1 withObject:[data objectAtIndex:j]];  
            j--;  
        }  
        [data replaceObjectAtIndex:j+1 withObject:tmp];  
    }  
    NSLog(@"插入排序后的結(jié)果：%@",[data description]);  
}  

3、選擇排序(Selection sort)
O(n2)
每一趟從待排序的數(shù)據(jù)元素中選出最性舻恕（或最大）的一個元素阶冈，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完塑径。 選擇排序是不穩(wěn)定的排序方法女坑。
選擇排序：比如在一個長度為N的無序數(shù)組中，
1）在第一趟遍歷N個數(shù)據(jù)统舀，找出其中最小的數(shù)值與第一個元素交換匆骗，
2）第二趟遍歷剩下的N-1個數(shù)據(jù)，找出其中最小的數(shù)值與第二個元素交換......
3）第N-1趟遍歷剩下的2個數(shù)據(jù)誉简，找出其中最小的數(shù)值與第N-1個元素交換碉就，
至此選擇排序完成。

int main(int argc, const char * argv[])
{
    int array[] = {12,2, 6, 9, 8, 5, 7, 1, 4};
    //為了增加可移植性(采取sizeof())計算數(shù)組元素個數(shù)count
    int count = sizeof(array) /sizeof(array[0]);
    //
    for (int i = 0; i < count - 1; i++) {   //比較的趟數(shù)
        int minIndex = i;//查找最小值
        for (int j = minIndex +1; j < count; j++ ) {
            if (array[minIndex] > array[j]) {
                minIndex = j;
            }
        }
        //如果沒有比較到最后還剩余一個數(shù),那么就執(zhí)行下面的操作
        if (minIndex != i) {
            //交換數(shù)據(jù)
            int temp = 0;
            temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }
    return 0;
}

4描融、快速排序 .時間復(fù)雜度 O(n*log2n)
1 ）設(shè)置兩個變量i铝噩，j 衡蚂，排序開始時i = 0窿克，就j = mutableArray.count - 1；
2 ）設(shè)置數(shù)組的第一個值為比較基準數(shù)key毛甲，key = mutableArray.count[0]年叮；
3 ）因為設(shè)置key為數(shù)組的第一個值，所以先從數(shù)組最右邊開始往前查找比key小的值玻募。如果沒有找到只损，j--繼續(xù)往前搜索；如果找到則將mutableArray[i]和mutableArray[j]互換七咧，并且停止往前搜索跃惫，進入第4步；
4 ）從i位置開始往后搜索比key大的值艾栋，如果沒有找到爆存，i++繼續(xù)往后搜索；如果找到則將mutableArray[i]和mutableArray[j]互換蝗砾，并且停止往后搜索先较；
5 ）重復(fù)第3携冤、4步，直到i == j（此時剛好執(zhí)行完第3步或第4部）闲勺，停止排序曾棕；

快速排序.jpg

//快速排序
NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(6), @(1),@(2),@(5),@(9),@(4),@(3),@(30),@(35),@(36),@(7),nil];
[self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count - 1];

- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
    if (leftIndex >= rightIndex) {//如果數(shù)組長度為0或1時返回
        return ;
    }
    NSInteger i = leftIndex;
    NSInteger j = rightIndex;
    //記錄比較基準數(shù)
    NSInteger key = [array[i] integerValue];
    while (i < j) {
        /**** 首先從右邊j開始查找比基準數(shù)小的值 ***/
        while (i < j && [array[j] integerValue] >= key) {//如果比基準數(shù)大，繼續(xù)查找
            j--;
        }
        //如果比基準數(shù)小菜循，則將查找到的小值調(diào)換到i的位置
        array[i] = array[j];
        /**** 當在右邊查找到一個比基準數(shù)小的值時翘地，就從i開始往后找比基準數(shù)大的值 ***/
        while (i < j && [array[i] integerValue] <= key) {//如果比基準數(shù)小，繼續(xù)查找
            i++;
        }
        //如果比基準數(shù)大癌幕，則將查找到的大值調(diào)換到j(luò)的位置
        array[j] = array[i];
    }
    
    //將基準數(shù)放到正確位置
    array[i] = @(key);
    /**** 遞歸排序 ***/
    //排序基準數(shù)左邊的
    [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
    //排序基準數(shù)右邊的
    [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}

5子眶、歸并
時間復(fù)雜度O(nlogn)
歸并過程為：比較a[i]和b[j]的大小，若a[i]≤b[j]序芦，則將第一個有序表中的元素a[i]復(fù)制到r[k]中臭杰，并令i和k分別加上1；否則將第二個有序表中的元素b[j]復(fù)制到r[k]中谚中，并令j和k分別加上1渴杆，如此循環(huán)下去，直到其中一個有序表取完宪塔，然后再將另一個有序表中剩余的元素復(fù)制到r中從下標k到下標t的單元磁奖。歸并排序的算法我們通常用遞歸實現(xiàn)，先把待排序區(qū)間[s,t]以中點二分某筐，接著把左邊子區(qū)間排序比搭，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]南誊。

- (void)mergeSortArray:(NSMutableArray *)array lowIndex:(NSInteger)lowIndex highIndex:(NSInteger)highIndex
{
    if (lowIndex >= highIndex) {
        return;
    }
    NSInteger midIndex = lowIndex + (highIndex - lowIndex) / 2;
    [self mergeSortArray:array lowIndex:lowIndex highIndex:midIndex];
    [self mergeSortArray:array lowIndex:midIndex + 1 highIndex:highIndex];
    [self mergeArray:array lowIndex:lowIndex midIndex:midIndex highIndex:highIndex];
}

- (void)mergeArray:(NSMutableArray *)array lowIndex:(NSInteger)lowIndex midIndex:(NSInteger)midIndex highIndex:(NSInteger)highIndex
{
    for (NSInteger i = lowIndex; i <= highIndex; i ++) {
        self.tempArr[i] = array[i];
    }
   
    NSInteger k = lowIndex;
    NSInteger l = midIndex + 1;
    for (NSInteger j = lowIndex; j <= highIndex; j ++) {
        if (l > highIndex) {
            array[j] = self.tempArr[k];
            k++;
        }else if (k > midIndex)
        {
            array[j] = self.tempArr[l];
            l++;
        }else if ([self.tempArr[k] integerValue] > [self.tempArr[l] integerValue])
        {
            array[j] = self.tempArr[l];
            l++;
        }else
        {
            array[j] = self.tempArr[k];
            k++;
        }
    }
}

6身诺、堆排序
圖解排序算法(三)之堆排序

//堆排序time:O(nlgn)
+ (void)heapSort:(NSMutableArray *)list{
    int i , size;
    size = [list count]/1.0;
    // 從子樹開始整理樹
    for (i = [list count]/1.0 - 1; i >= 0; i--) {
        [self createBiggestHeap:list withSize:size beIndex:i];
    }
    //拆除樹
    while (size > 0) {
        [list exchangeObjectAtIndex:size - 1 withObjectAtIndex:0];//將根（最小）與數(shù)組最末交換
        size--;//樹大小減小
        [self createBiggestHeap:list withSize:size beIndex:0];//整理樹
    }
}

/// 最大堆heap  最大／最小優(yōu)先級隊列
+ (void)createBiggestHeap:(NSMutableArray *)list withSize:(int)size beIndex:(int)element{
    int lchild = element * 2 + 1,rchild = lchild + 1;//左右子樹
    while (rchild < size) {//子樹均在范圍內(nèi)
        //如果比左右子樹都小抄囚，完成整理
        if (list[element] <= list[lchild] && list[element] <= list[rchild]) return;
        //如果左邊最小
        if(list[lchild] <= list[rchild]){
            [list exchangeObjectAtIndex:element withObjectAtIndex:lchild];//把左面的提到上面
            element = lchild;//循環(huán)時整理子樹
        }else{
            //否則右面最小
            [list exchangeObjectAtIndex:element withObjectAtIndex:rchild];
            element = rchild;
        }
        lchild = element * 2 + 1;
        rchild = lchild + 1;//重新計算子樹位置
    }
    //只有左子樹且子樹小于自己
    if (lchild < size && list[lchild] < list[element]) {
        [list exchangeObjectAtIndex:lchild withObjectAtIndex:element];
    }
}

參考：
http://blog.csdn.net/hguisu/article/details/7776068
文中評論很長....有的指出作者的錯誤霉赡，所以代碼要自己要運行驗證。