常见算法总结

一、选择排序：
1、首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2、再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3、重复第二步，直到所有元素均排序完毕。

- (void)selectPaiXu{
    NSMutableArray *arr_M = [NSMutableArray arrayWithObjects:@1,@4,@2,@3,@5,nil];

 
    for (int i=0; i<arr_M.count; i++) {
        
        for (int j=i+1; j<arr_M.count; j++) {
     
            if (arr_M[i]<arr_M[j]) {
               //此种交换思想首先是找出来一个较大的数A，放到第一个位置，然后再用A比对所有的数，就这样遇到比自己大的数就交换，当第一次遍历完成之后就会找出最大的数在第一个位置。  然后，开始从数据的第二个值开始遍历寻找第二小的数，以此类推可以排序出来。
                [arr_M exchangeObjectAtIndex:i withObjectAtIndex:j];
               
            }
        }
        
    }
    //打印结果  @[@5,@4,@3,@2,@1];
    NSLog(@"选择排序结果：%@",arr_M);
}

二、冒泡排序
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
每一次都会遍历所有的数进行相邻比较。

- (void)maoPaoPaiXu{
    NSMutableArray *arr_M = [NSMutableArray arrayWithObjects:@1,@4,@2,@3,@5,nil];
    for (int i = 0; i < arr_M.count; ++i) {
        
        //遍历数组的每一个`索引`（不包括最后一个,因为比较的是j+1）
        for (int j = 0; j < arr_M.count-1; ++j) {
            
            //根据索引的`相邻两位`进行`比较`
            if (arr_M[j] < arr_M[j+1]) {
                
                [arr_M exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
    NSLog(@"冒泡排序最终结果：%@",arr_M);
}

三、插入排序
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
场景：生活中常用的场景就是打扑克牌。
算法步骤：
1、将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2、从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
使用情况：直接插入排序适合记录数比較少、给定序列基本有序的情况。

- (void)insertPaiXu{
    NSMutableArray *arr_M = [NSMutableArray arrayWithObjects:@8,@4,@2,@3,@5,@7,nil];
    for (NSInteger i = 1; i < arr_M.count; i ++) {
        NSInteger temp = [arr_M[i] integerValue];
        for (NSInteger j = i - 1; j >= 0 && temp < [arr_M[j] integerValue]; j --) {
            arr_M[j + 1] = arr_M[j];
            arr_M[j] = [NSNumber numberWithInteger:temp];
        }
        //输出插入数据的步骤，查看内部思维方式  后一个数据对比前面的一个数据，刷新数组，然后原数组索引再次减一对比，例如index3替换index2，刷新变成index1,index3,index2,再次循环对比index1,index3，这样就能排出顺序了。
    }
    NSLog(@"插入升序排序结果：%@",arr_M);
    
}

四、快速排序
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
大致来说它才去的是一种分而治之的处理方式，用一个数不断地对数据进行分块处理。
使用场景：较大数据的排序，排序快、效率高。

终级思想：选一个比较值A，然后从数组左右两边开始查找，比A大的数放到A的右边，比A小的数放到A的左边，具体的方法就是和A互换值。

#pragma - mark 快速排序 包含相同数据的处理  https://www.jianshu.com/p/34e920acfe1c
- (void)quickSort:(NSMutableArray *)array low:(int)low high:(int)high
{
    if(array == nil || array.count == 0){
        return;
    }
    if (low >= high) {
        return;
    }
    
    //取中值     排序前:9 2 10 7 3 7 4
    int middle = low + (high - low)/2;
        NSLog(@"打印出middle:%d",middle);

    //用中值作为分界线
    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--;
        }
        //i&j都在向中间逼近
        if(i <= j){
            [array exchangeObjectAtIndex:i withObjectAtIndex:j];
            i++;
            j--;
        }
        
        printf("排序中:");
        NSLog(@"快速排序之后的数据位：%@",array);
//        [self printArray:array];
    }

    if (low < j) {
        [self quickSort:array low:low high:j];
    }
    if (high > i) {
        [self quickSort:array low:i high:high];
    }
}

五、堆排序
堆的定义：一个完全二叉树中，任意父结点总是大于或等于（小于或等于）任何一个子节点，则为大顶堆（小顶堆）。
利用堆顶记录的是最大关键字这一特性，每一轮取堆顶元素放入有序区，就类似选择排序每一轮选择一个最大值放入有序区，可以把堆排序看成是选择排序的改进。

将初始待排序关键字序列(R0,R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[0]与最后一个元素R[n]交换，此时得到新的无序区(R0,R1,R2,......Rn-1)和新的有序区(Rn)；
由于交换后新的堆顶R[0]可能违反堆的性质，因此需要对当前无序区(R0,R1,R2,......Rn-1)调整为新堆。
不断重复此2、3步骤直到有序区的元素个数为n-1，则整个排序过程完成。

- (void)duiPaiXu{  
    NSMutableArray *dataArr = [NSMutableArray arrayWithObjects:@1,@19,@2,@65,@876,@0,@63,@-1,@87,@100,@-5,@100,@333, nil];
    
    /*
     从最后一个非叶子节点开始 自下而上进行调整堆（将以i为根节点的二叉树通过筛选调整为堆）    
     */
    for (NSInteger i=(dataArr.count/2-1); i >= 0; --i) {
        NSLog(@"-----------子叶节点：%ld",(long)i);
        dataArr = [self maxHeapAdjust:dataArr index:i length:dataArr.count] ;
    }
    
    NSInteger num = dataArr.count;
    /*
     剩余的元素个数不为1时则继续调整，取出元素。取出的元素放在最后的一个节点。然后减小堆的元素的个数。所以大顶堆排序出来的是升序的。
     */
    while (num > 1) {
        [dataArr exchangeObjectAtIndex:0 withObjectAtIndex:num-1];
        dataArr=[self maxHeapAdjust:dataArr index:0 length:num-1];
        num--;
    }
    NSLog(@"堆排序-----%@",dataArr);

}

- (NSMutableArray*)maxHeapAdjust:(NSMutableArray *)array index:(NSInteger)index length:(NSInteger)length {
    NSInteger leftChildIndex =index*2+1;//获取该节点的左子节点索引
    NSInteger rightChildIndex=index*2+2;//获取该节点的右子节点索引
    NSInteger maxValueIndex=index;//暂时把该索引当做最大值所对应的索引

    NSLog(@"index------:%ld------leftChildIndex:%ld-------rightChildIndex:%ld",index,leftChildIndex,rightChildIndex);
    // leftChildIndex < length
    // 判断左子节点的值是否大于当前最大值  length是数组的长度
    if (leftChildIndex < length && [array[leftChildIndex] integerValue] > [array[maxValueIndex] integerValue]) {
        //把左子节点的索引作为最大值所对应的索引
        maxValueIndex=leftChildIndex;
    }
    // rightChildIndex < length
    // 判断右边子节点的值是否大于当前最大值
    if (rightChildIndex < length && [array[rightChildIndex] integerValue] > [array[maxValueIndex] integerValue]) {
        maxValueIndex=rightChildIndex;
    }
    
    //如果该节点不是最大值所在的节点 则将其和最大值节点进行交换
    if (maxValueIndex != index) {
        [array exchangeObjectAtIndex:maxValueIndex withObjectAtIndex:index];
        NSLog(@"调整节点之后的数组为：%@",array);
        //递归向下调整，此时maxValueIndex索引所对应的值是 刚才的父节点。
        array=[self maxHeapAdjust:array index:maxValueIndex length:length];
    }
    return array;
}

GitHub地址：https://github.com/caiqingchong/SuanFaDemo
参考文章：
https://www.jianshu.com/p/34e920acfe1c
https://www.cnblogs.com/ZachRobin/p/7094852.html