最近將之前的算法知識(shí)進(jìn)行梳理，總結(jié)了幾種常見的排序算法。廢話不多說，上圖上代碼，看解析

冒泡排序

原理：
1.臨近的數(shù)字兩兩進(jìn)行比較,按照從小到大或者從大到小的順序進(jìn)行交換。
2.這樣一趟過去后,最大或最小的數(shù)字被交換到了最后一位。
3.然后再從頭開始進(jìn)行兩兩比較交換,直到倒數(shù)第二位時(shí)結(jié)束。

void bubble_sort(int a[], int n)
{
    int i,j,temp;
    for (j = 0; j < n-1; j++) {
        for (i = 0; i < n - 1 - j; i++) {
            if (a[i] > a[i + 1]) {
                temp = a[I];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        int a[6] = {9,6,2,7,1,8};
        bubble_sort(a, 6);
        
    }
    return 0;
}

bubble_sort

快速排序

原理：
快速排序是對(duì)冒泡排序的一種改進(jìn)，基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)兩部分記錄繼續(xù)進(jìn)行排序。

void quick_sort(int *a, int left, int right)
{
    if(left > right){
        return;
    }
    int i = left;
    int j = right;
    int key = a[left];
    while (i < j) {
        while (i < j && key <= a[j]) {
            j--;
        }
        a[i] = a[j];
        while (i < j && key >= a[i]) {
            I++;
        }
        a[j] = a[I];
    }
    a[i] = key;
    //兩邊分別遞歸
    quick_sort(a, left, i - 1);
    quick_sort(a, i + 1, right);
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        int a[6] = {6,2,7,3,8,9};
        //第二個(gè)參數(shù)：起始索引
        //第三個(gè)參數(shù)：結(jié)束索引
        quick_sort(a,0,5);

    }
    return 0;
}

創(chuàng)建變量i=0（指向第一個(gè)數(shù)據(jù)）, j=5(指向最后一個(gè)數(shù)據(jù)), k=6(賦值為第一個(gè)數(shù)據(jù)的值)。

quick_sort

選擇排序

原理：
從所有序列中先找到最小的，然后放到第一個(gè)位置。之后再看剩余元素中最小的，放到第二個(gè)位置……以此類推，就可以完成整個(gè)的排序工作了。

void select_sort(int a[], int n)
{
    for (int i = 0; i < n; i++) {
        int temp = 0;
        int min = a[I];
        int index = I;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < min) {
                min = a[j];
                index = j;
            }
        }
        temp = a[I];
        a[i] = min;
        a[index] = temp;
    }
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        int a[6] = {9,6,2,7,1,8};
        select_sort(a,6);
        
    }
    return 0;
}

select_sort

歸并排序

原理：
用二分法將數(shù)組分割，直到每個(gè)分組里都只有一個(gè)元素。所以此時(shí)我們就得到了若干個(gè)有序數(shù)組。（每個(gè)數(shù)組里只有一個(gè)元素）

NSMutableArray * array = [NSMutableArray arrayWithObjects:@6,@1,@7,@5,@8,@2,@4,@3, nil];
//調(diào)用排序
[self mergeSortArray:array];

- (void)mergeSortArray:(NSMutableArray *)array {
    //創(chuàng)建一個(gè)副本數(shù)組
    NSMutableArray * auxiliaryArray = [[NSMutableArray alloc]initWithCapacity:array.count];
    
    //對(duì)數(shù)組進(jìn)行第一次二分，初始范圍為0到array.count-1
    [self mergeSort:array auxiliary:auxiliaryArray low:0 high:array.count-1];
}

- (void)mergeSort:(NSMutableArray *)array auxiliary:(NSMutableArray *)auxiliaryArray low:(int)low high:(int)high {
    //遞歸跳出判斷
    if (low>=high) {
        return;
    }
    //對(duì)分組進(jìn)行二分
    int middle = (high - low)/2 + low;
    
    //對(duì)左側(cè)的分組進(jìn)行遞歸二分 low為第一個(gè)元素索引，middle為最后一個(gè)元素索引
    [self mergeSort:array auxiliary:auxiliaryArray low:low high:middle];
    
    //對(duì)右側(cè)的分組進(jìn)行遞歸二分 middle+1為第一個(gè)元素的索引，high為最后一個(gè)元素的索引
    [self mergeSort:array auxiliary:auxiliaryArray low:middle + 1 high:high];
    
    //對(duì)每個(gè)有序數(shù)組進(jìn)行回歸合并
    [self merge:array auxiliary:auxiliaryArray low:low middel:middle high:high];
}

- (void)merge:(NSMutableArray *)array auxiliary:(NSMutableArray *)auxiliaryArray low:(int)low middel:(int)middle high:(int)high {
    //將數(shù)組元素復(fù)制到副本
    for (int i=low; i<=high; i++) {
        auxiliaryArray[i] = array[I];
    }
    //左側(cè)數(shù)組標(biāo)記
    int leftIndex = low;
    //右側(cè)數(shù)組標(biāo)記
    int rightIndex = middle + 1;
    
    //比較完成后比較小的元素要放的位置標(biāo)記
    int currentIndex = low;
    
    while (leftIndex <= middle && rightIndex <= high) {
        //此處是使用NSNumber進(jìn)行的比較，你也可以轉(zhuǎn)成NSInteger再比較
        if ([auxiliaryArray[leftIndex] compare:auxiliaryArray[rightIndex]]!=NSOrderedDescending) {
            //左側(cè)標(biāo)記的元素小于等于右側(cè)標(biāo)記的元素
            array[currentIndex] = auxiliaryArray[leftIndex];
            currentIndex++;
            leftIndex++;
        }else{
            //右側(cè)標(biāo)記的元素小于左側(cè)標(biāo)記的元素
            array[currentIndex] = auxiliaryArray[rightIndex];
            currentIndex++;
            rightIndex++;
        }
    }
    //如果完成后左側(cè)數(shù)組有剩余
    if (leftIndex <= middle) {
        for (int i = 0; i<=middle - leftIndex; i++) {
            array[currentIndex +i] = auxiliaryArray[leftIndex +I ];
        }
    }
}

將兩個(gè)有序數(shù)組合并為一個(gè)數(shù)組

合并兩個(gè)有序數(shù)組

歸并排序

merge_sort

總結(jié)

在實(shí)際應(yīng)用中，根據(jù)需求選擇合適的排序算法。
其他常用的排序算法還有：插入排序，堆排序，桶排序。