1、插入排序--直接插入排序

要求在一个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这中方法叫做插入排序

//插入排序
- (NSArray *)inserSort:(NSArray *)arr{
    
    //首先建立一个空表，表示这个有序集合
    NSMutableArray *newArr = [NSMutableArray array];
    //将数组中第一个元素放入新列表，当做有序集合的第一个元素
    [newArr addObject:[arr firstObject]];
    
    //遍历需要排序的数组获取排序元素
    for (int j = 1; j < arr.count; j++) {
        NSInteger srcObj = [arr[j] integerValue];
        //遍历新数组，找到对应位置放置排序元素
        for (int i = 0; i < newArr.count; i++) {
            NSInteger obj = [newArr[i] integerValue];
            if (srcObj <= obj) {
                [newArr insertObject:@(srcObj) atIndex:i];
                break;
            }else if (i == newArr.count-1){
                [newArr addObject:@(srcObj)];
                break;//不加break，你通过addobject改变了newArr.cout的值，所以会有两个当前最大值
            }
        }
    }
    return [newArr copy];
}

上述例子中是直观的使用了两个数组进行排序，其实换一种想法，可以从原数组的第一个元素开始当做一个已经排好序的数组，然后依次取后面一位数据，插入到前面数组，使得第i次排序后数组的第i个元素之前有事有序的。

2、插入排序--希尔排序

希尔排序：希尔排序的思想是将数组以一定间隔分成多个子数组，然后分别对子数组进行插入排序，排完序之后在减少间隔数，分割成新的子数组，然后再对新的子数组进行排序，知道间隔为1时，对最后的数组进行排序

//希尔排序
- (void)shellSort:(NSMutableArray *)arr{
    
    NSInteger gap = arr.count/2;
    
    //将大的数组，按间隔分成若干个小数组，先对小数组进行插入排序，最后整体排序
    while (1 <= gap) {
        
        for (NSInteger i = gap; i < arr.count; i++) {
            NSInteger j = i - gap;
            //需要排序的数
            NSInteger tmpValue = [arr[i] integerValue];
            //每次遍历完之后，就是从小到大的顺序位置，只要小，就把当前数字后移，这里就是tmpvalue的位置， j+gap 的位置就是tmpValue适合的位置，
            while (j >= 0 && tmpValue < [arr[j] integerValue]) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j+gap] = @(tmpValue);
        }
        gap /= 2;
    }
}

3、选择排序--简单选择排序

选择排序：每次从待排数组中找出最小的一个元素，将其放入顺序数组中的最后面，直到排完所有元素。

//选择排序
- (void)selectSort:(NSMutableArray *)marr{
    
    //有n个待排数字的数组
    //NSMutableArray *marr = [arr mutableCopy];
    //从寻找最小数字的次数
    for (int i = 0; i < marr.count; i++) {
        NSInteger minIndex = i;
        for (int j = i; j < marr.count; j++) {
            //找到后面最小元素下标
            NSInteger min = [marr[minIndex] integerValue];
            NSInteger current = [marr[j] integerValue];
            if (current < min) {
                minIndex = j;
            }
        }
        //将最小的元素放在前面
        [marr exchangeObjectAtIndex:minIndex withObjectAtIndex:i];
    }
    //NSLog(@"%@",marr);
}

4、选择排序--二元排序

二元排序：与简单选择排序差不多，简单选择排序是每次循环找出最小的值，而二元排序则是每次循环不但找出最小的值，还顺便找出最大的值，减少了循环的次数

//选择排序--二元排序
- (void)selectSort2:(NSArray *)arr{
    
    //有n个待排数字的数组
    NSMutableArray *marr = [arr mutableCopy];
    //从寻找最小和最大数字的次数
    for (int i = 0; i < marr.count/2; i++) {
        NSInteger minIndex = i;
        NSInteger maxIndex = marr.count-i-1;
        for (int j = i; j < marr.count-i; j++) {
            //找到后面最小和最大元素下标
            NSInteger min = [marr[minIndex] integerValue];
            NSInteger max = [marr[maxIndex] integerValue];
            NSInteger current = [marr[j] integerValue];
            if (current < min) {
                minIndex = j;
                continue;
            }
            if (current > max) {
                maxIndex = j;
            }
        }
        //将最小和最大的元素放在对应位置
        [marr exchangeObjectAtIndex:minIndex withObjectAtIndex:i];
        [marr exchangeObjectAtIndex:maxIndex withObjectAtIndex:marr.count-i-1];
    }
    //NSLog(@"%@",marr);
}

5、选择排序--堆排序

堆：这个‘堆’是指数据结构中的堆，首先满足一个完全二叉树结构，并且满足条件1、堆中所有根节点的数值都大于（或小于，都大于叫大根堆，都小于叫小根堆）子节点的数值，2、堆中任意子树还是堆。
堆在程序中的表达就可以用数组去表示，按照MLR的遍历方式顺序放入数组中，
堆排序算法：首先在数组中构建一个完整的大根堆，然后将堆中最大的数放入数组末尾，然后以n-1的数组n为原数组长度，调整大根堆，使其再次从n-1个数组中最大的数在堆的根节点上，重复放入n-1的位置，循环上述步骤，直至排完。

//选择排序———堆排序
- (void)heapSort:(NSMutableArray *)marr{
    
    //第i个节点的父节点为(i-1)/2
    //左右子节点为(2*1)+1 、 (2*1)+2
    //二叉堆：父节点的键值总是大于，或小于任何一个子节点的键值，每一个左右子树也都是二叉堆
    
   //NSMutableArray *marr = [arr mutableCopy];
    
    NSInteger (^getChildLeftIndex)(NSInteger current) = ^NSInteger(NSInteger current){
        return 2*current+1;
    };
    NSInteger (^getChildRightIndex)(NSInteger current) = ^NSInteger(NSInteger current){
        return 2*current+2;
    };
    NSInteger (^getParentIndex)(NSInteger current) = ^NSInteger(NSInteger current){
        return (current-1)/2;
    };
    //构建一个最大堆（根节点值大于子节点值），比较当前节点的左右节点是否大于自身，如果大就交换，并别重排交换过后的子节点
    __block void(^MaxHeapBlock)(NSMutableArray *marr,NSInteger length,NSInteger current) = ^void(NSMutableArray *marr,NSInteger length,NSInteger current){
    
        NSInteger left = getChildLeftIndex(current);
        NSInteger right = getChildRightIndex(current);
        
        NSInteger largest = current;
        if (left<length && [marr[left] integerValue] > [marr[largest] integerValue]) {
            largest = left;
        }
        if (right<length && [marr[right] integerValue] > [marr[largest] integerValue]) {
            largest = right;
        }
        
        if (largest != current) {
            [marr exchangeObjectAtIndex:current withObjectAtIndex:largest];
            MaxHeapBlock(marr,length,largest);
        }
    };
    //其实是从子节点开始排，一直排到根节点,构建一个完整的最大堆
    for (NSInteger i = marr.count-1; i>=0; i--) {
        MaxHeapBlock(marr,marr.count,i);
    }
    
    //将根节点的数字放入数组最末尾，然后按照去掉一个末尾元素的数组重新构建一个最大堆
    for (NSInteger i = marr.count-1; i>0; i--) {
        [marr exchangeObjectAtIndex:i withObjectAtIndex:0];
        MaxHeapBlock(marr,i,0);
    }
    
}

6、交换排序--冒泡排序

冒泡排序：两两比较，前面比后面大就交换，双for循环，外层循环控制的是拍出最大数的次数，内层循环是保证大数是比较了数组中所有元素得出的。双向冒泡排序就是个鸡肋，本来内层for循环的终止条件是marr.coun-1,但是加上一个-i效果和双向冒泡排序是一致的。

//冒泡排序
- (void)popSort:(NSArray *)arr{
    
    NSMutableArray *marr = [arr mutableCopy];
    
    NSInteger exchangeCount = 0;
    NSInteger loopCount = 0;
    
    //排序次数
    for (int i = 0; i < marr.count; i++) {
        //从列表中第一个数字到最后一个没有拍好的数字
        for (int j = 0; j < marr.count-i-1; j++) {
            //如果前面的大于后面的，就交换
            NSInteger first = [marr[j] integerValue];
            NSInteger seconde = [marr[j+1] integerValue];
            if (first > seconde) {
                [marr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
                exchangeCount++;
            }
            loopCount++;
        }
    }
    
    NSLog(@"冒泡 changeCount%zd   loopCount%zd",exchangeCount,loopCount);
}

7、交换排序--快速排序

快速排序：通过从数组中选取一个关键值，使数组分成两个部分，一部分里面所有元素都小于关键值，另一部分所有元素都小于关键值。然后在分别对分出的两个数组在进行类似操作，知道分到不能再分。

//快速排序1
- (NSArray *)quickSort:(NSArray *)arr{
    
    if (arr.count <= 1) {
        return arr;
    }
    //将第一个数当做中间数
    NSInteger firstObj = [[arr firstObject] integerValue];
    //左边都是小于中间数的数组
    NSMutableArray *leftMarr = [NSMutableArray array];
    //右边都是大于中间数的数组
    NSMutableArray *rightMarr = [NSMutableArray array];
    
    //将原数组中的数据和中间数进行比较得出左右两边数组
    for (int i = 1; i < arr.count; i++) {
        if ([arr[i] integerValue]<firstObj) {
            [leftMarr addObject:arr[i]];
        }else{
            [rightMarr addObject:arr[i]];
        }
    }
    NSMutableArray *marr = [NSMutableArray array];
    [marr addObjectsFromArray:[self quickSort:leftMarr]];
    [marr addObject:@(firstObj)];
    [marr addObjectsFromArray:[self quickSort:rightMarr]];
    return [marr copy];
}

//快速排序2  这个比快排1快一倍
- (void)quickSort2:(NSMutableArray *)marr LeftIndex:(NSInteger)left RightIndex:(NSInteger)right{
    
    if (right <= left) {
        return;
    }
    NSInteger headIndex = left;
    NSInteger footIndex = right;
    NSInteger key = [[marr objectAtIndex:left] integerValue];
    
    //判断有没有找完
    while (headIndex < footIndex) {
        
        
        while ([marr[footIndex] integerValue] >= key && headIndex < footIndex)  {
            footIndex--;
        }
        marr[headIndex] = marr[footIndex];
        while ([marr[headIndex] integerValue] <= key && headIndex < footIndex) {
            headIndex++;
        }
        marr[footIndex] = marr[headIndex];
        
    }
    marr[headIndex] = @(key);
    [self quickSort2:marr LeftIndex:left RightIndex:headIndex-1];
    [self quickSort2:marr LeftIndex:headIndex+1 RightIndex:right];
}

8、归并排序

归并排序：是将数组切分成若干个小数组，分别对若干个小数组进行排序，然后，依次合并小数组，并重新排序，重复合并小数组，最后合并成一个数组,看似与希尔排序一样，但是切分小数组的形式不一样，希尔排序是间隔区分数组，而归并排序是按照相邻两个元素为一个数组，排序后就将排序后的数组看成一个元素进行合并

- (void)mergeSort:(NSMutableArray *)marr{
    
    /*
     归并排序：是将数组切分成若干个小数组，分别对若干个小数组进行排序，然后，依次合并小数组，并重新排序，重复合并小数组，最后合并成一个数组
     */
    NSMutableArray *hmarr = [NSMutableArray array];
    
    
    __block void(^SortArr)(NSMutableArray *srcArr,NSMutableArray *desArr,NSInteger head,NSInteger foot,NSInteger middle) = ^void(NSMutableArray *srcArr,NSMutableArray *desArr,NSInteger head,NSInteger foot,NSInteger middle){

        for (NSInteger i = head; i<=foot; i++) {
            desArr[i] = srcArr[i];
        }
        NSInteger helpLeft = head;
        NSInteger helpRight = middle+1;
        NSInteger current = head;
        //对数组整体排序，遍历整个数组，分别从两边的数组中获取最小的放到对应位置
        while (helpLeft <= middle && helpRight<= foot) {
            if ([desArr[helpLeft] integerValue] <= [desArr[helpRight] integerValue]) {
                srcArr[current] = desArr[helpLeft];
                helpLeft++;
            }else{
                srcArr[current] = desArr[helpRight];
                helpRight++;
            }
            current++;
        }
        //这个表示前面先排完，那么后面数组的大数肯定是合适的
        if (middle-helpLeft < 0) {
            return;
        }
        
        //表示前面那一个数组在排序中大于后面数组最大值剩余的个数，都添加到数组末尾去
        for (NSInteger i = 0; i <= (middle-helpLeft); i++) {
            srcArr[current+i] = desArr[helpLeft+i];
        }
    };
    
    //无限对半分割数组
    __block void(^MergeSortTwoArr)(NSMutableArray *srcArr,NSMutableArray *desArr,NSInteger head,NSInteger foot) = ^void(NSMutableArray *srcArr,NSMutableArray *desArr,NSInteger head,NSInteger foot){
        
        if (head < foot) {
            NSInteger middle = (foot - head)/2 + head;
            MergeSortTwoArr(srcArr, desArr, head, middle);
            MergeSortTwoArr(srcArr, desArr, middle+1, foot);
            SortArr(srcArr,desArr,head,foot,middle);
            
        }
    };
    
    MergeSortTwoArr(marr,hmarr,0,marr.count-1);
    NSLog(@"%@",marr);
    
}

9、基数排序

基数排序：这个是最简答的，看了下概念，想都没想就写出来了，将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

//基数排序
- (void)baseSort:(NSArray *)arr Count:(NSInteger)count{
   
    NSInteger base = 1;//比较的位数
    NSMutableArray *srcMarr = [arr mutableCopy];
    NSMutableArray *marr = [NSMutableArray array];//放位数的二维数组
    
    /*
        先按照个位数排序，然后按照十位数排序，最后按照最高位排序
     */
    
    //最大的数的位数决定这层循环次数
    while (base<=count) {
        
        //为了取得对应位数上面的值
        NSInteger baseCount = 1;
        for (int i = 1; i < base; i++) {
            baseCount*=10;
        }
        //创建按照对应位数值的二维数组
        [marr removeAllObjects];
        for (int i = 0; i < 10; i++) {
            NSMutableArray *bitarr = [NSMutableArray array];
            [marr addObject:bitarr];
        }
        //根据位数值，放入对应二维数组
        for (NSNumber *value in srcMarr) {
            [marr[([value integerValue]/(baseCount))%10] addObject:value];
        }
        
        //直接拼接二维数组中的值
        [srcMarr removeAllObjects];
        for (NSArray *tmparr in marr) {
            [srcMarr addObjectsFromArray:tmparr];
        }
        base++;
    }
    NSLog(@"%@",srcMarr);
}