几种常用的排序算法，OC实现

1、冒泡排序
原理是：比较相邻的元素，如果第一个比第二个大，就交换他们两个。对每一个相邻元素作同样的工作，从开始第一对到结尾的最后一对，重复以上步骤，直到没有任何一对数字需要比较。
n个元素比较n-1趟
每趟比较次数=数组元素个数-趟数
OC代码实现：

+ (void)buddleSort:(NSMutableArray *)array
{
    if(array == nil || array.count == 0){
        return;
    }
    
    for (int i = 1; i < array.count; i++) {
        for (int j = 0; j < array.count - i; j++) {
            if ([array[j] compare:array[j+1]] == NSOrderedDescending) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
            
            printf("排序中:");
            [self printArray:array];
        }
    }

}   

2、快速排序
原理：从数列中挑出一个元素，成为“基准”，重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以放在任一边），在这个分区退出之后，该基准就处于数列的中间位置，递归的把小于基准值元素的子数列和大于基准值元素的子数列排序。
OC代码实现：

+ (void)quickSort:(NSMutableArray *)array low:(int)low high:(int)high
{
    if(array == nil || array.count == 0){
        return;
    }
    if (low >= high) {
        return;
    }
    
    //取中值
    int middle = low + (high - low)/2;
    NSNumber *prmt = array[middle];
    int i = low;
    int j = high;
    
    //开始排序，使得left<prmt 同时right>prmt
    while (i <= j) {
//        while ([array[i] compare:prmt] == NSOrderedAscending) {  该行与下一行作用相同
        while ([array[i] intValue] < [prmt intValue]) {
            i++;
        }
//        while ([array[j] compare:prmt] == NSOrderedDescending) { 该行与下一行作用相同
        while ([array[j] intValue] > [prmt intValue]) {
            j--;
        }
        
        if(i <= j){
            [array exchangeObjectAtIndex:i withObjectAtIndex:j];
            i++;
            j--;
        }
    }
    
    if (low < j) {
        [self quickSort:array low:low high:j];
    }
    if (high > i) {
        [self quickSort:array low:i high:high];
    }
}

3、选择排序
原理： 首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾，以此类推，直到所有元素均排序完毕。
OC代码实现：

+ (void)selectSort:(NSMutableArray *)array
{
    if(array == nil || array.count == 0){
        return;
    }
    
    int min_index;
    for (int i = 0; i < array.count; i++) {
        min_index = i;
        for (int j = i + 1; j<array.count; j++) {
            if ([array[j] compare:array[min_index]] == NSOrderedAscending) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:min_index];
            }
      
        }
    }
}

4、插入排序
原理：从第一个元素开始，该元素可以认为已经被排序，取出下一个元素，在已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于新元素，将钙元素移到下一位置，重复以上步骤，直到找到已经排序的元素小于或者等于新元素的位置，将新元素插入到该位置中
OC代码实现：

+ (void)inserSort:(NSMutableArray *)array
{
    if(array == nil || array.count == 0){
        return;
    }
    
    for (int i = 0; i < array.count; i++) {
        NSNumber *temp = array[i];
        int j = i-1;
        
        while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) {
            [array replaceObjectAtIndex:j+1 withObject:array[j]];
            j--;

        }
        
        [array replaceObjectAtIndex:j+1 withObject:temp];
    }
}

5、希尔排序
希尔排序是基于插入排序的以下两点性质而提出的改进方法的：
（1）插入排序在对几乎已经排好序的数据操作时，效率高，既可以达到线性排序的效率。
（2）但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
OC代码实现：

//希尔排序,初始的dk值为array.count/2
- (void)ShellSort:(NSMutableArray *)array dk:(int)dk
{
    
    if(array == nil || array.count == 0||dk>=array.count){
        return;
    }
   
    for (int i = 0; i < array.count; i ++) {
        NSNumber *temp = array[i];
        int j = i - dk;
       
            //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
            while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) {
                [array replaceObjectAtIndex:j+dk withObject:array[j]];
                j-=dk;
            }
            [array replaceObjectAtIndex:j+dk withObject:temp];
        
    }
    
    while (dk>=1) {
        dk = dk/2;
        [self ShellSort:array dk:dk];
    }
}