Java 与排序算法（3）：插入排序

悠悠 2024-03-17 09:49 46阅读 0赞

## 一、插入排序 ##

插入排序（Insertion Sort）是一种简单直观的排序算法，它的基本思想是将待排序序列分为已排序区间和未排序区间，然后每次从未排序区间取出一个元素，将其插入到已排序区间的合适位置中，使得插入后仍然保持已排序区间有序。重复这个过程，直到未排序区间为空，整个序列有序为止。

具体来说，插入排序的实现可以分为两个步骤：

1.  将待排序序列分为已排序区间和未排序区间。初始时，已排序区间只包含第一个元素，而未排序区间包含剩余的所有元素。
2.  从未排序区间取出一个元素，将其插入到已排序区间的合适位置中。插入时，我们从已排序区间的末尾开始比较，找到插入位置后将其插入，并将已排序区间的元素向后移动一位。  
    ‘  
    ![在这里插入图片描述][bec1a33bce204de99dc73e133488aec6.png]

## 二、插入排序的性质 ##

插入排序的性质包括：

1.  稳定性：插入排序是一种稳定排序算法，即相等的元素在排序前后的相对位置不变。
2.  原地排序：插入排序是一种原地排序算法，即不需要额外的空间来存储排序结果，只需要在原数组上进行操作即可。
3.  最好情况时间复杂度：当待排序序列已经有序时，插入排序的时间复杂度为 O(n)，即最优情况下的时间复杂度。
4.  最坏情况时间复杂度：当待排序序列是逆序的时，插入排序的时间复杂度为 O(n^2)，即最坏情况下的时间复杂度。
5.  平均情况时间复杂度：插入排序的平均情况时间复杂度为 O(n^2)。
6.  适用性：插入排序适用于小规模的数据排序，对于大规模数据排序效率较低。在实际应用中，插入排序通常用作其他排序算法的辅助排序算法，例如快速排序的子过程。

## 三、插入排序的变种 ##

插入排序有多种变种，以下是几种常见的变种：

1.  希尔排序（Shell Sort）：希尔排序是插入排序的改进版，它通过将待排序序列分成多个子序列，分别进行插入排序，最后再进行一次整体的插入排序，从而提高了排序效率。希尔排序的时间复杂度为 O(nlogn) ~ O(n^2)。
2.  折半插入排序（Binary Insertion Sort）：折半插入排序是插入排序的一种优化，它利用二分查找来寻找插入位置，从而减少了比较次数。折半插入排序的时间复杂度为 O(n^2)。
3.  带哨兵的插入排序（Insertion Sort with Sentinel）：带哨兵的插入排序是插入排序的一种优化，它通过在待排序序列的首位增加一个哨兵元素，从而避免了每次插入时的边界判断，提高了排序效率。带哨兵的插入排序的时间复杂度与普通插入排序相同，都为 O(n^2)。
4.  双向插入排序（Two-way Insertion Sort）：双向插入排序是插入排序的一种改进，它同时从前后两个方向遍历待排序序列，从而减少了比较次数和交换次数。双向插入排序的时间复杂度为 O(n^2)。
5.  链表插入排序（Insertion Sort for Linked List）：链表插入排序是插入排序的一种适用于链表的变种，它通过遍历链表，将每个节点插入到已排序链表的合适位置中，从而实现链表的排序。链表插入排序的时间复杂度为 O(n^2)。

总之，插入排序的变种有很多，每种变种都有其适用的场景和优缺点，选择合适的排序算法取决于具体的应用场景和需求。

## 四、Java 实现 ##

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

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;
            while (j >= 0 && arr[j] > key) {
        
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

在这个实现中，我们使用了一个外层循环来遍历待排序序列，从第二个元素开始，依次取出每个元素；内层循环从当前元素的前一个位置开始，依次比较已排序区间中的元素，找到插入位置后将其插入。重复这个过程，直到整个序列有序为止。

使用示例：

int[] arr = {
        4, 2, 1, 5, 3};
    insertionSort(arr);
    System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5]

在这个示例中，我们定义了一个数组 arr，使用插入排序对其进行排序，并输出排序结果。

## 五、插入排序的应用场景 ##

插入排序适用于以下场景：

1.  数据规模较小：插入排序的时间复杂度为 O(n^2)，对于数据规模较小的排序任务，插入排序的效率较高。
2.  数据基本有序：当待排序序列基本有序时，插入排序的时间复杂度可以达到 O(n)，即最优情况下的时间复杂度，因此插入排序在这种情况下的效率非常高。
3.  辅助排序算法：插入排序通常用作其他排序算法的辅助排序算法，例如快速排序的子过程。
4.  链表排序：插入排序是一种适用于链表的排序算法，因为链表的节点可以通过指针直接插入到已排序链表的合适位置中，从而避免了数组排序时的元素移动操作。

插入排序适用于数据规模较小、数据基本有序、辅助排序算法和链表排序等场景，但对于大规模数据排序，效率较低，因此在实际应用中需要根据具体情况选择合适的排序算法。

## 六、插入排序在spring 中的应用 ##

在 Spring 框架中，插入排序主要用于 BeanFactory 的初始化工作中，即对 BeanDefinitionMap 中的 BeanDefinition 进行排序。

在 Spring 中，BeanDefinitionMap 是一个 Map 类型的数据结构，其中包含了所有的 BeanDefinition。当 Spring 容器启动时，需要对 BeanDefinition 进行排序，以便在后续的 Bean 实例化过程中能够正确地解析依赖关系。

为了实现 BeanDefinition 的排序，Spring 使用了插入排序算法。具体来说，Spring 使用了一个名为 SimpleAliasRegistry 的类来管理 BeanDefinition，其中包含了一个名为 singletonObjects 的 Map，用于存储已经实例化的单例 Bean。在初始化 BeanFactory 时，Spring 会对 BeanDefinition 进行排序，并按照排序后的顺序依次实例化 Bean，并将其存储到 singletonObjects 中。

以下是 Spring 中插入排序的示例代码：

public class SimpleAliasRegistry implements AliasRegistry {
        
        private final Map<String, String> aliasMap = new ConcurrentHashMap<>(16);
    
        private final Map<String, Object> singletonObjects = new ConcurrentHashMap<>(256);
    
        private final Map<String, Object> earlySingletonObjects = new HashMap<>(16);
    
        private final Map<String, ObjectFactory<?>> singletonFactories = new HashMap<>(16);
    
        private final Set<String> registeredSingletons = new LinkedHashSet<>(256);
    
        private final List<String> singletonCurrentlyInCreation = new ArrayList<>(16);
    
        private volatile boolean singletonsCurrentlyInDestruction = false;
    
        private final Map<String, BeanDefinition> beanDefinitionMap = new ConcurrentHashMap<>(256);
    
        // ...
    
        public void registerBeanDefinition(String beanName, BeanDefinition beanDefinition) {
        
            this.beanDefinitionMap.put(beanName, beanDefinition);
            this.frozenBeanDefinitionNames = null;
        }
    
        public void preInstantiateSingletons() throws BeansException {
        
            List<String> beanNames = new ArrayList<>(this.beanDefinitionMap.keySet());
            // 对 BeanDefinition 进行排序
            Collections.sort(beanNames, new Comparator<String>() {
        
                @Override
                public int compare(String beanName1, String beanName2) {
        
                    return getPriority(beanName1) - getPriority(beanName2);
                }
            });
            // 依次实例化 Bean
            for (String beanName : beanNames) {
        
                BeanDefinition bd = this.beanDefinitionMap.get(beanName);
                if (bd.isSingleton()) {
        
                    if (bd.isLazyInit()) {
        
                        this.registerLazyInit(beanName, bd);
                    } else {
        
                        this.getBean(beanName);
                    }
                }
            }
        }
    
        // ...
    }

在这个示例代码中，我们可以看到 Spring 中使用了插入排序算法对 BeanDefinition 进行排序，并按照排序后的顺序依次实例化 Bean。

[bec1a33bce204de99dc73e133488aec6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/66650536fb2b49f4b233f67c64440b2d.png