选择排序是一种简单直观的排序算法。它的工作原理如下:
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 然后,再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步,直到所有元素均排完。
具体步骤如下:
- 初始时,假设第一个元素是最小的。
- 遍历数组,找到当前最小元素的下标。
- 如果当前最小元素的下标不是第一个元素的下标,则交换这两个元素。
- 继续遍历剩余未排序的元素,重复步骤2和步骤3,直到所有元素都有序。
时间复杂度：
选择排序的时间复杂度为O(n^2),因为需要进行n次遍历,每次遍历需要O(n)的时间来找到最小元素。
代码实现如下：
def select_sort_simple(li): # 复杂度是 O(n**2) li_new=[] for i in range(len(li)): min_val=min(li) #找最小值则需要遍历一遍 O(n) li_new.append(min_val) li.remove(min_val) # 删除的时候还需要遍历一遍 O(n) return li_new li=[1,2,5,6,8,7,4,9] print(select_sort_simple(li)) #通常不建议用这种方法 因为时间复杂度较高 #修正好之后 def select_sort(li): #复杂度O(n**2) for i in range(len(li)-1): min_col=i for j in range(i,len(li)): if li[j]<li[min_col]: min_col=j li[i],li[min_col]=li[min_col],li[i] print(li) li = [3,4,2,1,5,6,8,7,9] print(li) select_sort(li)
选择排序的优点是:
- 简单直观,实现容易。
- 不需要额外的存储空间。
- 对输入数据的基本操作是交换,相比于其他排序算法,交换次数较少。
缺点是:
- 时间复杂度较高,不适合处理大规模数据。
- 不稳定,可能会改变相同元素的相对位置。
总的来说,选择排序是一种简单有效的排序算法,适用于小规模数据的排序场景。
