直接插入排序是一种简单的排序算法，它的基本思想是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。这个过程会不断重复，直到所有数据都插入到有序序列中。
在直接插入排序的过程中，我们通常会将待排序的数组分为已排序和未排序两部分。初始化时，我们假设第一个元素是已排序的。接下来，从第二个元素开始，我们寻找它在已排序子数组中的合适位置，并将其插入。这个过程涉及到两个关键步骤：
1. **寻找插入位置**：我们并不从已排序子数组的起始位置开始比较，而是从子数组的末尾开始，逆序地与待插入元素进行比较。如果待插入元素小于当前元素，我们就将当前元素后移一位，直到找到一个不大于待插入元素的位置。
2. **插入元素**：找到合适的位置后，我们将待插入元素放置在这个位置，完成一次插入操作。这个过程在Java代码中通过一个内部循环实现，当待插入元素与已排序的元素比较后，将大于待插入元素的所有元素都向后移动一位，然后在正确的位置插入。
以下是一个Java实现的直接插入排序的示例：
```java
public class InsertArray {
private long[] arr;
private int elems;
public InsertArray() {
arr = new long[50];
}
public InsertArray(int max) {
arr = new long[max];
}
public void insert(long value) {
arr[elems] = value;
elems++;
}
public void display() {
for (int i = 0; i < elems; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public void insertSort() {
long select = 0L;
for (int i = 1; i < elems; i++) {
select = arr[i];
int j = i;
for (; j > 0 && arr[j - 1] >= select; j--) {
arr[j] = arr[j - 1];
}
arr[j] = select;
}
}
}
// 测试类
public class TestInsertArray {
public static void main(String[] args) {
InsertArray iArr = new InsertArray();
iArr.insert(85);
iArr.insert(7856);
iArr.insert(12);
iArr.insert(8);
iArr.insert(5);
iArr.insert(56);
iArr.display();
iArr.insertSort();
iArr.display();
}
}
```
这段代码首先定义了一个`InsertArray`类，包含了数组、元素数量以及插入和显示数据的方法。`insertSort`方法实现了直接插入排序的逻辑。在测试类`TestInsertArray`中，我们创建了一个`InsertArray`对象，插入了一些数据，然后调用`insertSort`方法进行排序，并输出排序前后的数组状态。
关于算法的性能，直接插入排序的时间复杂度分析如下：
1. **最佳情况**：如果输入数组已经是正序，每个元素都能立即找到正确的位置，只需要一次比较，因此时间复杂度为O(n)。
2. **最坏情况**：当输入数组完全逆序时，每个元素都需要与已排序的所有元素进行比较，总共需要进行n*(n-1)/2次比较和移动，时间复杂度为O(n^2)。
3. **平均情况**：平均情况下，每次插入大约需要移动n/2次，因此总操作次数大约为n^2/2，时间复杂度也是O(n^2)。
空间复杂度方面，由于直接插入排序是原地排序，不需要额外的存储空间，所以空间复杂度为O(1)。
总结来说，直接插入排序适用于小规模或部分有序的数据，对于大规模或无序的数据，其效率较低。在实际应用中，对于需要高效排序的场景，通常会选择更高级的排序算法，如快速排序、归并排序等。
