简单排序算法(OC实现)

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

---

截图1.png

---

截图2.png

---

截图3.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
其实还有很多排序算法没有总结，像冒泡排序算法，快速排序算法，堆排序算法，归并排序算法，计数排序算法，桶排序算法，基数排序算法等等。以后也会花一些时间研究一下这些排序算法，给自己多充点电。