【排序算法】插入排序原理及Java实现

亦凉 2022-08-21 10:42 208阅读 0赞

## 1、基本思想 ##

直接插入排序的基本操作是将一个记录插入到已经排好的有序表中，从而得到一个新的、记录数增1的有序表。对于给定的一组记录，初始时假定第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直到最后一个记录插到有序序列中为止。

## 2、复杂度分析 ##

当最好的情况，也就是要排序的表本身就是有序的，此时只有数据比较，没有数据移动，时间复杂度为*O(n)*。  
当最坏的情况，即待排序的表是逆序的情况，此时需要比较次数为：*2+3+…+n=(n+2)(n-1)/2* 次,而记录移动的最大值也达到了 *(n+4)(n-1)/2* 次.  
如果排序记录是随机的，那么根据概率相同的原则，平均比较和移动次数约为次![这里写图片描述][20160427091142307]，因此，得出直接插入排序发的时间复杂度为![这里写图片描述][20160427091101931]。从这里可以看出，同样的是时间复杂度![这里写图片描述][20160427091101931]，直接插入排序法比冒泡和简单选择排序的性能要好一些。

## 3、排序过程如下 ##

以数组\{38,65,97,76,13,27,49\}为例，  
![这里写图片描述][20160426213126568]

## 4、Java实现如下 ##

public class InsertSort {
        public static void insertSort(int[] a) {
            int i, j, insertNote;// 要插入的数据
            for (i = 1; i < a.length; i++) {
       // 从数组的第二个元素开始循环将数组中的元素插入
                insertNote = a[i];// 设置数组中的第2个元素为第一次循环要插入的数据
                j = i - 1;
                while (j >= 0 && insertNote < a[j]) {
                    a[j + 1] = a[j];// 如果要插入的元素小于第j个元素,就将第j个元素向后移动
                    j--;
                }
                a[j + 1] = insertNote;// 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
            }
        }
    
        public static void main(String[] args) {
            int a[] = { 38,65,97,76,13,27,49 };
            insertSort(a);
            System.out.println(Arrays.toString(a));
        }
    }

[20160427091142307]: https://img-blog.csdn.net/20160427091142307
[20160427091101931]: /images/20220724/25def71bacda4d50a2bbcae1a943a1c1.png
[20160426213126568]: /images/20220724/1b29a28301f2420ba24716984f6a573c.png