2016-08-11 •

简单排序算法(OC实现)

排序的目的，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。我们子啊开发过程，从后台拿到的数据有可能是无序列，这就要我们运用一些排序算法，对这些数据进行二次排序。 ** ** 截图2.png ** ** 下面就介绍三种简单排序：

//属性
@interface ViewController ()
@property (weak, nonatomic) IBOutlet UIButton *selectSortBtn;//选择排序
@property (weak, nonatomic) IBOutlet UIButton *insertSortBtn;//插入排序
@property (weak, nonatomic) IBOutlet UIButton *shellSortBtn;//希尔排序
@property (weak, nonatomic) IBOutlet UITextView *resultTextView;//排序过程
@property (weak, nonatomic) IBOutlet UITextView *methodDesTextView;//算法简单描述
@property (nonatomic,assign)double  count;//用于保存运算次数
@property (weak, nonatomic) IBOutlet UIButton *calculateCount;//计算次数

@end

1：选择排序算法选择排序算法就是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。这种算法不会因为数据源是否是有序数组而改变排序计算次数。

//
- (IBAction)selectSort:(UIButton *)sender {
    //排序算法思路
     _count = 0;
    [_calculateCount setTitle:@"交换次数" forState:UIControlStateNormal];
    self.resultTextView.text = @"排序结果:";
    self.methodDesTextView.text = @"算法简介:\n关键点是拿到当前数组的最小的元素跟剩下的元素依次比较\n拿到首个元素，将这个元素的值作为首次遍历时的数组元素的最小值，它的下标记作最小元素的下标\n然后开始从0遍历整个数组，这个最小值跟数组里面的所有值进行比较\n如果在遍历过程中有数组元素的值有比当前记录的最小值,那么就需要变更之前记录的最小值，以及最小值元素的下标\n然后讲当前遍历的首个元素跟记录的最小元素，交换一下位置，如此反复就可以达到排序的效果\n特点：不会因是否有序数组而改变排序计算次数";
    NSArray *array = @[@(13),@(5),@(9),@(12),@(10),@(4),@(1),@(7)];//无序
//    NSArray *array =@[@(1),@(5),@(9),@(12),@(10),@(4),@(7),@(13)];//部分有序
    array = [self selectSort:[array mutableCopy] withStartIndex:0];
}

-(NSMutableArray *)selectSort:(NSMutableArray *)array withStartIndex:(int)start{
    if (start == array.count) {
        return array;
    }
    int minVale = [array[start] intValue];
    int minIndex = start;
    for (int index = start; index < array.count; index++) {
        if (minVale > [array[index] intValue]) {
            minVale = [array[index] intValue];
            minIndex = index;
            _count ++;
        }
    }
    [array exchangeObjectAtIndex:start withObjectAtIndex:minIndex];
    self.resultTextView.text = [self.resultTextView.text stringByAppendingString:[NSString stringWithFormat:@"\nstart:%d--end:%ld--count:%.f:%@",start,array.count,_count,array]];
    array = [self selectSort:array withStartIndex:start + 1];
    return array;
}

2：插入排序算法插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。对于有序数组或部分有序数组，此排序方法是十分高效的。若果最小的元素都在最后部分的位置，那么该排序方法就会变得非常费劲了。

- (IBAction)insertSort:(UIButton *)sender {
     _count = 0;
    [_calculateCount setTitle:@"交换次数" forState:UIControlStateNormal];
    self.resultTextView.text = @"排序结果:";
    self.methodDesTextView.text = @"算法简介:\n始终定义第一个元素为有序的，将元素逐个插入到有序排列之中\n其特点是要不断的移动数据，空出一个适当的位置，把待插入的元素放到里面去\n特点：对于有序数组或部分有序数组，此排序方法是十分高效的\n若果最小的元素都在最后部分的位置，那么该排序方法就会变得非常费劲了";
    NSArray *array =@[@(13),@(5),@(9),@(12),@(10),@(4),@(1),@(7)];//无序
//    NSArray *array =@[@(1),@(5),@(9),@(12),@(10),@(4),@(7),@(13)];//部分有序
    array = [self insertSortArray:[array mutableCopy]];
}

-(NSMutableArray *)insertSortArray:(NSMutableArray *)array{
    for (int i = 1; i < array.count; i ++) {
        int temp = [array[i] intValue];
        int j = i;
        for (; j > 0 && temp < [array[j -1] intValue]; j --) {
            array[j] =  array[j - 1];
            _count ++;
            
        }
        array[j] = @(temp);
        self.resultTextView.text = [self.resultTextView.text stringByAppendingString:[NSString stringWithFormat:@"\nstart-%d--count:%.f:%@",i,_count,array]];  
    }
    return array;
}

3：希尔排序算法希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。希尔排序是直接插入排序算法的一种更高效的改进版本，性能上比选择排序和插入排序快得多,中等大小规模表现良好，对规模非常大的数据排序不是最优选择。

- (IBAction)shellSort:(UIButton *)sender {
    _count = 0;
    [_calculateCount setTitle:@"交换次数" forState:UIControlStateNormal];
    self.resultTextView.text = @"排序结果:";
    self.methodDesTextView.text = @"算法简介:\n希尔排序是直接插入排序算法的一种更高效的改进版本\n使数组中任意间隔为N的元素都是有序的,这样的数组为N有序数组。N有序数组可以看作是N个小的有序数组所构成的一个数组\n记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止\n特点：性能上比选择排序和插入排序快得多,中等大小规模表现良好，对规模非常大的数据排序不是最优选择";
    NSArray *array =@[@(13),@(5),@(9),@(12),@(10),@(4),@(1),@(7)];//无序
//    NSArray *array =@[@(1),@(5),@(9),@(12),@(10),@(4),@(7),@(13)];//部分有序
    [self shellSortArray:[array mutableCopy] withGapH:(int)array.count/2];
}

-(NSMutableArray *)shellSortArray:(NSMutableArray *)array withGapH:(int)gapH {
    
    if (gapH < 1 ) {
       return array;
    }else{
        for (int i = gapH; i < (int)array.count; i++ ) {
            int temp = [array[i] intValue];
            int j = i;
            while (j >= gapH && temp < [array[j - gapH] intValue]) {
                [self exchangeArray:array withNIndex:j andMIndex:j - gapH];
                j -= gapH;
                _count ++;
            }
            array[j] = @(temp);
            
        }
        self.resultTextView.text = [self.resultTextView.text stringByAppendingString:[NSString stringWithFormat:@"\nsortgapH-%d--count:%.f:%@",gapH,_count,array]];
        gapH = gapH/2;
        [self shellSortArray:array withGapH:gapH];
    }
    
    return array;
}

//交换两个元素
-(void)exchangeArray:(NSMutableArray *)array withNIndex:(int)n andMIndex:(int)m{
    int temp = [array[n] intValue];
    array[n] = array[m];
    array[m] = @(temp);
}

本文示例demo链接：OC_SortingAlgorithm 其实还有很多排序算法没有总结，像冒泡排序算法，快速排序算法，堆排序算法，归并排序算法，计数排序算法，桶排序算法，基数排序算法等等。以后也会花一些时间研究一下这些排序算法，给自己多充点电。

Allen Woody

简单排序算法(OC实现)

iOS中NSString的strong、copy的使用

ios8-横屏状态栏不显示解决方法