数据结构直接插入排序的课程设计

直接插入排序是一种简单的排序算法，其基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。下面是一个数据结构直接插入排序的课程设计的示例：

假设我们有一个动态数组类模板DynamicArray，其中包含以下成员函数：
- `int getSize()`：获取动态数组的大小
- `void insert(int index, int value)`：在指定位置插入一个元素
- `int get(int index)`：获取指定位置的元素

我们可以设计一个直接插入排序的函数模板，如下所示：

template <typename T>
void insertionSort(DynamicArray<T>& arr) {
    int n = arr.getSize();
    for (int i = 1; i < n; i++) {
        T temp = arr.get(i);
        int j = i - 1;
        while (j >= 0 && arr.get(j) > temp) {
            arr.insert(j + 1, arr.get(j));
            j--;
        }
        arr.insert(j + 1, temp);
    }
}

该函数模板接受一个动态数组作为参数，使用直接插入排序算法对其进行排序。具体实现过程为：从第二个元素开始，将其插入到已经排好序的前面的有序表中，直到整个数组都排好序为止。