线性表的排序算法比较与性能分析

# 1. 线性表的概述

线性表是一种数据结构，由零个或多个数据元素组成。线性表中的元素之间存在**一对一**的关系，即除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继。线性表的特点包括**有序性、可重复性**和**顺序存取性**。在实际应用中，线性表常用于列表、数组、堆栈和队列等数据结构中。例如，线性表可以用于表示学生成绩、员工信息等。线性表的灵活性使其在计算机程序设计领域得到广泛应用，尤其在数据结构和算法中扮演着重要角色。线性表的研究与应用，有助于提高程序的效率和可读性。

# 2. 线性表的基本操作

2.1 创建线性表

线性表的创建是指在内存中分配一段连续的存储空间来存储线性表的元素。我们可以使用数组来实现线性表的存储结构，以下是创建线性表的基本操作：
1. **初始化操作：** 初始化一个空的线性表，通常需要指定线性表的最大长度。
2. **申请存储空间：** 通过动态内存分配函数（如`malloc`）在堆上申请足够的空间来存储线性表元素。
3. **赋初值：** 可以根据需求对线性表中的元素进行初始化。

# 创建线性表的示例代码（Python）
class ArrayList:
    def __init__(self, max_size):
        self.max_size = max_size
        self.data = [None] * max_size
        self.length = 0

# 初始化一个最大长度为 10 的线性表
array_list = ArrayList(10)

2.2 插入元素

插入元素是向线性表中的指定位置插入一个新元素，需要考虑插入位置的合法性以及线性表的扩容问题。以下是插入元素的基本操作：
1. **判断位置合法性：** 检查插入位置是否在有效范围内。
2. **元素后移：** 将插入位置及其后的元素依次向后移动一位。
3. **插入新元素：** 将新元素插入到指定位置处。
4. **更新长度：** 更新线性表的长度。

# 插入元素的示例代码（Python）
def insert_element(array_list, index, element):
    if index < 0 or index > array_list.length:
        print("Invalid index for insertion.")
        return
    if array_list.length == array_list.max_size:
        print("The array list is full. Need to expand.")
        return
    for i in range(array_list.length - 1, index - 1, -1):
        array_list.data[i + 1] = array_list.data[i]
    array_list.data[index] = element
    array_list.length += 1

2.3 删除元素

删除元素是从线性表中删除指定位置的元素，同时需要处理删除位置的合法性及后续元素的前移操作。以下是删除元素的基本操作：
1. **判断位置合法性：** 确保删除位置在有效范围内。
2. **元素前移：** 将删除位置之后的元素依次向前移动一位。
3. **删除元素：** 删除指定位置处的元素。
4. **更新长度：** 更新线性表的长度。

# 删除元素的示例代码（Python）
def delete_element(array_list, index):
    if index < 0 or index >= array_list.length:
        print("Invalid index for deletion.")
        return
    for i in range(index, array_list.length - 1):
        arra