Python插入排序 - 像整理扑克牌一样！¶

视频教程¶

1. 插入排序基础概念¶

2. 完整排序过程¶

3. 代码讲解¶

1. 插入排序是什么？让我们一起想象...¶

想象你在玩扑克牌！当你拿到新牌时，你会把它插入到手里已经排好序的牌中的正确位置。这就是插入排序啦！每次拿一张新牌，找到它应该在的位置，然后把它插进去。

在这里看看扑克牌是怎么排序的！

2. 让我们玩个游戏！¶

2.1. 扑克牌游戏¶

想象你在玩扑克牌： 1. 先拿一张牌在手上 2. 再拿一张牌，和手里的牌比较，放到合适的位置 3. 继续拿牌，每次都把新牌放到正确的位置 4. 直到所有的牌都排好序啦！

2.2. 写个简单的程序¶

def insertion_sort(numbers):
    # 从第二个数字开始，因为第一个数字已经是排好序的啦
    for i in range(1, len(numbers)):
        # 拿到当前的数字，就像抽了一张新牌
        current_number = numbers[i]

        # 找到这个数字应该放的位置
        j = i - 1
        while j >= 0 and numbers[j] > current_number:
            # 把比current_number大的数字都往右移一位
            numbers[j + 1] = numbers[j]
            j = j - 1

        # 把current_number放到它应该在的位置
        numbers[j + 1] = current_number

    return numbers

# 试一试！
my_numbers = [5, 2, 8, 1, 9]
print("排序前：", my_numbers)
sorted_numbers = insertion_sort(my_numbers)
print("排序后：", sorted_numbers)

3. 让插入排序变得更有趣！¶

3.1. 二分查找插入¶

就像猜数字游戏一样，我们可以用二分查找来更快地找到插入位置：

def binary_insertion_sort(numbers):
    def binary_search(arr, target, start, end):
        if start == end:
            if arr[start] > target:
                return start
            else:
                return start + 1

        if start > end:
            return start

        mid = (start + end) // 2
        if arr[mid] < target:
            return binary_search(arr, target, mid + 1, end)
        elif arr[mid] > target:
            return binary_search(arr, target, start, mid - 1)
        else:
            return mid

    for i in range(1, len(numbers)):
        # 拿到当前的数字
        current_number = numbers[i]

        # 用二分查找找到应该插入的位置
        j = binary_search(numbers, current_number, 0, i - 1)

        # 把数字插入到正确的位置
        numbers[j+1:i+1] = numbers[j:i]
        numbers[j] = current_number

    return numbers

# 试试这个聪明的方法
my_numbers = [6, 2, 9, 1, 7, 3, 8]
print("排序前：", my_numbers)
sorted_numbers = binary_insertion_sort(my_numbers)
print("排序后：", sorted_numbers)

4. 插入排序有什么特点？¶

4.1. 优点：¶

超级容易理解，就像整理扑克牌一样简单！
对于小数据或者已经差不多排好序的数据特别快
可以一边接收数据一边排序
特别适合小朋友学习编程

4.2. 缺点：¶

如果数字特别多，移动次数会很多
对于完全乱序的大数据不太适合
需要经常移动数字

5. 生活中的例子¶

5.1. 图书馆整理书籍¶

想象你是图书管理员： 1. 书架上已经有一些按顺序排好的书 2. 来了一本新书，你要把它放到正确的位置 3. 找到位置后，把其他书往后移一下 4. 把新书放进去，完美！

5.2. 整理扑克牌¶

开始时手里有一张牌
每次抽一张新牌
把新牌插入到手里已有的牌中的正确位置
重复这个过程，直到所有牌都排好序

6. 趣味练习题¶

6.1. 小游戏：整理卡片¶

材料：一副数字卡片（1-10） 1. 随机抽5张卡片 2. 试着用插入排序的方法把它们排好 3. 看看你能不能越排越快！

6.2. 动手编程¶

# 完成下面的程序，实现插入排序
def my_first_insertion_sort(numbers):
    # 在这里写下你的代码
    # 提示：从第二个数字开始
    # 提示：把每个数字插入到前面已排序的部分
    pass

# 测试你的程序
test_numbers = [4, 2, 7, 1, 3]
sorted_numbers = my_first_insertion_sort(test_numbers)
print("你的程序排序结果：", sorted_numbers)

7. 小贴士¶

记住插入排序的关键点：
把数组分成已排序和未排序两部分
每次从未排序的部分拿一个数字
把这个数字插入到已排序部分的正确位置
练习方法：
用扑克牌实际练习一下
从小数据开始练习
试试对已经差不多排好序的数据排序
进阶学习：
学习二分查找来加快找位置的速度
比较和其他排序方法的不同
想想什么时候用插入排序最合适

记住：插入排序就像整理扑克牌一样有趣，多练习就能成为排序高手啦！

进一步学习¶

插入排序 (Insertion Sort)¶

算法介绍¶

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

完整演示¶

下面的视频展示了插入排序的完整过程：

代码实现¶

让我们来看看插入排序的Python代码实现：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # 当前要插入的元素
        j = i-1
        # 将比key大的元素都向后移动一位
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key  # 找到合适的位置，插入key
    return arr

算法特点¶

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定
原地排序：是

适用场景¶

数据量较小
数据基本有序
需要稳定的排序算法
在线算法（可以边输入边排序）