选择排序

• 时间复杂度为$O(N^2)$，额外空间复杂度$O(1)$

一句话总结

从前到后依次保证当前最小

Note

选择排序的时间复杂度计算结果为等比数列求和，请自行尝试求解

• 思路 从第1位到最后一位逐位保证当前最小，即 从第1位开始，找到从该位到最后一位中最小的数，并交换到第1位 从第2位开始，找到从该位到最后一位中最小的数，并交换的第2位 … 直到最后一位

• 演示

• 伪代码

  ''' 选择排序，Input: arr (arr.shape = [1, N]) '''
  for i in range(0, N):
  	minNum = min(arr[i:N-1])# 找到i位置到最后的最小值 -> 每个看一眼并比较,约 O(2N)
  	swap(arr[i], minNum)    # 移动到最前 -> 交换两个数 O(1)

• 实际代码

	def selectSort(nums: List[int]) -> List[int]:
    N = len(nums)
    for i in range(0, N):
        minIdx = i
        for j in range(i, N): # 找i-N中的最小值
            if nums[j] < nums[minIdx]:
                # 这里记录最小值的下标，最后再换，能省点时间
                minIdx = j 
        nums = swap(nums, i ,minIdx)
    return nums
 
	def swap(nums: List[int], i: int, j: int) -> List[int]:
	    temp = nums[i]
	    nums[i] = nums[j]
	    nums[j] = temp
	    return nums

笔记

注意代码中是两个循环嵌套，非常慢的 故意没有自带的排序算法，就是为了体现时间复杂度的计算