OC算法05：选择排序探索

选择排序

1. 基本思路：选择排序（Selection sort）是最基本的 O(n^2) 的排序算法，它的原理是每一次从待排序的数据元素中 选出最小或最大 的一个元素，存放在序列的起始位置，然后，再从 剩余未排序的元素当中继续寻找最小或大的元素， 然后放到未排序的末尾，以此类推，直到全部待排序的数据元素排完。

2. 稳定性

选择排序是不稳定的排序方法。

3. 主要流程：从小到大

• 第1趟，在待排序记录r[0]~r[n-1]中选出最小的记录，将它与r[0]交换；

• 第2趟，在待排序记录r[1]~r[n-1]中选出最小的记录，将它与r[1]交换；

• 以此类推，第i趟在待排序记录r[i-1]~r[n-1]中选出最小的记录，将它与r[i-1]交换，使有序序列不断增长直到全部排序完毕。

4. 具体代码

- (void)viewDidLoad {
    [super viewDidLoad];
    
    [self selectionSortWithArr:[NSMutableArray arrayWithArray:@[@3,@1,@2,@5,@4]]];
}

// 选择排序
- (void)selectionSortWithArr:(NSMutableArray *)arr{
    // 开始时间
    double startTime = CFAbsoluteTimeGetCurrent();
    // 外层遍历
    for (int i = 0; i< arr.count; i++) {
        int minIndex = i;
        // 内层遍历
        for (int j = i + 1; j < arr.count; j++) {
            // 获取最小下标
            if ([arr[j] intValue]< [arr[minIndex] intValue]) {
                minIndex = j;
            }
        }
        //交换位置
        [arr exchangeObjectAtIndex:i withObjectAtIndex:minIndex];
    }
    double endTime = CFAbsoluteTimeGetCurrent();
    NSLog(@"%@",arr);
    NSLog(@"选择排序用时:%f s",endTime - startTime);
}

查看打印结果

2020-08-26 17:11:21.653476+0800 OC-选择排序[48845:2694230] (
    1,
    2,
    3,
    4,
    5
)
2020-08-26 17:11:21.653672+0800 OC-选择排序[48845:2694230] 选择排序用时:0.000003 s