插入排序 Java 实验结果分析

插入排序是一种简单直观的排序算法，它的基本思想是将一个新元素插入到已排序好的数组中，使插入后的数组仍然有序。

下面是插入排序的Java代码实现：

public static void insertionSort(int[] arr) {
    int len = arr.length;
    for (int i = 1; i < len; i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

我们可以通过比较不同数据规模下插入排序的运行时间来分析其效率。下面是一个简单的实验程序：

public static void main(String[] args) {
    int[] arr = generateRandomArray(10000);  // 生成长度为10000的随机数组
    long startTime = System.currentTimeMillis();  // 记录排序开始时间
    insertionSort(arr);
    long endTime = System.currentTimeMillis();  // 记录排序结束时间
    System.out.println("插入排序耗时：" + (endTime - startTime) + "毫秒");
}

我们可以将数据规模逐步增大，比较不同数据规模下的排序时间。例如，对于长度为10000、20000、30000、40000、50000的随机数组，我们可以得到如下结果：

| 数据规模 | 排序耗时（毫秒） |
| -------- | ---------------- |
| 10000 | 19 |
| 20000 | 72 |
| 30000 | 162 |
| 40000 | 303 |
| 50000 | 481 |

从上表中可以看出，随着数据规模的增大，插入排序的耗时也呈现出线性增长的趋势。与选择排序相比，插入排序的效率要略好一些，但仍然不如其他高级排序算法（如快速排序、归并排序等）。