插入排序详细解说

逃离我推掉我的手 2022-10-27 01:44 203阅读 0赞

## 思路分析 ##

插入排序是将整个区间被分 **有序区间**和**无序区间**。每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入

我们这里使用bound来作为无序区间的第一个元素，需要将这个元素和前面的每一个元素依次进行比较，此处排出来的顺序应该为升序，也就是将bound元素放到合适的地方即可

此处令cur为bound的前一个元素，如果cur与bound比较，bound小与粗人，那么就将cur往后移一位（bound位置的元素事先存起来，以保证不被覆盖），然后将cur减一，再与之前存好的bound元素进行比较，直到放到合适的位置（bound元素不再小于cur的元素），就停止比较，以上过程就是一次比较的过程，重复上面的步骤，就可以完成整个数组的排序。

## 图解 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70]

## 代码示例 ##

//插入排序------
        public static void insertSort(int[] array){
        
            for (int bound = 1; bound < array.length; bound++){
        
                int v = array[bound];
                int cur = bound - 1;//已排好序列的最后一个元素
                for (; cur >= 0; cur--){
        
                    //循环和前面已排好序的元素一次比较
                    if (array[cur] < v){
        
                        array[cur + 1] = array[cur];
                    }else {
        
                        break;
                    }
                }
                array[cur + 1] = v;
            }
        }

## 两个特性 ##

1.数据量少的时候，速度快  
2.数据接近有序的时候，速度快

## 性能分析 ##

**时间复杂度：**  
最好：O(N) \{数据有序\}  
平均：O(N^2)  
最坏：O(N^2) \{数组逆序\}

**空间复杂度：**  
O(1)

**稳定性：**  
稳定排序

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70]: /images/20221024/0e8154dc04e6414b9833b08fc31c6808.png