直接插入排序是一种简单的排序算法,它适用于小型或部分有序的数据集。该算法的基本思想是将待排序的数组分为已排序区和未排序区,每次从未排序区选择一个元素(称为关键字),然后将其插入到已排序区的正确位置,使得已排序区始终保持有序。这个过程会持续进行,直到所有元素都被插入到已排序区,即整个数组排序完成。
在编程中,特别是在C++中,数组是数据结构的重要组成部分。一维数组是一组相同类型的元素按顺序排列的集合,例如:
1. **静态数组**:在程序编译时,数组的大小(如`const int iLen=6; int iArr[iLen];`)必须是常量,且类型固定。它们在内存中占用连续的存储空间,访问效率高,但大小不可变。
2. **动态数组**:如`int *pArr = new int[iLen];`,允许在运行时确定大小。它们使用指针来管理内存,虽然初始分配时也是连续的,但可以通过`new[]`和`delete[]`操作动态扩展或缩小。
对于二维数组,如`int len; cin >> len; int *p = new int[len];`,表示的是行向量,每一行可以看作是一个一维数组。这种数组可以用于表示表格数据,其大小同样可以在运行时确定。
C++标准模板库(STL)中的`vector`提供了动态数组功能,它支持动态扩容,使得数组长度可以根据需要增长,无需手动管理内存,例如`vector<int> array(len);`。
字符数组和字符串数组也属于数组类型,如`char cName[] = “Jackson”`,或者`char *pName[3]`,它们存储的是字符序列,常用于处理文本数据。
结构体数组,如`StructStudents[3]`,则可以存储不同类型的数据,每个元素都是一个结构体实例。此外,还可以创建动态结构体数组,如`Box shoesbox[3]`,其中`Box`可能是自定义的结构体类型。
数组初始化的方式多样,包括直接初始化(如`int iArr[3]{1,2,3};`)和间接初始化(如通过初始化列表)。通过下标(如`a[0]`到`a[9]`)可以直接访问数组元素,而一维数组的引用提供更直观的操作方式。
在对数组进行插入排序时,C++中的实现通常不会涉及数组的底层细节,而是通过迭代和比较元素,确保每个插入操作都能保持已排序部分的有序性。这种简单但效率较低的排序方法适用于数据量较小或者基本有序的情况。