选择排序---每次都是最优解
1,思路
选择排序基于一种简单的思路:每一次选择都选最小的,直到把所有的数据都排完。
例如:对于如下【0,9】随机数组
[8, 6, 3, 5, 9, 1, 0, 4, 2, 7]
其排序结果是
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
对于任何数组,下标本身就是一个排序
第一位 |
第二位 |
……… |
第N位 |
那么选择排序的过程是怎样的呢?
简单来说,排序过程就像一个店小二的吆喝,像这样 “谁是第一名,来来来,到这来”,“第二名是哪个,过来,过来...”
过程如下:
① 找到最小的数0,存放在第一位
② 找到第二小的1,存放在第二位
③ 直到排完所有数据.
实际上,选择排序的逻辑是在一个数组中进行的。这样比较省内存。在一个数组中,不可避免的就会出现一个问题,数据交换,过程如下
① 创建临时变量 将5 存入到变量中
② 将第一位赋值为0
③ 将第五位赋值为5
2,代码片段如下
① 交换逻辑
② 选择排序逻辑
③ 排序过程图:
绿色是以完成排序,红色为本次排序交换部分,黑色为无操作部分
3,时间复杂度分析:
对于长度为10的数组:入上图所示
第一行比较了 9 次
第二行比较了 8 次
.
.
.
最后一行比较了1 次;
则总数M=9+8 +……+1
把10换成N,对于任意N长度数组,总比较次数为
N-1+N-2+…+2+1=N*(N-1+1)/2= N2/2
综上,选择排序的时间复杂度为O(N2)
4,特点
选择排序与输入无关,即无论输入数组是正序,倒序,还是乱序,他的时间复杂度都一样。