列表排序

路比三人组

冒泡排序

• 列表相邻的两个数，如果前面比后面大，交换这两个数

• 一趟排序完成后，无序列表区减一，有序列表区加一

• 时间复杂度：O(n^2)

• def bubble_sort(li):
      for i in range(len(li)):
          exchange = False  #优化：减少排序次数
          for j in range(len(li)-i-1):
              if li[j] > li[j+1]:
                  li[j],li[j+1] = li[j+1],li[j]
                  exchange = True
          print(li)  # 每一次拍完序打印
          if not exchange:
              return  # 如果已经排序完成，后面都是有序，则不用继续比对，继续排列 如 [9,6,1,2,3,4,5],只比对前三个，减少时间提高效率
  li = [4,3,6,87,8,3,2,6]
  bubble_sort(li)
  

选择排序

• 遍历记录最小的数放在第一位

• 再一趟排序记录列表区最小的数，放在第二个位置

• 算法关键点：有序区，无序区最小数的位置

• 时间复杂度：O(n^2)

• def select_sort(li):
      for i in range(len(li)-1):
          min_loc = i
          for j in range(i+1,len(li)):
              if li[j] < li[min_loc]:
                  min_loc = j
          li[i],li[min_loc] = li[min_loc],li[i]
          print(li)
  
  li = [3,6,8,9,1]
  select_sort(li)
  

插入排序

• 时间复杂度：O(n^2)

• 摸牌规则，摸到一张牌和手上的牌比对，大的放后面，小的放前面

• def insert_sort(li):
      for i in range(1, len(li)): #i 表示摸到的牌的下标
          tmp = li[i]
          j = i - 1  # j指手里牌的下标
          while j >= 0 and tmp < li[j]:
              li[j + 1] = li[j]
              j = j - 1
          li[j + 1] = tmp
          print(li)
  
  li = [3,4,6,2,7,9]
  print(li)
  insert_sort(li)
  

牛逼三人组

快速排序

• 时间复杂度：O(nlogn)

• def partition(li,left,right):
      tmp = li[left]
      while left < right:
          while left<right and li[right] >= tmp: #从右边找比tmp小的数
              right -=1 #往左走一步
          li[left] = li[right] #把右边的值写到左边空位
          while left < right and li[left] <= tmp:
              left +=1
          li[right]  = li[left] #把左边的值写到右边的空位上
      li[left] = tmp
      return left
  
  def quick_sort(li,left,right):
      if left<right: #至少有两个元素
          mid = partition(li,left,right)
          quick_sort(li,left,mid-1)
          quick_sort(li,mid+1,right)
  li = [3,5,6,8,2,9]
  quick_sort(li,0,len(li)-1)
  print(li)