关键点
- 无序区,一开始都是无序区
- 有序区,每次执行完有序区数量不断增大,无序区数量不断减小
- 排序的趟数
每趟遍历从无序区第二个元素开始向后找到最小的元素,和第一个元素交换,使得有序区数量增加1
趟数和每趟无序区下标都从1开始:
第1趟开始
:有序区数量0,无序区数量n,无序区中选择最小值的下标:下标1,下标2,下标3...,下标n
第2趟开始
:有序区数量1,无序区数量n-1,无序区中选择最小值的下标: 下标2,下标3,下标4...,下标n
第3趟开始
:有序区数量2,无序区数量n-2,无序区中选择最小值的下标: 下标3,下标4,下标5...,下标n
第4趟开始
:有序区数量3,无序区数量n-3,无序区中选择最小值的下标: 下标4,下标5,下标6...,下标n
第 i 趟开始
:有序区数量 i-1,无序区数量 n-(i-1)=n-i+1,无序区中选择最小值的下标:下标i,下标i+1,...,下标n
下标一般都是从0开始,趟数和每趟无序区下标都转换成从0开始:
第0趟开始
:有序区数量0,无序区数量n,无序区中选择最小值的下标:下标0,下标1,下标2...,下标n-1
第1趟开始
:有序区数量1,无序区数量n-1,无序区中选择最小值的下标: 下标1,下标2,下标3...,下标n-1
第2趟开始
:有序区数量2,无序区数量n-2,无序区中选择最小值的下标: 下标2,下标3,下标4...,下标n-1
第3趟开始
:有序区数量3,无序区数量n-3,无序区中选择最小值的下标: 下标3,下标4,下标5...,下标n-1
第 i 趟开始
:有序区数量 i,无序区数量 n-i,无序区中选择最小值的下标: 下标i,下标i+1,...,下标n-1
代码实现
#时间复杂度O(n^2)
def select_sort(li):
n = len(li)
for i in range(n-1):#n个数,n-1趟
min_pos = i #记录无序区最小值的位置,即无序区的第一个元素
for j in range(i+1,n):#第i趟时,无序区范围:下标i,下标i+1,...,下标n-1,从无序区范围的第二个开始一直到最后一个,即i+1~n-1,即range(i+1,n)
if li[j] < li[min_pos]:
min_pos = j
li[i], li[min_pos] = li[min_pos], li[i]
排序稳定性
源数据中相同的元素相对顺序保持不变,即稳定排序
3 3 1 5
使用选择排序就是不稳定,第一个1和第二个1排序完相对顺序变了。冒泡是稳定排序。
挨个换的是稳定排序,不挨个换的是不稳定排序
网友评论