冒泡法

  • 冒泡法
    • 冒泡法属于交换排序
    • 两两比较大小，交换位置
    • 结果分为升序和降序排列

示例：

  1. # num_list = [1, 9, 2, 5, 7, 2, 8, 5, 4, 3]
  2. num_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
  4. count = 0  # 统计循环的次数
  5. count_swap = 0  # 统计交换的次数
  6. length = len(num_list)
  7. for i in range(length):
  8.     flag = False  # 设置标志位
  9.     for j in range(length - i - 1):  # 边界考虑，每轮比较后最大的数字排在最右边，因此下次就就无需再次比较，故可使用length-i来排除，后面比较时已经是比较当前索引和后一个索引的大小，因此-1是为了防止越界
  10.         count += 1
  11.         if num_list[j] > num_list[j + 1]:
  12.             flag = True  # 如果此判断进不来，说明最近的两个值的顺序就是我们需要的，因此修改标志位
  13.             num_list[j], num_list[j + 1] = num_list[j + 1], num_list[j]  # 封装解构
  14.             count_swap += 1
  15.     if not flag:  # 当一轮循环结束，标志位没有被修改，说明当前顺序就是我们需要的，可终止循环
  16.         break
  18. print(num_list, count, count_swap)
  • 总结
    • 冒泡法数据需要一轮轮比较
    • 可以设定一个标记判断此轮数据是否发生交换，如果没有可结束此轮排序
    • 时间复杂度为O(n2)

选择排序

  • 选择排序
    • 两两比较大小，找出极值（最大值最小值）放在固定位置索引上
    • 结果分为生序或者降序
  1. # 算法一
  2. m_list = [1, 9, 5, 4, 2, 7, 3, 8, 6]
  4. length = len(m_list)
  6. for i in range(length):
  7.     maxindex = i
  8.     for j in range(i + 1, length):
  9.         if m_list[maxindex] < m_list[j]:
  10.             maxindex = j
  12.     if i != maxindex:
  13.         m_list[i], m_list[maxindex] = m_list[maxindex], m_list[i]
  15. print(m_list)
  1. 算法二：折半计算，优化效率
  2. m_list = [1, 9, 3, 2, 7, 5, 8, 4, 6]
  4. length = len(m_list)
  6. # 每次计算出最大值和最小值，折半计算
  7. for i in range(length // 2):
  8.     maxindex = i
  9.     minindex = -i - 1
  10.     minorigin = minindex
  11.     for j in range(i + 1, length - i):  # 每次循环左右各少比较一个
  12.         if m_list[maxindex] < m_list[j]:
  13.             maxindex = j
  14.         if m_list[minindex] > m_list[-j - 1]:
  15.             minindex = -j - 1
  17.     print(maxindex, minindex)
  18.     if m_list[maxindex] == m_list[minindex]:  # 如果最大值和最小值相同，则跳出
  19.         break
  21.     if i != maxindex:
  22.         m_list[i], m_list[maxindex], = m_list[maxindex], m_list[i]
  23.         # 如果最小值被交换过，则更新索引
  24.         if i == minindex or i == length + minindex:
  25.             minindex = maxindex
  27.     if minorigin != minindex:
  28.         m_list[minindex], m_list[minorigin] = m_list[minorigin], m_list[minindex]
  30. print(m_list)

插入排序

直接插入排序

  • 原理
    • 在未排序序列中，构建一个子排序序列，直至所有数据排序完成
    • 将待排序的数据，插入到已排序的序列中合适的位置
    • 增加一个哨兵，放入待比较值，让它和后面已经排好序的序列比较，找到合适的插入点
  • 图示

image-20190808103720464

  • 上图中分为三个区域
    • 红色字体代表哨兵，即待插入值
    • 初始状态的1为假定的有序序列区
    • 剩余的无序区
  1. nums = [1, 9, 3, 2, 7, 5, 8, 4, 6]
  2. nums = [0] + nums  # 增加初始哨兵位，每轮将待比较的数据放入哨兵位
  4. length = len(nums)
  5. for i in range(2, length):
  6.     nums[0] = nums[i]  # 将待比较的数据放置在哨兵位
  7.     j = i - 1   # 获取有序序列中待比较的数据
  8.     if nums[j] > nums[0]:   # 大于哨兵位的右移，找到插入的位置
  9.         while nums[j] > nums[0]:  # 比较哨兵位和有序序列中的值
  10.             nums[j + 1] = nums[j]  # 如果有序序列的值大于哨兵位，则右移位置
  11.             j -= 1   # 依次判断有序序列
  12.         nums[j + 1] = nums[0]   # 将哨兵插入，因判断有序序列时减1，因此此时需要在右侧加1
  13. print(nums[1:])