选择排序

何为选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

n个数的选择排序是一个两重循环的问题：外循环控制求最小值的次数，n个数求最小值，要用n-1次循环;内层循环用来完成求最小值的过程，假定当前元素_array[i]是最小值，假设内循环变量是j(j>=i+1&&j<=n-1) ，让_array[i]与其后的所有元素_array[j]逐个相比较。

 for(NSInteger i = 0; i <  _array.count; i++ ){
        for(NSInteger j = i+1; j < _array.count; j++){
            if(_array[i] > _array[j]){
                [_array exchangeObjectAtIndex:i withObjectAtIndex:j];
            }
        }
    }

改进

虽然上述代码能得到结果，但是还是有缺陷的，对于一个顺序的数组 @[@10,@9,@8,@7,@6,@5,@4,@3,@2,@1]排序的话，元素_array[0]要与后面的每个元素都要比较，这样肯定不行的，那么咱们改进一下：
每次找最小值最多只需要一次交换，即初始位置的元素与最小值元素的交换。这样在找最小值的过程中，就要把最小值的位置标记下来，因此可以定义一个标记变量，来标记本轮比较中最小值的元素，开始假设初始元素最小，将其下标作为标记变量的初始值。然后让后面的所有元素与标记的最小值做比较，如果比最小值还小，只需要更新最小值下标赋值变量。当外层循环结束后，判断标记变量的位置，如果不再指向初始元素，说明最小值不在初始位置，这时，让初始元素与标记变量所标记位置的元素做一次交换，否则不用交换：

for(NSInteger i = 0; i <  _array.count; i++ ){
        NSInteger k = i; //标记变量的初始化，假设初始元素最小
        for(NSInteger j = i+1; j < _array.count; j++){
            if(_array[k] > _array[j]){//如果后面的元素小于最小值，则将其下标赋值给标记变量
                k = j;
            }
        }
        if(k != i){//交换
            [_array exchangeObjectAtIndex:i withObjectAtIndex:k];
        }
    }