简单选择排序算法

在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。

最坏情况下，即待排序记录初始状态是按第一条记录最大，之后的记录从小到大顺序排列，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n^2)，进行移动操作的时间复杂度为O(n)。

简单选择排序是不稳定排序。

image.png

每一趟选出最小的数放到前面

NSMutableArray *arrSort = [NSMutableArray arrayWithArray:@[@(7), @(3), @(15), @(5), @(11), @(2), @(4), @(9), @(6)]];

- (void)selectionSort:(NSMutableArray *)arrSort {
    int i ;
    for (i = 0; i < arrSort.count-1; i++) {
        int temp = 0;
        for (int j = i + 1; j < arrSort.count; j++) {
            if (arrSort[j] < arrSort[i]) {
                temp = [arrSort[j] intValue];
                arrSort[j] = arrSort[i];
                arrSort[i] = @(temp);
            }
        }
    }
    NSLog(@"%@",arrSort);
}

第0趟：  2 7 15 5 11 3 4 9 6
第1趟：  2 3 15 7 11 5 4 9 6
第2趟：  2 3 4 15 11 7 5 9 6
第3趟：  2 3 4 5 15 11 7 9 6
 第4趟：  2 3 4 5 6 15 11 9 7
第5趟：  2 3 4 5 6 7 15 11 9
第6趟：  2 3 4 5 6 7 9 15 11
 第7趟：  2 3 4 5 6 7 9 11 15