选择排序(Selection sort) 的基本思想是每一趟在 n – i + 1 (i = 1,2,***,n – 1)个记录中选取关键字最小(或最大)的记录作为有序序列的第 i 个记录,直到所有元素排序完成。选择排序是不稳定的排序算法。
选择排序的时间复杂度为 O(n^2),但性能上略优于冒泡排序。
步骤:
把要排序的序列分为有序序列和无序序列
遍历序列,每一次从无序序列找到最小元素,定义为minIndex=i,放到无序序列最前面,
直到无序区间内没有元素,也就是所有元素都排好序
上面动图中:
橙色表示被排序好的数字
绿色表示迭代过程中的数字
蓝色表示等待排序的数字
红色表示一轮迭代中的minIndex,最小值的索引。
以下是选择排序的Python实现
# 选择排序 def selectionSort(nums): if len(nums) <= 1: return nums
for i in range(0, len(nums)): # 最小值位置索引 minIndex = i for j in range(i + 1, len(nums)): if nums[j] < nums[minIndex]: minIndex = j nums[i], nums[minIndex] = nums[minIndex], nums[i] return nums
# 快速排序 def quicksort(nums): if len(nums) <= 1: return nums
# 左子数组 left = [] # 右子数组 right = [] # 基准数,数组最后一位 base = nums.pop() # 对原数组进行划分 for x in nums: if x < base: left.append(x) else: right.append(x) # 递归调用 return quicksort(right) + [base] + quicksort(left)
发表回复