- 算法简介
选择排序法 是对 定位比较交换法（也就是冒泡排序法） 的一种改进。选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。
简单选择排序的基本思想：第1趟，在待排序记录r[1]...r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]...r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]...r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
- C语言实现
//下面为升序，降序array[j] > array[min]
void selectSort(int array[],int count) {
int temp;
for (int i = 0; i < count - 1; i++) {
int min = i;
for (int j = i + 1; j < count; j++) {
if (array[j] < array[min]) min = j;
}
if (i != min) {
temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
}
//调用
int number1[7] = {10, 2, 23, 11, 9, 3, 18};
selectSort(number1, 7);
for (i = 0; i < 7; i++) {
printf("%d\n", number1[i]);
}
- OC实现
//下面为升序，降序numbers[j] > numbers[min]
- (void)selectSortWithNumbers:(NSMutableArray *)numbers {
for (int i = 0; i < numbers.count - 1; i++) {
int min = i;
for (int j = i + 1; j < numbers.count; j++) {
if ([numbers[j] intValue] < [numbers[min] intValue]) min = j;
}
if (i != min) {
[numbers exchangeObjectAtIndex:i withObjectAtIndex:min];
}
}
NSLog(@"%@",numbers);
}
//调用
NSMutableArray *array = [NSMutableArray arrayWithObjects:@(10),@(4),@(8),@(6),@(16),@(19),@(3), nil];
[self selectSortWithNumbers:array];
- 时间复杂度
最好、最坏和平均情况下都是O(n²）
- 算法稳定性
选择排序是不稳定的排序方法
