Java 插入排序详解

秒速五厘米 2023-10-10 00:27 40阅读 0赞

Java 中插入排序是一种简单但实用的排序算法，其基本原理是将一个无序的数组分为有序部分和无序部分，每次取出无序部分中的一个元素插入到有序部分中，从而实现整体的有序化。

插入排序算法的具体实现方法有两种：直接插入排序和希尔排序。直接插入排序是一种简单但效率较低的排序算法，适用于小规模数据的排序；而希尔排序是对直接插入排序的改进，通过增加步长来更高效地对大规模数据进行排序。

### 1. 直接插入排序 ###

直接插入排序的基本思想是将一个无序的数组分为有序部分和无序部分，从无序部分中取出一个数，插入到有序部分中去。假设我们有一组数 \{38, 65, 97, 76, 13, 27, 49\}，将其按照从小到大排序的过程如下：

初始状态：\{38, 65, 97, 76, 13, 27, 49\}

第一轮插入：将 65 插入到已经排好序的部分中，得到 \{38, 65, 97, 76, 13, 27, 49\}。

第二轮插入：将 97 插入到已经排好序的部分中，得到 \{38, 65, 76, 97, 13, 27, 49\}。

第三轮插入：将 76 插入到已经排好序的部分中，得到 \{38, 65, 76, 97, 13, 27, 49\}。

第四轮插入：将 13 插入到已经排好序的部分中，得到 \{13, 38, 65, 76, 97, 27, 49\}。

第五轮插入：将 27 插入到已经排好序的部分中，得到 \{13, 27, 38, 65, 76, 97, 49\}。

第六轮插入：将 49 插入到已经排好序的部分中，得到 \{13, 27, 38, 49, 65, 76, 97\}。

最终结果：\{13, 27, 38, 49, 65, 76, 97\}

从上面的排序过程可以看出，直接插入排序算法是通过将一个元素插入到已经排好序的部分中去来实现整体排序的。其具体实现方法如下：

public static void insertionSort(int[] arr) {
        
        int n = arr.length; // 获取数组长度
        for (int i = 1; i < n; i++) {
         // 外循环，从第二个元素开始遍历，因为第一个元素本身就是有序的
            int current = arr[i]; // 将当前元素保存到变量中
            int j = i - 1; // 将需要比较的元素的索引值设置为 i-1，即当前元素的前一个元素
            while (j >= 0 && arr[j] > current) {
         // 内循环，将当前元素与前面有序部分中的元素依次比较，直到找到合适的位置插入当前元素
                arr[j + 1] = arr[j]; // 如果前一个元素大于当前元素，将前一个元素后移一位
                j--; // 继续向前查找
            }
            arr[j + 1] = current; // 将当前元素插入到合适的位置
        }
    }

上述代码中，我们使用两层循环来实现插入排序。外层循环从第二个元素开始遍历，因为第一个元素本身就是有序的。内层循环则需要将当前元素与前面有序部分中的元素依次比较，直到找到合适的位置插入当前元素。

在内层循环中，我们首先将当前元素保存到变量中，然后将需要比较的元素的索引值设置为 i-1，即当前元素的前一个元素。在比较的过程中，如果前一个元素大于当前元素，我们将前一个元素后移一位，并继续向前查找，直到找到合适的位置插入当前元素。

### 2. 希尔排序 ###

希尔排序是对直接插入排序的改进，通过增加步长来更高效地对大规模数据进行排序。其基本思想是将一个数组分成若干个子序列，对每个子序列进行插入排序，然后逐步缩短步长，最终完成整体排序。

假设我们有一组数 \{38, 65, 97, 76, 13, 27, 49\}，按照希尔排序的过程如下：

初始状态：\{38, 65, 97, 76, 13, 27, 49\}

第一轮排序，增量为 3：\{38, 27, 49, 76, 13, 65, 97\}

第二轮排序，增量为 2：\{13, 27, 38, 49, 65, 76, 97\}

第三轮排序，增量为 1：\{13, 27, 38, 49, 65, 76, 97\}

最终结果：\{13, 27, 38, 49, 65, 76, 97\}

从上面的排序过程可以看出，希尔排序算法是通过增加步长来更高效地对大规模数据进行排序的。其具体实现方法如下：

public static void shellSort(int[] arr) {
        
        int n = arr.length; // 获取数组长度
        for (int gap = n / 2; gap > 0; gap /= 2) {
         // 外循环，逐步缩短步长
            for (int i = gap; i < n; i++) {
         // 内循环，对每个子序列进行插入排序
                int current = arr[i]; // 将当前元素保存到变量中
                int j = i - gap; // 将需要比较的元素的索引值设置为当前元素的间隔值前面的那个元素
                while (j >= 0 && arr[j] > current) {
         // 如果前一个元素大于当前元素，将前一个元素后移 gap 位
                    arr[j + gap] = arr[j];
                    j -= gap; // 继续向前查找
                }
                arr[j + gap] = current; // 将当前元素插入到合适的位置
            }
        }
    }

上述代码中，我们使用了两层循环来实现希尔排序。外层循环逐步缩短步长，内层循环则对每个子序列进行插入排序。

在内层循环中，我们首先将当前元素保存到变量中，然后将需要比较的元素的索引值设置为当前元素的间隔值前面的那个元素。在比较的过程中，如果前一个元素大于当前元素，我们将前一个元素后移 gap 位，并继续向前查找，直到找到合适的位置插入当前元素。

希尔排序算法有以下几个特点：

1.  比直接插入排序更高效：希尔排序算法通过增加步长来更高效地对大规模数据进行排序，相比之下直接插入排序效率较低，不适合处理大规模数据。
2.  时间复杂度不稳定：希尔排序的时间复杂度与步长有关，不同的步长可能会导致不同的时间复杂度表现，因此其时间复杂度是不稳定的。
3.  不适合处理链表结构：由于链表结构的数据不支持随机访问，因此希尔排序算法不适用于链表结构的数据。
4.  希尔排序算法是一个不稳定的排序算法，不稳定性是指相等的元素在排序后的顺序与之前的顺序可能不同。
5.  在实际应用中，我们通常采用 Hibbard、Sedgewick 或 Knuth 等增量序列来实现希尔排序，这些增量序列可使得希尔排序算法的时间复杂度尽可能地接近 O(nlogn)。

### 总结 ###

插入排序算法是一种简单但实用的排序方法，其中直接插入排序适用于小规模数据的排序，而希尔排序则适用于大规模数据的排序。由于它们都是基于数组结构实现的排序算法，因此它们都不适用于链表结构的数据。

在实际应用中，插入排序算法的优点是简单易懂、实现方便，缺点是时间复杂度较高，不适合处理大规模数据；而希尔排序算法通过增加步长来提高效率，但其时间复杂度与步长有关，也不稳定。因此，在实际工作中，我们需要根据具体的场景选择合适的排序算法。