插入排序

简介

插入排序（Insertion Sort）是一种简单直观的排序算法。它的基本思想是将数组分为已排序区和未排序区，每次从未排序区选择一个元素，插入到已排序区的正确位置，以此不断扩大已排序区的范围，直到整个数组排序完成。

算法步骤

插入排序的算法步骤如下：

• 从第一个元素开始，将其视为已排序区。

• 取下一个元素，将其插入到已排序区的正确位置，使得已排序区仍然保持有序。

• 重复步骤2，直到所有元素都被插入到已排序区。

实战案例

以下是一个使用Java实现插入排序算法的示例代码：

public class InsertionSort {
    public static void insertionSort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            int key = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }
​
    public static void main(String[] args) {
        int[] array = {5, 2, 8, 12, 1, 6, 3, 9};
        System.out.println("Original array: " + Arrays.toString(array));
        insertionSort(array);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}

在上面的代码中，insertionSort方法实现了插入排序算法。它使用了一个外层循环遍历数组中的每个元素，将其插入到已排序区的正确位置。内层循环用于找到插入位置，并将大于当前元素的元素后移一位。最后，将当前元素插入到正确位置。

在main方法中，我们创建一个整数数组并进行插入排序。运行程序后，将输出原始数组和排序后的数组。

优化方法

以下使用拆半插入优化的插入排序算法示例代码：

public class InsertionSort {
    public static void insertionSort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            int key = array[i];
            int left = 0;
            int right = i - 1;
            
            // 使用二分查找找到插入位置
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (array[mid] > key) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            // 插入位置后的元素后移
            for (int j = i - 1; j >= left; j--) {
                array[j + 1] = array[j];
            }
            
            // 插入元素到正确位置
            array[left] = key;
        }
    }
​
    public static void main(String[] args) {
        int[] array = {5, 2, 8, 12, 1, 6, 3, 9};
        System.out.println("Original array: " + Arrays.toString(array));
        insertionSort(array);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}

在这个示例中，我们对插入排序算法进行了拆半插入优化。在内层循环中，使用二分查找来确定插入位置，通过不断比较目标元素和中间元素的大小来缩小查找范围，直到找到插入位置。然后，在插入位置之后的元素，使用循环将它们依次后移，为目标元素腾出插入位置。最后，将目标元素插入到正确的位置。

拆半插入优化可以减少比较操作的次数，但由于需要进行元素后移操作，因此其性能提升主要取决于具体数据集的特性。在某些情况下，拆半插入优化可能比普通的插入排序更快，特别是在数据集较大且有序度较高（接近有序）时。然而，在有序度较低的情况下，拆半插入优化可能带来较小的性能提升。

因此，在实际应用中，需要根据具体数据集的特点进行评估，选择合适的排序算法和优化策略。