Python3 基本排序算法之冒泡排序，

发布时间：2019-09-24 08:20:11编辑：auto阅读（1533）

    　　基本排序算法按时间复杂度分类

    　　O(n^2)

    　　冒泡排序

    　　插入排序

    　　选择排序

    　　Q(n log n)

    　　分而治之

    　　快速排序

    　　归并排序

    　　冒泡排序

    　　相邻的两个元素对比，大的数后推，遍历整个列表一次后，将最大项以冒泡的方式排列i到列表末尾。

    　　简易版冒泡排序示例如下

    　　def bubble(sl):

    　　"""

    　　冒泡排序，O(n^2)

    　　相邻的两个元素对比，大的后推，遍历整个列表一次后，将最大项以冒泡的方式排列到列表末尾

    　　:param sl: list

    　　:return:

    　　"""

    　　for i in range(len(sl)-1):

    　　for j in range(i+1, len(sl)):

    　　if sl[i] > sl[j]:

    　　sl[i], sl[j] = sl[j], sl[i]

    　　return sl

    　　优化版冒泡排序示例如下

    　　def bubble_sort(items):

    　　"""

    　　冒泡排序, 还是将while循环换为for循环比较习惯

    　　最好 O(n)

    　　最坏 O(n^2)

    　　"""

    　　items_len = len(items)

    　　for i in range(1, items_len):

    　　has_swap = False

    　　for j in range(1, items_len):

    　　if items[j - 1] > items[j]:

    　　has_swap = True

    　　items[j - 1], items[j] = items[j], items[j - 1]

    　　if not has_swap:

    　　break

    　　return items

    　　插入排序

    　　从第二个数开始找前面对应顺序的位置，像插入一张扑克牌顺序一样将其排好顺序。

    　　def insert_sort_for(items):

    　　"""

    　　插入排序，for循环, 中间还是使用while循环容易理解：

    　　比插入的值 大的数挪后，直到不需要挪动为止即为插入的位置。

    　　:param items:　无锡妇科检查多少钱 http://www.csyhjlyy.com/

    　　:return:

    　　"""

    　　for i in range(1, len(items)):

    　　item_insert = items[i]

    　　j = i - 1

    　　while j >= 0:

    　　if item_insert < items[j]:

    　　items[j + 1] = items[j] # 比插入值大的元素，向后移动一位

    　　j -= 1

    　　else: # 不需要挪动时，跳出循环

    　　break

    　　items[j + 1] = item_insert # 找到了插入的位置

    　　return items

    　　选择排序

    　　搜索整个列表，找到最小项位置，列表每一项都会判断其位置是否为最小项。

    　　def select_sort(items):

    　　"""

    　　选择排序, 搜索整个列表，找到最小项位置

    　　"""

    　　for i in range(len(items)-1):

    　　min_index = i

    　　for j in range(i+1, len(items)):

    　　if items[j] < items[min_index]:

    　　min_index = j

    　　if min_index != i:

    　　items[min_index], items[i] = items[i], items[min_index]

    　　return items


关键字：

上一篇： Python练习3：判断学生成绩等级

下一篇： H3C交换机python命令下发脚本