Java 直接插入排序的三种实现

本文将介绍 Java 中直接插入排序的三种实现方式，分别为插入排序、希尔排序和折半插入排序。

插入排序

插入排序是一种简单直观的排序算法，其基本思想是将一个待排序的元素插入到已排好序列中的适当位置。

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

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

上述实现中，使用一个外层循环遍历待排序数组，从第二个元素开始到最后一个元素。在内层循环中以正确的顺序将当前元素插入到已排好序的序列中。

以下是一个使用插入排序的示例：

int[] arr = {5, 3, 8, 6, 4};
insertSort(arr);
System.out.println(Arrays.toString(arr));

输出结果为：

[3, 4, 5, 6, 8]

希尔排序

希尔排序是一种基于插入排序的优化算法，它通过将待排序数组分成若干个子序列进行插入排序来加快排序速度。

以下是 Java 中希尔排序的实现代码：

public static void shellSort(int[] arr) {
    int gap = arr.length / 2;
    while (gap > 0) {
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j-gap] > temp) {
                arr[j] = arr[j-gap];
                j -= gap;
            }
            arr[j] = temp;
        }
        gap /= 2;
    }
}

上述实现中，首先定义希尔增量 gap 为数组长度的一半，然后在外层循环中不断将 gap 减半，内层循环采用插入排序的方式对每个子序列进行排序。

以下是一个使用希尔排序的示例：

int[] arr = {5, 3, 8, 6, 4};
shellSort(arr);
System.out.println(Arrays.toString(arr));

输出结果为：

[3, 4, 5, 6, 8]

折半插入排序

折半插入排序是一种对插入排序的优化算法，它通过将查找插入位置的线性搜索改为二分查找的方式来减少比较次数。

以下是 Java 中折半插入排序的实现代码：

public static void binaryInsertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int temp = arr[i];
        int left = 0;
        int right = i-1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > temp) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        for (int j = i-1; j >= left; j--) {
            arr[j+1] = arr[j];
        }
        arr[left] = temp;
    }
}

上述实现中，在内层循环中使用折半查找的方式找到待插入元素的位置。这里使用一个 left 指针指向待插入的位置，然后将 left 右侧的元素向右移动一位，最后将待插入元素插入到 left 的位置上。

以下是一个使用折半插入排序的示例：

int[] arr = {5, 3, 8, 6, 4};
binaryInsertSort(arr);
System.out.println(Arrays.toString(arr));

输出结果为：

[3, 4, 5, 6, 8]

总结

本文介绍了 Java 中直接插入排序的三种实现方式，分别为插入排序、希尔排序和折半插入排序。不同的实现方式有着不同的优缺点，选择适合自己的算法是提高排序性能的重要步骤。