选择排序（Selection Sort）

1. 算法描述

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

• 默认第一个元素问最小元素,并记录当前元素;
• 扫描第一个之后的所有元素和最小元素相比较如果小于最小元素把此元素作为最小元素一趟选择排序下来,找到最小元素下标,如果最小元素和当前元素不相等,则交换当前元素和最小元素；
• 这样第一位元素有序,重复以上步骤;

2. 过程演示

选择排序.gif

原始数据

34 54  12  78 3  45  9  

I = 0;

minIndex = 0;
minIndex = 2;
minIndex = 4;

3  54  12  78 34  45  9  

I = 1;

minIndex = 1;
minIndex = 2;
minIndex = 6;

3  9  12  78 34  45  54 

I = 2;

minIndex = 2;


I = 3;

minIndex = 3;
minIndex = 4;

3  9  12 34  78  45  54 


I = 4;

minIndex = 4;
minIndex = 5;

3  9  12 34  45  78  54 


I = 5;

minIndex = 5;
minIndex = 6;

3  9  12 34  45 54  78 

3. 代码实现

- (NSArray *)selectedSort:(NSArray *)sortArray {
    NSMutableArray *sort = [NSMutableArray arrayWithArray:sortArray];
    NSInteger length = sortArray.count;
    
    NSInteger count1 = 0;// 外层循环次数
    NSInteger count2 = 0;//内层循环次数
    
    NSInteger curentIndex = 0;
    NSInteger minIndex = 0;
    
    for (int i = 0; i < length - 1; i ++) {
        count1 ++;
        curentIndex = i;
        minIndex = i;
        for (int j = i + 1; j < length; j ++) {
            count2 ++;
            if ([sort[minIndex] integerValue] > [sort[j] integerValue]) {
                minIndex = j;
            }
        }
        
        if (curentIndex != minIndex) {
            [sort exchangeObjectAtIndex:curentIndex withObjectAtIndex:minIndex];
        }
    }
    
    NSLog(@"count1 : %ld\n count2 :%ld\n sort: %@",(long)count1,(long)count2,sort);
    return [sort copy];
}

4. 验证

NSArray *arr = @[@34,@54,@12,@78,@3,@45,@9];
 NSArray *arr1 = [self selectedSort:arr];
count1 : 6                    // 外层循环
count2 :21                    // 内层循环
 sort: (
    3,
    9,
    12,
    34,
    45,
    54,
    78
)
一万条数据所用时间
time:3.070174s;