线性表的排序算法：插入排序

# 1.1 简介

线性表是一种常用的数据结构，它是由 n 个数据元素组成的有限序列。具有以下特点：数据元素之间是有序的，每个数据元素只有唯一的前驱和后继。线性表广泛应用于各种领域，如数据库、算法等。通过线性表，可以方便地对数据进行存储、查找和操作，提高程序的效率和可维护性。在现代计算机科学中，线性表扮演着重要的角色，是许多高级数据结构和算法的基础。因此，深入理解线性表的定义、特点和应用是非常必要的。在接下来的部分，我们将深入探讨线性表的分类以及与之相关的数据结构和算法。

# 2.1 冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过多次遍历待排序序列，依次比较相邻元素的大小，若顺序不满足要求则交换它们，从而将最大（或最小）的元素逐渐“冒泡”到最后（或最前）的位置。

#### 2.1.1 算法思想

1. 从序列的第一个元素开始，依次与其后相邻元素比较。
2. 如果当前元素大于（或小于）相邻元素，交换它们的位置。
3. 每次遍历结束后，最大（或最小）的元素将“冒泡”到正确位置。
4. 重复上述步骤，直至整个序列有序。

#### 2.1.2 时间复杂度分析

- 最好情况：O(n)，即序列已经有序。
- 最坏情况：O(n^2)，即逆序情况。
- 平均情况：O(n^2)。

#### 2.1.3 稳定性比较

冒泡排序是一种稳定的排序算法，相等元素的相对位置在排序前后不会改变。

#### 2.1.4 优缺点

- 优点：实现简单，适用于较小规模的数据排序。
- 缺点：效率较低，时间复杂度高，不适用于大规模数据排序。

### 2.2 选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，它每次从待排序序列中选出最小（或最大）的元素，放到已排序序列的末尾（或开头），直到整个序列排序完成。

#### 2.2.1 算法原理

1. 初始时，将整个序列看作未排序部分。
2. 每次在未排序部分选择最小（或最大）的元素，与未排序部分的起始元素交换。
3. 每次迭代，已排序部分增加一个元素。

#### 2.2.2 时间复杂度分析

- 最好情况：O(n^2)，与逆序情况相同。
- 最坏情况：O(n^2)，与逆序情况相同。
- 平均情况：O(n^2)。

#### 2.2.3 稳定性比较

选择排序是一种不稳定的排序算法，相等元素的相对位置在排序后可能发生变化。

#### 2.2.4 优缺点

- 优点：简单直观，适用于简单场景。
- 缺点：效率低下，不稳定性，不适合大规模数据。

# 3. 插入排序的概念和原理

#### 3.1 插入排序简介
插入排序是一种简单直观的排序算法，基本思想是将待排序的数据分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的合适位置。这种排序方法类似于打牌时整理手中的牌，逐个插入