数据结构与算法之手撕排序算法

本篇攻略介绍如何手撕常见的排序算法。

冒泡排序

冒泡排序是一种通过不断交换相邻元素来排序的方法。它的时间复杂度为$O(n^2)$。

def bubble_sort(nums):
    for i in range(len(nums)):
        for j in range(len(nums)-i-1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

示例1：

>>> nums = [5, 2, 8, 4, 9, 1]
>>> bubble_sort(nums)
[1, 2, 4, 5, 8, 9]

示例2：

>>> nums = [7, 3, 6, 1, 9]
>>> bubble_sort(nums)
[1, 3, 6, 7, 9]

选择排序

选择排序是一种每次找最小元素并放到已排序数组末尾的方法。它的时间复杂度为$O(n^2)$。

def selection_sort(nums):
    for i in range(len(nums)):
        min_idx = i
        for j in range(i+1, len(nums)):
            if nums[j] < nums[min_idx]:
                min_idx = j
        nums[i], nums[min_idx] = nums[min_idx], nums[i]
    return nums

示例1：

>>> nums = [5, 2, 8, 4, 9, 1]
>>> selection_sort(nums)
[1, 2, 4, 5, 8, 9]

示例2：

>>> nums = [7, 3, 6, 1, 9]
>>> selection_sort(nums)
[1, 3, 6, 7, 9]

插入排序

插入排序是一种将未排序段元素逐个插入已排序段的方法。它的时间复杂度为$O(n^2)$。

def insertion_sort(nums):
    for i in range(1, len(nums)):
        temp = nums[i]
        j = i-1
        while j >= 0 and nums[j] > temp:
            nums[j+1] = nums[j]
            j -= 1
        nums[j+1] = temp
    return nums

示例1：

>>> nums = [5, 2, 8, 4, 9, 1]
>>> insertion_sort(nums)
[1, 2, 4, 5, 8, 9]

示例2：

>>> nums = [7, 3, 6, 1, 9]
>>> insertion_sort(nums)
[1, 3, 6, 7, 9]