图片源于网络
选择排序
选择排序（Selection Sort）是一种简单直观的排序算法.每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。
算法思想
- 设数组内存放了n个待排数字，数组下标从1开始，到n结束。
- 从数组的第i个元素开始到第n个元素，寻找最小的元素。（具体过程为:先设arr[i]为最小，逐一比较，若遇到比之小的则交换）
- 将上一步找到的最小元素和第i位元素交换。
- 如果i=n－1算法结束，否则重复"从数组的第i个元素开始到第n个元素，寻找最小的元素"的过程
图-选择排序示例图
如图所示，每趟排序中，将当前第 i 小的元素放在位置 i 上。
范例代码
/**
选择排序
@param array 需要排序的Array
*/
+ (void)selectSort:(NSMutableArray *)array{
//遍历数组
/*
选择排序的原理：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
//排序数组
NSMutableArray *originalArray =
[NSMutableArray arrayWithObjects:@9,@1,@2,@5,@7,@4,@8,@6,@3,@5,nil];
*/
NSInteger min = 0;
for (int i=0; i<array.count; i++) {
//先设数组最小值下标为i；
min = i;
for (int j=i+1; j<array.count; j++) {
//待排序数组array[j] < array[min] 其最小值的下标为j
if (array[j]<array[min]) {
min = j;
}
}
//交换数据
if (min != i) {
[array exchangeObjectAtIndex:i withObjectAtIndex:min];
}
}
NSLog(@"选择排序：%@",array);
}
算法分析
-
选择排序算法的性能
选择排序算法的性能
-
时间复杂度
选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 n 个元素，则比较次数总是[n *(n - 1)] / 2。
而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为[3n *(n - 1) ]/ 2。选择排序的最优时间复杂度和最差时间复杂度和平均时间复杂度都为 ：O(n^2) -
空间复杂度
空间复杂度，最优的情况下（已经有顺序）复杂度为：O(0) ；最差的情况下（全部元素都要重新排序）复杂度为：O(n )；平均的时间复杂度：O(1)
-
算法稳定性
选择排序是不稳定的排序方法。（如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。
冒泡排序与选择排序的区别
冒泡排序在内循环交换，选择排序在外循环交换
-
效率差也就在这个交换次数上，毕竟O(n)<O(n^2)。
冒泡排序算法：每次比较如果发现较小的元素在后面，就交换两个相邻的元素。
选择排序算法：先并不急于调换位置，先从A[1]开始逐个检查，看哪个数最小就记下该数所在的位置P，等一躺扫描完毕，再把A[P]和A[1]对调，这时A[1]到A[10]中最小的数据就换到了最前面的位置。
注意:
如果数组完全有序，冒泡内循环的交换一次都不会执行，而选择排序每次还要和本身交换一次，此时冒泡效率高。但这种情况极少，所以仅从算法的角度看，选择优于冒泡
