环境

Python 3.5.2

原理

  • 在列表中挑选出一个基准值
  • 将列表中的其它元素与基准值对比,比基准值大的放在基准值右侧,比基准值小的放在基准值左侧
  • 以此类推

源码

def quick_sort(l, start, end):
    if start >= end:
        return

    low = start
    high = end
    mid_value = l[low]

    while low < high:
        # low<high这个条件必须在这里再次体现,避免出现循环过程中low>high的情况
        while low < high and l[high] >= mid_value:
            high -= 1
        # 当中间值右侧的值小于中间值时,将该值赋值于l[low](原来的值已保存至mid_value变量)
        l[low] = l[high]

        # low<high这个条件必须在这里再次体现,避免出现循环过程中low>high的情况
        while low < high and l[low] <= mid_value:
            low += 1
        # 当中间值左侧的值大于中间值时,将该值赋值于l[high](原来的值已保存至l[low])
        l[high] = l[low]

    # 退出循环时,说明low==high,则可以将mid_value的值赋予它
    l[low] = mid_value

    quick_sort(l, start, low-1)
    quick_sort(l, low+1, end)


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    quick_sort(l, 0, len(l)-1)
    print(l)

时间复杂度

  • 最优时间复杂度:O(nlogn)
  • 最坏时间复杂度:O(n2)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):不稳定

环境

Python 3.5.2

原理

  • 在列表左侧构建有序序列
  • 一开始将第一个元素视为有序序列
  • 对于未排序序列,则将未排序序列中的元素依次从右到左与已排序序列中的元素做比较
  • 如果未排序元素小于当时比较的已排序元素,则将该已排序元素右移
  • 如果未排序元素大于当时比较的已排序元素,则说明该元素已插入到合适位置,此轮循环结束
  • 以此类推

源码

def insert_sort(l):
    n = len(l)
    # 要排序的元素
    for i in range(1, n):
        # 已排序的元素
        for j in range(i, 0, -1):
            if l[j] < l[j-1]:
                l[j], l[j-1] = l[j-1], l[j]
            else:
                break


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    insert_sort(l)
    print(l)

时间复杂度

  • 最优时间复杂度:O(n)
  • 最坏时间复杂度:O(n2)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):稳定

环境

Python 3.5.2

原理

  • 默认最左侧的元素为最小,而后依次将右侧的每个元素与最左侧的元素比较,如果比最左测的元素小,则交换位置
  • 第一遍遍历会将最小的元素放在最左边,而后继续遍历,依次得出第二小、第三小…第二大的元素

源码

def select_sort(l):
    n = len(l)
    for i in range(n-1):
        for j in range(i+1, n):
            # 一开始默认下标为i的值最小
            if l[j] < l[i]:
                l[j], l[i] = l[i], l[j]


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    select_sort(l)
    print(l)

时间复杂度

  • 最优时间复杂度:O(n2)
  • 最坏时间复杂度:O(n2)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):不稳定

环境

Python 3.5.2

原理

  • 从头开始比较列表中每两个相邻的元素,如果前者比后者大,则将这两个元素交换
  • 第一遍遍历会将最大的元素放置在最右边,而后继续遍历,依次得出第二大、第三大…第二小的元素
  • [优化]每次遍历时,判断各元素之间的位置是否发生了改变,如果没有改变,则直接结束排序

源码

def bubble_sort(l):
    n = len(l)
    for j in range(n-1):
        # 用于判断此轮遍历过程中各元素之间的位置是否发生了改变
        has_change = False
        for i in range(n-1-j):
            if l[i] > l[i+1]:
                l[i+1], l[i] = l[i], l[i+1]
                has_change = True
        if has_change == False:
            break


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    bubble_sort(l)
    print(l)

时间复杂度

  • 最优时间复杂度:O(n)
  • 最坏时间复杂度:O(n2)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):稳定