Python 基本排序算法：冒泡，选择，快速排序

󰃭 2017-06-27

冒泡排序

算法

n 个数的序列 [a1,a2,a3,…,an]

  1. 从 a1 开始比较相邻元素，遍历到 an，如果第一个比第二个大，就交换他们两个
  2. 第一次遍历之后，最大的在最后（an）
  3. 从 a1 开始比较相邻元素，遍历到 a(n-1) [倒数第二个]，第一个比第二个大就交换他们
  4. 第二次遍历之后，最后两个值 a(n-1)，an, 分别是第二大的值，第一大的值
  5. 针对所有的元素重复以上的步骤
  6. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

示例

# 原始序列
[6, 8, 5, 7, 3]

# 第 1 次排序
[6, 5, 7, 3, 8]

# 第 2 次排序
[5, 6, 3, 7, 8]

# 第 3 次排序
[5, 3, 6, 7, 8]

# 第 4 次排序
[3, 5, 6, 7, 8]

# 第 5 次排序不需要移动

代码

def bubble_sort(nums):
    '''
    冒泡排序, 时间复杂度 O(n^2)
    '''
    total = len(nums)
    for i in range(total-1):
        for j in range(total-i-1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]

    return nums

选择排序

特点

  • 选择排序是一个不稳定的排序算法
  • 比较次数 O(n^2），交换次数 O(n）
  • 算法的时间复杂度 O(n^2)
  • 交换次数比冒泡排序少, n 值较小时，选择排序比冒泡排序快

算法

n 个数的序列 [a1,a2,a3,…,an]

  1. 第一次遍历，从 a1 开始，遍历到 an，找出第一个最小值位置，交换最小值与 a1
  2. 第二次遍历，从 a2 开始，遍历到 an，找出第二个最小值位置，交换最小值与 a2
  3. 第三次遍历，从 a3 开始，遍历到 an，找出第三个最小值位置，交换最小值与 a3
  4. 循环 n 次，完成排序

示例

# 原始序列
[6, 8, 5, 7, 3]

# 第 1 次排序，最小值3与6交换，得到
[3, 8, 5, 7, 6]

# 第 2 次排序，第二小值5与8交换，得到
[3, 5, 8, 7, 6]

# 第 3 次排序，第三小值6与8交换，得到
[3, 5, 6, 7, 8]

# 第 4，第 5 次不需要移动

代码

def select_sort(nums):
    '''
    选择排序, 时间复杂度 O(n^2)
    '''
    total = len(nums)
    for i in range(total):
        min = i
        for j in range(i+1, total):
            if nums[min] > nums[j]:
                min = j
        nums[min], nums[i] = nums[i], nums[min]

    return nums

快速排序

算法

n 个数的序列 [a1,a2,a3,…,an]

  1. 选取一个中值
  2. 通过一趟排序将要排序的数据根据中值分成两部分，
  3. 其中一部分的所有数据都比另外一部分的所有数据都要小（根据中值划分）
  4. 然后再按此方法对这两部分数据分别进行快速排序
  5. 排序过程递归进行，最终完成整个数据的排序

示例

# 原始序列
[6, 8, 5, 7, 3]

# 第 1 次排序，选择 6 为中值
[6, 8, 5, 7, 3]
[6, 3, 5, 7, 8]
[5, 3, 6, 7, 8]

# 第 2 次排序，选择 5 为中值
[5, 3, 6]
[3, 5, 6]

# 第 3 次排序，选择 7 为中值
[7, 8]

# 完成排序
[3, 5, 6, 7, 8]

代码

def quick_sort(nums, left, right):
    '''
    快速排序, 平均时间复杂度 O(nlogn)
    '''
    # 递归终止条件
    if left >= right:
        return nums

    # 选择中间值
    key = nums[left]

    pre_left = left
    pre_right = right
    while left < right:
        # 选取右侧小于中间值的数值
        while left < right and nums[right] >= key:
            right -= 1

        # 选取左侧大于中间值的数值
        while left < right and nums[left] <= key:
            left += 1

        # 交换获取的值
        nums[left], nums[right] = nums[right], nums[left]

    # 交换中值与当前左右哨兵相交位置的值
    nums[pre_left], nums[left] = nums[left], nums[pre_left]


    # 递归二分后的子序列
    quick_sort(nums, pre_left, left)
    quick_sort(nums, left + 1, pre_right)

    return nums

测试程序

#!/usr/bin/env python
# coding: utf-8

import random
import timeit
import functools

# ... 算法函数定义

def main():
    number = 100
    sample = random.sample(range(number), number)

    sample = random.sample(range(number), number)
    print(sample)
    print('bubble sort: ', timeit.timeit(functools.partial(bubble_sort, sample), number=1))
    print(sample)

    sample = random.sample(range(number), number)
    print(sample)
    print('select sort: ', timeit.timeit(functools.partial(select_sort, sample), number=1))
    print(sample)

    sample = random.sample(range(number), number)
    print(sample)
    print('quick sort: ', timeit.timeit(functools.partial(quick_sort, sample, 0, len(sample)-1), number=1))
    print(sample)


if __name__ == '__main__':
    main()