vlambda博客
学习文章列表

图解排序 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 );


感想

选择排序与冒泡排序,插入排序都属于同一思想排序,这种排序算法思想简单,往往会用于其它复杂排序算法的子序列排序。


推荐阅读:



超越技术