冒泡排序

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

• 思路：起点从第一位到最后一位，相邻两位比较，大的换到右边。 从第1位开始，到最后一位，滑窗向右两两比较，大的换到右边 从第1位开始，到倒数第二位，滑窗向右两两比较，大的换到右边 … 直到第1位结束

• 演示

• 伪代码

  '''冒泡排序'''
  # 滑窗起点，向右走（窗口大小为2）
  for i in range(0,N):
          # 滑窗终点
  		for j in range(0, N-i):
  		    # 两两比较，大的换到右边
  			if arr[j] > arr[j+1]:
  				swap(arr[j], arr[j+1])

• 实际代码

  def bubbleSort(nums: List[int]) -> List[int]:
  N = len(nums)
  for i in range(0, N):
      for j in range(1,N-i):
          if nums[j-1] > nums[j]:
              temp = nums[j]
              nums[j]=nums[j-1]
              nums[j-1]=temp
  return nums