插入排序 java实现

**插入排序(Insertion Sort)**是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 在Java中实现插入排序，主要涉及以下几个关键步骤： 1. **初始化**：创建一个方法，如`public static void insertionSort(int[] arr)`，接收一个整数数组作为参数。 2. **外层循环**：遍历数组，从第二个元素（下标为1）开始，因为第一个元素默认已经排序好。外层循环的终止条件是数组的最后一个元素，即`for (int i = 1; i < arr.length; i++)`。 3. **内层循环**：在内层循环中，我们需要将当前元素（`arr[i]`）与前面已排序的部分进行比较，并在适当的位置插入。内层循环的终止条件是找到合适的位置或到达已排序区的起始位置，即`for (int j = i - 1; j >= 0 && arr[j] > arr[i]; j--)`。 4. **交换元素**：在内层循环中，如果`arr[j]`大于`arr[i]`，则交换这两个元素的位置，确保前面的元素始终小于后面的元素。交换操作可以用临时变量辅助完成，例如`int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;`。 5. **结束内层循环**：当找到合适的位置时，跳出内层循环，此时`arr[i]`已经位于正确位置，继续处理下一个未排序元素。 6. **结束外层循环**：外层循环结束后，整个数组已按升序排序完成。 在Java中，`MyInsertSort.java`文件中的代码可能如下所示： ```java public class MyInsertSort { public static void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } public static void main(String[] args) { // 随机生成1000个0-1000之间的数 int[] nums = new int[1000]; Random rand = new Random(); for (int i = 0; i < nums.length; i++) { nums[i] = rand.nextInt(1001); } // 执行插入排序 insertionSort(nums); // 输出排序后的结果 for (int num : nums) { System.out.print(num + " "); } } } ``` 在上述代码中，`main`方法用于生成随机数并调用`insertionSort`进行排序。这个程序可以用于验证插入排序算法的正确性。由于插入排序的时间复杂度在最坏情况下为O(n^2)，对于大数据量的排序，效率较低。但在数据部分有序或者小规模数据排序时，插入排序有较好的表现。 此外，插入排序是八大经典排序算法之一，包括冒泡排序、选择排序、希尔排序、快速排序、归并排序、堆排序、基数排序和插入排序。每种排序算法都有其适用场景和优缺点，理解并掌握这些算法有助于在实际编程中选择合适的排序方法。