Java常见排序算法-插入排序

一、算法介绍 

插入排序是一种简单且常用的排序算法，它的实现思路是将列表分为已排序和未排序两部分，每次从未排序部分取出一个元素，将它插入到已排序部分的适当位置，最终将列表排序完成。即将未排序的数值直接插入有序的一组数中，使得插入后的这组数还是有序的。

二、算法示意图

三、算法实现

    public static void main(String[] args) {
        int[] arr = {2, 5, 9, 4, 1, 6};
        System.out.println(Arrays.toString(arr));

        //算法核心
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
        //排序后结果输出
        System.out.println(Arrays.toString(arr));
    }

运行结果

[2, 5, 9, 4, 1, 6]
[1, 2, 4, 5, 6, 9] 

四、算法性能

插入排序的时间复杂度为O(n^2)，其中n是数组的长度。它是一种稳定的排序算法，并且在小规模数据或部分有序的数据上表现良好。然而，在处理大规模数据时，插入排序的性能可能不如其他更高效的排序算法。
优点：

1. 简单易实现： 插入排序算法的实现相对简单，易于理解和编写。

2. 原地排序： 插入排序只需要使用常数级别的额外空间，可以在原地进行排序，不需要额外的辅助空间。

3. 稳定性： 插入排序是一种稳定的排序算法，相等元素的相对顺序在排序后不会改变。

缺点：

1. 较慢的平均和最坏时间复杂度：插入排序的平均时间复杂度为O ( n 2 ) O(n^2)O(n 2 )，最坏情况下的时间复杂度也是O ( n 2 ) O(n^2)O(n 2)，其中n是待排序元素的数量。这使得插入排序在处理大规模数据时效率较低。

2. 对逆序数据的排序效率低：如果待排序的数据已经部分有序或者是逆序的，插入排序的效率会明显降低。当逆序度较高时，需要进行大量的元素移动操作，导致性能下降。

3. 不适用于大规模数据： 由于插入排序的时间复杂度较高，它在处理大规模数据时的性能表现不如其他更高级的排序算法（如快速排序、归并排序等）。

4. 不适用于链式结构： 插入排序需要频繁地访问和移动元素，对于链式结构来说，访问和移动的成本较高，因此不适用于链表等非随机访问结构的排序。

五、算法应用

插入排序算法在处理小规模数据集或部分排序的数据集时有着明显的优势，如低时间复杂度和简单的实现逻辑。然而，由于其较高的时间复杂度，对于大规模数据集，插入排序通常不是一个理想的选择。在实际应用中，应根据数据的规模和特性来选择合适的排序算法，以确保程序的效率和性能。