八大排序：
一、直接插入排序

二、希尔排序

三、简单选择排序

四、堆排序

五、冒泡排序

六、快速排序

七、归并排序

八、基数排序

一、直接插入排序

算法步骤：
　　1. 从第一个元素开始，认为该元素已经是排好序的。
　　2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。
　　3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
　　4. 重复步骤3，直到已排好序的元素小于或等于新元素。
　　5. 在当前位置插入新元素。
　　6. 重复步骤2。
　复杂度：
　平均时间复杂度：O(n^2)
　平均空间复杂度：O(1)

/// 从小到大，升序
- (void) sortByInsertWithArray:(NSMutableArray *)array {
    
    /*
     
     算法步骤：
          　　1. 从第一个元素开始，认为该元素已经是排好序的。
          　　2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。
          　　3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
          　　4. 重复步骤3，直到已排好序的元素小于或等于新元素。
          　　5. 在当前位置插入新元素。
          　　6. 重复步骤2。
          　复杂度：
          　平均时间复杂度：O(n^2)
          　平均空间复杂度：O(1)

     */
    
    // 外层for循环从第二个元素，i = 1而不是0。 有n个数字就执行n-1次
    for (int i = 1; i < array.count; i++) {
        
        // 待排元素
        int temp = [array[i] intValue];
        
        // 从后向前扫描，与待排元素比较。
        // 待排元素，大于j元素，不做处理
        // 待排元素，小于j元素，j元素后移，待排元素补上j位置
        for (int j = i - 1; j >= 0; j--) {
            
            if (temp < [array[j] intValue]) {
                
                array[j + 1] = array[j];
                
                array[j] = [NSNumber numberWithInt:temp];
            }
        }
         
    }
    
}

二、希尔排序，非稳定算法

/*
     希尔排序（Shell Sort）也称递增量排序算法，是插入排序的一种更高效的改进版本。但是希尔排序是非稳定算法。
     希尔排序是基于插入排序的以下两个性质提出改进 方法的：
         插入排序在对几乎已经排好的数据操作时，效率高，即可以达到线性排序的效率
         但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
     
     希尔排序的基本思想是：先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体进行依次插入排序。
     
         希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
         希尔排序在插入排序的基础上增加一个叫增量的概念。那么什么是增量？插入排序只能与相邻的元素进行比较，而希尔排序则是进行跳跃比较，而增量就是步长。比如增量为3时，下标为0的元素与下标为3的元素比较，3再与6比较，1与4比较，4再与7比较......比较完后，再去减少增量，重复之前步骤，直到增量为1，此时只有一个分组了，再对这个分组进行插入排序，真个希尔排序就结束了。
     
     
     算法步骤：
     1.选择一个增量序列t1,t2,...,tk,其中ti > tj, tk = 1;
     2.按增量序列个数k，对序列进行k趟排序；
     3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子序列进行插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
     
     用这样增量序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还要快，但是在涉及大量数据时希尔排序还是比快速排序慢。
     
     希尔排序复杂度分析：
     在最坏的情况下时间复杂度仍为0（n^2）,而使用最优的增量在醉话的情况下却为0（n^2/3）需要注意的是，增量序列的最后一个增量值必须等于1才行。另外由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。
     
     */

/// 从小到大，升序
- (void)sortByShellWithArray:(NSMutableArray *)array {
    
    
    int N = (int)array.count;
    // 设置增量，每次递减 / 2
    for (int gap = N / 2; gap > 0; gap /= 2) {
        
        // 直接进行一个插入排序
        [self sortByInsertWithArray:array andGap:gap];
    }
    
    
}

-(NSMutableArray *)sortByInsertWithArray:(NSMutableArray *)array andGap:(NSInteger)gap{
 
    //循环次数，（array.count - gap ）趟
    for (NSInteger i = gap; i < array.count; i ++) {
        
        NSInteger temp = [array[i] integerValue];
        //把当前元素插入到前面去
        for (NSInteger j = i - gap ; j >= 0 ; j -= gap) {
            
            if (temp < [array[j] integerValue]) {
                array[j + gap] = array[j];
                array[j] = [NSNumber numberWithInteger:temp];
            }
        }
    }
    return  array;
}

三、直接选择排序

/**
     
     选择排序
     
     实现步骤：
     1.第一个元素和剩余的元素比较，如果其他的元素小，就交换
     2.第二元素和剩余的元素比较，如果其他的元素小，就交换
     3.重复下去
     
     不稳定，平均时间复杂度0（n^2）
     
     
     
     */

-(void)sortBySelectWithArray:(NSMutableArray *)array {
    
    
    
    int i, j, k;
    
    // 有多少个数字就要执行多少次
    for (i = 0; i <= array.count - 1; i++) {
        
        k = i;
        
        // 第i个元素和剩下的比较
        for (j = i + 1; j <= array.count - 1; j++) {
            
            // 如果剩下的某个元素比第i个元素小，记下下标
            if ([array[k] intValue] > [array[j] intValue]) {
                
                k = j;
            }
        }
        
        // 开始交换
        if (k != i) {
            
            id temp = array[i];
            
            array[i] = array[k];
            
            array[k] = temp;
        }
    }
    
}

四、堆排序

/// 递增
- (void)sortByHeapWithArray:(NSMutableArray *)array {
    
    
}

五、冒泡排序

/// 递增
-(void)sortByBubbleWithArray:(NSMutableArray *)array{
    
    //交换相邻的2个元素，值大的必然会交换到末尾
    //稳定，平均时间复杂度 O(n^2)
    
    //有 array.count -1 趟交换
    for (int i = 0; i< array.count -1 ; i++) {
        
        //内层for循环控制 每趟的 交换次数, 每次递减
        for (int j = 0; j< array.count -1 - i; j++) {
            
            if ([array[j] integerValue] > [array[j + 1] integerValue]) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
}

六、快速排序

/// 递增
-(void)sortByQuickWithArray:(NSMutableArray *)array low:(int )low high:(int )high {
    
    /**
     快速排序：
     思路：
     1.
     
     */
}