【数据结构与算法之排序与查找】直接插入排序

系统管理员 2024-03-25 16:38 88阅读 0赞

#### 【数据结构与算法之排序与查找】直接插入排序 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之排序与查找】直接插入排序

直接插入排序是最简单的排序算法，因此也称为简单插入排序。

基本思想：第i 趟排序将序列中 第i+ 1个元素  k i + 1 k\_\{i + 1\} ki\+1 插入一个已经按值有序的子序列  ( k 1 , k 2 , . . . , k i ) (k\_1,k\_2,...,k\_i) (k1,k2,...,ki) 的合适位置，使得插入后的序列仍然保持按值有序。

举个栗子：

设数据元素序列为 \{5, 6, 3, 9, 2, 7, 1\}

将序列中的第一个元素5 看作一个有序的子序列，将后面的元素不断插入，过程如下：

![在这里插入图片描述][884f4efe61b845a3b2f1ddffe9938200.png_pic_center]

所以对于一个包含n 个元素的序列，可通过n -1 趟直接插入排序将原序列中的元素按值有序排列。

Java代码实现：【从小到大】

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: Sort
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 8:37
     */
    
    public class Sort {
        
    
        public static void insertSort(int[] array) {
        
    
            for (int i = 1; i < array.length; i++) {
        
                int tmp = array[i];
                int j = i - 1;
    
                while (j >= 0 && tmp < array[j]) {
        
                    array[j + 1] = array[j--];
    
                }
    
                array[j + 1] = tmp;
            }
        }
    
        public static void main(String[] args) {
        
    
            int[] array = {
        3, 12, 20, 1, 0, 5, 8, 19, 5};
            Sort.insertSort(array);
    
            for (int e : array) {
        
                System.out.print(e + " ");
            }
    
        }
    
    }

运行结果

![在这里插入图片描述][7f49881551de47789cd14150647240b7.png_pic_center]

每一趟插入排序的过程其实都是将 array\[i\] 并入有序子序列 \{array\[0\] ,…, array\[i - 1\]\} 中的过程：

1.  将array\[i\] 保存到tmp
2.  通过内层循环while 在有序子序列 \{array\[0\] ,…, array\[i - 1\]\} 中找到 array\[i\] 应该放置的位置。
    
    如果子序列中的元素比array\[i\] 大，就将子序列中的元素向后移动，直到在子序列中找到第1个比array\[i\] 小或者相等的元素，再将array\[i\] 插到这个元素的右边，即array\[j + 1\] 的位置。
    
    如果子序列中元素都比array\[i\] 大，那么就将array\[i\] 插入到索引为0的位置
3.  将tmp 赋值给array\[j + 1\] 完成一趟插入排序

[884f4efe61b845a3b2f1ddffe9938200.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/5a1a44df212348009d965856883c49d0.png
[7f49881551de47789cd14150647240b7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/42b9a81277e34a2586c6e4d116ba36a8.png