图解排序 10/10 - 选择排序
选择排序的思想是,依次从「无序列表」中找到一个最小的元素放到「有序列表」的最后面。以 arr = [ 8, 1, 4, 6, 2, 3, 5, 4 ] 为例,排序开始时把 arr 分为有序列表 A = [ ], 无序列表 B = [ 8, 1, 4, 6, 2, 3, 5, 4 ],依次从 B 中找出最小的元素放到 A 的最后面。这种排序也是逻辑上的分组,实际上不会创建 A 和 B,只是用下标来标记 A 和 B。
选择排序
以 arr = [ 8, 1, 4, 6, 2, 3, 5, 4 ] 为例,第一次找到最小元素 1 与 8 进行交换,这时有列表 A = [1], 无序列表 B = [8, 4, 6, 2, 3, 5, 4];第二次从 B 中找到最小元素 2,与 B 中的第一个元素进行交换,交换后 A = [1,2],B = [4, 6, 8, 3, 5, 4];就这样不断缩短 B,扩大 A,最终达到有序。
代码
+ (NSArray *)seelectSort:(NSArray *)unsortDatas {
NSMutableArray *unSortArray = [unsortDatas mutableCopy];
for (int i = 0; i < unSortArray.count; i++) {
int mindex = i;
for (int j = i; j < unSortArray.count; j++) {
// 找到最小元素的index
if ([unSortArray[j] integerValue] < [unSortArray[mindex] integerValue]) {
mindex = j;
}
}
// 交换位置
NSNumber *data = unSortArray[i];
unSortArray[i] = unSortArray[mindex];
unSortArray[mindex] = data;
}
return [unSortArray copy];
}
特点
稳定性:排序过程中元素是按顺序进行遍历,相同元素相对位置不会发生变化,故稳定。
空间复杂度:在原序列进行操作,故为 O( 1 );
时间复杂度:需要 2 次循环遍历,故为 O( n * n );
感想
选择排序与冒泡排序,插入排序都属于同一思想排序,这种排序算法思想简单,往往会用于其它复杂排序算法的子序列排序。
推荐阅读:
超越技术