0x01 选择排序

排序是计算机最为常见的操作之一,排序就是将一组杂乱无章的数据按照一定的规律排序起来(递增或递减),排序的对象可以是数字型,也可以是字符型(按照ASCII码的顺序排列)

  • 选择排序(升序)
    每次在若干无序数据中查找最小数,放在无序数据的首位

    • N个元素的列表中找最小值及下标,与第一个元素交换
    • 从第二个元素开始的N-1个元素中找出最小值及其下标,与第二个元素交换
    • 以此类推,N-1轮后即为排好序的数据

    选择排序

  • 选择排序算法的实现

    # 选择排序
    list = [49, 38, 65, 97, 76, 13, 27, 49]
    for i in range(len(list) - 1):
      m = i
      for j in range(i + 1, len(list)):
          if list[j] < list[m]:
              m = j
      list[i], list[m] = list[m], list[i]
    print(list)
  • 算法分析
    选择排序共需比较N-1轮,总共比较的轮数为(N-1)+(N-2)+...+2+1=N(N-1)/2
    选择排序执行交换的次数是N-1

    0x02 冒泡排序

  • 算法思想

    • 第一轮比较:从第一个元素开始,按照顺序对列表中所有N个元素中连续的两个元素进行两两比较,如果两者不满足升序关系则交换。第一轮比较过后,最大数将下沉到列表最后。
    • 第二轮比较:从第一个元素开始,对列表中前N-1个元素之间进行两两比较,使第二大的数字沉到最后
    • 以此类推,N-1轮后,排序完毕

冒泡排序

  • 冒泡排序算法的实现

    list = [77, 42, 35, 10, 22, 101, 5]
    for i in range(len(list) - 1):
      for j in range(len(list) - 1 - i):
          if list[j] > list[j + 1]:
              list[j], list[j + 1] = list[j + 1], list[j]
    print(list)
  • 冒泡排序算法的改进
    如果在某一轮的比较中,一次交换也没有执行过,就说明已经排好序了

    # 改进
    list = [77, 42, 35, 10, 22, 101, 5]
    for i in range(len(list) - 1):
      flag = True
      for j in range(len(list) - 1 - i):
          if list[j] > list[j + 1]:
              list[j], list[j + 1] = list[j + 1], list[j]
              flag = False
      if flag:
          break
    print(list)
  • 冒泡算法的分析

    • 算法主要时间消耗是比较的次数
    • 冒泡算法共需比较N-1轮,总共比较次数为(N-1)+(N-2)+...+2+1=N(N-1)/2
    • 冒泡排序执行交换的次数不确定
    • 冒泡排序是一种执行效率很低的排序算法

    0x03 函数、递归

  • 函数的好处

    • 在程序中分离不同的任务
    • 实现结构化程序设计
    • 减少程序复杂度
    • 实现代码的复用
    • 提高代码的质量
    • 协作开发
    • 实现特殊功能(递归)
    • .......
  • Python中函数的分类

    • 内置函数
      input()、print()、int()、float()、len()、max()等
    • 标准库函数
      math包中的sqrt()、sin()、cos();random包中的random()等
    • 第三方库函数
    • 自定义库函数
  • 函数

    # 自定义函数的定义
    def 函数名([形参列表]):
      函数体
    # 函数的调用
    函数名([实参列表])
    # 例子:定义一个求平均值的函数
    def average(a, b):
      return (a + b / 2)
    temp = average(1, 3)
    print(temp)
  • 问题:编写一个函数判断一个数是否为素数,并调用其输出200以内的素数

    import math
    def isPrime(a):
      m = int(math.sqrt(a))
      for i in range(2, m + 1):
          if a % i == 0:
              return False
      return True
    for i in range(2, 200):
      if isPrime(i):
          print(i)
  • 问题:将冒泡排序算法写成函数形式

    def bubbleSort(a):
      for i in range(len(a) - 1):
          for j in range(len(a) - 1 - i):
              if a[j] > a[i]:
                  a[j], a[i] = a[i], a[j]
    list = [77, 42, 35, 10, 22, 101, 5]
    bubbleSort(list)
    print(list)
  • 递归函数
    自调用函数,在函数体内部直接或间接调用自己

    # 非递归方法
    def factorial(n):
      s = 1
      for i in range(1, n + 1):
          s = s * i
      return s
    # 递归方法
    def factorial(n):
      if n == 1:
          return 1
      else:
          s = n * factorial(n - 1)
          return s
    print(factorial(3))

0x04 归并排序

  • 算法思想

    • 将包含N个元素的列表拆分成两个含N/2个元素的子列表
    • 对两个子列表递归调用归并排序(最后可将整个列表分为N个子列表)
    • 合并两个已经排序好的子列表

  • 归并排序算法的实现

    def merge(left, right):  # 合并两个列表
      merged = []
      i, j = 0, 0  # i和j分别作为left和right的下标
      left_len, right_len = len(left), len(right)  # 分别获取左右列表的长度
      while i < left_len and j < right_len:  # 循环归并左右子列表元素
          if left[i] <= right[j]:
              merged.append(left[i])  # 归并左子列表元素
              i += 1
          else:
              merged.append(right[j])  # 归并右子列表元素
              j += 1
      merged.extend(left[i:])  # 归并左子列表剩余元素
      merged.extend(right[j:])  # 归并右子列表剩余元素
      print(left, right, merged)  # 跟踪调试
      return merged  # 返回归并好的列表
    def mergeSort(a):  # 归并排序
      if len(a) <= 1:  # 空或者只有一个元素,直接返回列表
          return a
      mid = len(a) // 2  # 列表中间位置
      left = mergeSort(a[:mid])  # 归并排序左子列表
      right = mergeSort(a[mid:])  # 归并排序右子列表
      return merge(left, right)  # 合并排好序的左右两个子列表
    a = [98, 23, 11, 10, 33, 42]
    temp = mergeSort(a)
    print(temp)

    python语言系统提供的排序算法,底层就采用了归并排序算法实现

    a = sorted([24, 8, 10, 35])
    print(a)
    # [8, 10, 24, 35]
    a.sort(reverse=True)
    print(a)
    # [35, 24, 10, 8]
    b = sorted(a)
    print(b)
    # [8, 10, 24, 35]
    c = sorted(a, reverse=True)
    print(c)
    # [35, 24, 10, 8]
Last modification:January 25, 2022
If you think my article is useful to you, please feel free to appreciate