插入排序
本页面将简要介绍插入排序。
定义
插入排序（英语：Insertion sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。
一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌，按牌面大小插到手牌后，再抓下一张牌。
性质
稳定性
插入排序是一种稳定的排序算法。
时间复杂度
插入排序的最优时间复杂度为
插入排序的最坏时间复杂度和平均时间复杂度都为
代码实现
伪代码
=== "C++"
```cpp
void insertion_sort(int arr[], int len) {
for (int i = 1; i < len; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
```=== "Python"
```python
def insertion_sort(arr, n):
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key
```贡献者：@四月永不逃离@Menci@WenzelTian@llh721113@Nathan@mgt@Nano@夜轮_NachtgeistW@NachtgeistW@H-J-Granger@雷蒻@thy@ouuan@partychicken
本页面最近更新：2/3/2023, 12:00:00 AM，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用