简单排序之插入排序

青旅半醒 2022-05-22 04:04 190阅读 0赞

**一、算法原理**

插入排序法：所谓插入排序法乃是将一个数目插入该占据的位置。

假设我们输入的是 “53，27，36，15，69, 42” 我们从第二个数字开始，这个数字是27，我们的任务只要看看27有没有正确的位置，我们的做法是和这个数字左边的数字来比，因此我们比较27和53，27比53小，所以我们就交换27和53，原来的排列就变成了“27, 53, 36, 15, 69, 42 ”

接下来，我们看第3个数字有没有在正确的位置。这个数字是36，它的左边数字是53，36比53小，所以我们将36和53交换，排列变成了 “27,36, 53, 15, 69, 42 “我们必须继续看36有没有在正确的位置，36的左边是27，27比36小，36就维持不动了,这时候排序还是“27, 36, 53, 15, 69, 42 “。

再来看第四个数字，这个数字是15，我们将15和它左边的数字相比，都比15大，所以就将15一路往左移动，这时候排序变成了 “15, 27, 36, 53, 69, 42 ”。

再来看第五个数字，这个数字是69，我们将69和它左边的数字相比，都比69小，所以就69维持不动了，这时候排序变成了 “15, 27, 36, 53, 69, 42 ”

最后，我们检查第六个数字，这个数字是42，42必须往左移，一直移到42的左边是36为止，所以我们的排列就变成了 “15, 27, 36, 42 ,53, 69”排序因此完成了。  
![这里写图片描述][70]  
所谓插入排序法，就是检查第i个数字，如果在它的左边的数字比它大，进行交换，这个动作一直继续下去，直到这个数字的左边数字比它还要小，就可以停止了。插入排序法主要的回圈有两个变数：i和j，每一次执行这个回圈，就会将第i个数字放到左边恰当的位置去。

**二、算法描述**

1、从第一个元素开始，该元素可以认为已经被排序。  
2、取出下一个元素，在已经排序的元素序列中从后向前扫描。  
3、如果该元素（已排序）大于新元素，则将该元素移到下一位置。  
4、重复步骤3，直到找到已排序的元素小于或者大于新元素的位置。  
5、将新元素插入到该位置。  
6、重复步骤2。

**三、效率分析**

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况如下。  
最好情况：序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。  
最坏情况：序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。  
直接插入排序属于稳定的排序，最坏时间复杂度为O(n^2)，最好时间复杂度为O(n)，空间复杂度为O(1)。  
插入排序的赋值操作是比较操作的次数加上(n-1)次。  
因此，插入排序不适合对于数据量比较大的排序应用。

**四、代码实现**

package cn.DataStructures.Sort;
    
    public class InsertSort {
        public static void main(String[] args) {
            int []arr={
       12,20,5,16,15,1,2,100,30,45,23,9};
            System.out.println("排序前：");
            printSort(arr);
            System.out.println("排序中：");
            insertSort(arr);
        }
        public static void insertSort(int []arr){
            int j;
            int temp;
            for(int i=1;i<arr.length;i++){
                temp=arr[i];
                j=i-1;
                while(j>=0&&arr[j]>temp){
                    arr[j+1]=arr[j];
                    j--;
    
                }
                arr[j+1]=temp;
                System.out.println("第"+i+"趟排序");
                printSort(arr);     
            }
    
        }
        //打印数组
                public static void printSort(int []arr){
                    StringBuilder res=new StringBuilder();
                    res.append("[");
                    for(int i=0;i<arr.length;i++){
                        if(i==arr.length-1)
                            res.append(arr[i]+"]");
                        else
                            res.append(arr[i]+",");
                    }
                    System.out.println(res.toString());
                }
    }

[70]: /images/20220522/d5f6f9d3c3664e709ea4e705fbbcc486.png