选择排序

选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

代码实现如下:

@interface DMSelectionSort : NSObject

// 选择排序
- (void)selectionSort:(NSMutableArray *)array;

@end

@implementation DMSelectionSort

- (void)selectionSort:(NSMutableArray *)array
{
    NSLog(@"选择排序前数据：%@", array);
    NSInteger count = [array count];
    for (NSInteger i = 0; i < count - 1; i++) {
        NSNumber *tmpValue = [array objectAtIndex:i];
        NSNumber *minValue = tmpValue;
        NSInteger minIndex = i;
        for (NSInteger j = i + 1; j < count; j++) {
            NSNumber *twoValue = [array objectAtIndex:j];
            if ([minValue integerValue] > [twoValue integerValue]) {
                minValue = twoValue;
                minIndex = j;
            }
        }
        
        if (minIndex != i) {
            // 互换
            [array replaceObjectAtIndex:i withObject:minValue];
            [array replaceObjectAtIndex:minIndex withObject:tmpValue];
        }
    }
    NSLog(@"选择排序后数据：%@", array);
}

@end

@interface DMSortDemo : NSObject

@end

@implementation DMSortDemo

- (void)demo 
{   
    // 选择排序
    DMSelectionSort *selectionSort = [[DMSelectionSort alloc] init];
    {
        NSMutableArray *dataArray = [[NSMutableArray alloc] init];
        [dataArray addObject:[NSNumber numberWithInteger:4]];
        [dataArray addObject:[NSNumber numberWithInteger:5]];
        [dataArray addObject:[NSNumber numberWithInteger:6]];
        [dataArray addObject:[NSNumber numberWithInteger:1]];
        [dataArray addObject:[NSNumber numberWithInteger:3]];
        [dataArray addObject:[NSNumber numberWithInteger:2]];
        [selectionSort selectionSort:dataArray];
    }
    {
        NSMutableArray *dataArray = [[NSMutableArray alloc] init];
        [dataArray addObject:[NSNumber numberWithInteger:3]];
        [dataArray addObject:[NSNumber numberWithInteger:5]];
        [dataArray addObject:[NSNumber numberWithInteger:4]];
        [dataArray addObject:[NSNumber numberWithInteger:1]];
        [dataArray addObject:[NSNumber numberWithInteger:2]];
        [dataArray addObject:[NSNumber numberWithInteger:6]];
        [selectionSort selectionSort:dataArray];
    }
}

@end

首先，选择排序空间复杂度为O(1)，是一种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n * n)。
选择排序是一种不稳定的排序算法。从第一张图可以看出来，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。比如5，8，5，2，9这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素2，与第一个5交换位置，那第一个5和中间的5顺序就变了，所以就不稳定了。