插入排序

插入排序（Insertion Sort）

工作原理

插入排序通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。

1. 初始状态：数组中的第一个元素被认为是已排序的。
2. 取出下一个元素：在未排序部分取出下一个元素。
3. 定位已排序部分的插入位置：从已排序的部分开始，比较新元素与该部分的每个元素，找到合适的位置。
4. 插入新元素：将新元素插入到已排序部分的适当位置。

Java实现

public class InsertionSort {

    /**
     * 使用插入排序算法对数组进行排序
     * @param arr 要排序的数组
     */
    public static void sort(int[] arr) {
        int n = arr.length;

        // 从第二个元素开始，因为第一个元素默认已排序
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            // 将大于key的元素向后移动一位
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 将key插入到正确的位置
            arr[j + 1] = key;
        }
    }

    /**
     * 打印数组中的元素
     * @param arr 数组
     */
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    /**
     * 主函数
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        int[] sampleArray = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original array:");
        printArray(sampleArray);

        sort(sampleArray);

        System.out.println("Sorted array:");
        printArray(sampleArray);
    }
}

代码解析

1. sort() 方法：这是插入排序的核心实现。它接受一个整型数组作为参数，并对其进行排序。
2. 外层循环：从数组的第二个元素开始，依次将每个元素插入到已排序的序列中。
3. 内层循环：从当前元素的前一个位置开始，向左查找直到找到合适的位置。
4. 插入操作：将当前元素插入到正确的位置。
5. printArray() 方法：用于打印数组中的元素。
6. main() 方法：测试排序功能的方法。

注意事项

• 时间复杂度：插入排序的平均和最坏情况下的时间复杂度均为 O(n^2)，其中 n 是数组长度。但是，在最好的情况下（即输入数组已经是排序好的），时间复杂度为 O(n)，因为内层循环不会执行。
• 稳定性：插入排序是稳定的排序算法，因为它不会改变相等元素之间的原有顺序。
• 空间复杂度：插入排序的空间复杂度为 O(1)，因为它不需要额外的存储空间。

适用场景

插入排序适合于小规模数据的排序，或者当输入数据部分已排序时。由于其时间复杂度较高，不推荐用于大规模数据集的排序。

希望这段代码及其说明能够帮助您更好地理解和实现插入排序算法。如果您有任何疑问或需要进一步的帮助，请随时告诉我。