Java算法系列第五篇：插入排序算法详解

插入排序（Insertion Sort）是一种简单直观的排序算法，适用于少量数据的排序。它的基本思想是将数组分为已排序和未排序两部分，逐步将未排序的元素插入到已排序部分的适当位置。本文将详细介绍插入排序的原理、实现及其优化方法。

一、插入排序的基本原理

插入排序的基本步骤如下：

1. 初始状态：将第一个元素看作是已排序部分，剩余元素看作是未排序部分。
2. 遍历未排序部分：依次将未排序部分的元素插入到已排序部分的适当位置。
3. 插入操作：在已排序部分从后向前扫描，如果遇到比当前元素大的元素，则将其后移，直到找到合适的位置插入当前元素。

二、插入排序的实现

下面是一个用Java实现的插入排序算法：

public class InsertionSort {

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // 将arr[i]插入到已排序部分的适当位置
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("排序前：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        insertionSort(arr);

        System.out.println("排序后：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

运行结果

排序前：
12 11 13 5 6 
排序后：
5 6 11 12 13 

三、插入排序的优化方法

插入排序在处理大数据时效率较低，时间复杂度为O(n^2)。为了提高效率，可以考虑以下优化方法：

1. 二分查找优化：在已排序部分中使用二分查找确定插入位置，减少比较次数。
2. 希尔排序：通过将数据分成若干子序列分别进行插入排序，从而提高效率。

使用二分查找优化插入排序的示例：

public class BinaryInsertionSort {

    public static void binaryInsertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // 在已排序部分使用二分查找确定插入位置
            int pos = binarySearch(arr, key, 0, j);

            // 将元素后移，给key腾出位置
            while (j >= pos) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    // 二分查找方法
    public static int binarySearch(int[] arr, int key, int low, int high) {
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("排序前：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        binaryInsertionSort(arr);

        System.out.println("排序后：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

四、希尔排序

希尔排序（Shell Sort）是插入排序的一种改进版本，通过将数据分成若干子序列分别进行插入排序来提高效率。希尔排序的基本步骤如下：

1. 选择间隔序列：选择一个间隔序列，将数组分成若干子序列。
2. 逐步减小间隔：对每个子序列分别进行插入排序，然后逐步减小间隔，重复进行插入排序，直到间隔为1。

下面是一个用Java实现的希尔排序算法：

public class ShellSort {

    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 key = arr[i];
                int j = i;

                // 对每个子序列进行插入排序
                while (j >= gap && arr[j - gap] > key) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = key;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 2, 3};
        System.out.println("排序前：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        shellSort(arr);

        System.out.println("排序后：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

五、总结

插入排序是一种简单且稳定的排序算法，适用于少量数据的排序。通过二分查找优化和希尔排序，可以进一步提高插入排序的效率。在实际应用中，插入排序常用于小规模数据的排序和其他高级排序算法的优化。

希望大家多多点赞、关注和收藏！你的支持是我持续创作的动力！下期我们将详细讲解选择排序算法，敬请期待！

---

这篇文章详细介绍了插入排序的原理、实现及其优化方法。如果你有任何问题或建议，欢迎在评论区留言！

Java算法系列

1. Java算法系列第一篇：排序算法概述与实现

2. Java算法系列第二篇：快速排序算法详解

3. Java算法系列第三篇：归并排序算法详解

4. Java算法系列第四篇：堆排序算法详解

5. Java算法系列第五篇：插入排序算法详解

6. Java算法系列第六篇：选择排序算法详解

7. Java算法系列第七篇：桶排序算法详解

8. Java算法系列第八篇：基数排序算法详解

9. Java算法系列第九篇：计数排序算法详解

10. Java算法系列第十篇：希尔排序算法详解

11. Java算法系列第十一篇：计数排序算法详解

12. Java算法系列第十二篇：归并排序算法详解

13. Java算法系列第十三篇：树排序算法详解

14. Java算法系列第十四篇：外部排序算法详解

15. Java算法系列第十五篇：分布式排序算法详解

16. Java算法系列第十六篇：贪心算法详解

17. Java算法系列第十七篇：动态规划详解

18. Java算法系列第十八篇：图算法中的最短路径算法

19. Java算法系列第十九篇：最小生成树算法详解

20. Java算法系列第二十篇：图遍历算法详解