排序算法之插入排序

来源百度百科：

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

一、基本思想
将数组分为两部分,一部分是已排序的数组,一部分是未排序的数组,将未排序的一个个取出来放到已排序数组的对应位置即可.

二、过程

最开始将数组第一个数默认为排好序的数组,后面的都为未排好序的数组
从未排好序的数组按顺序一个个取数
查找未排序数组中取出数字在排好序数组的位置,并且插入
继续循环未排好序的数组,直至未排序数组到最后一个元素即可
假设数组arr=｛36，26，27，2，10｝
我们默认arr1={36}为排好序的数组,arr2={26,27,2,10}为未排好序的数组
从未排好序的数组中取出26放入arr1的对应位置中,数组arr1={26,36},arr2={27,2,10}
从arr2中取出27放入arr1对应位置,arr1={26,27,36},arr2={2,10}
从arr2中取出2放入arr1对应位置,arr1={2,26,27,36},arr2={10}
从arr2中取出10放入arr1对应位置,arr1={2,10,26,27,36},arr2={}
此时arr2为空,arr1中所有元素都已排好序了

三、总结
代码：

 /**
     * 插入排序
     * @param arr   需要排序的数组
     */
    public static void insertSort(int[] arr){

        int length = arr.length;
        if (length <= 1)
            return;
        for (int i = 1; i < length; i++) {
            int value = arr[i];
            int j = i-1;
            //查找要插入的位置并移动数据
            for (; j >= 0 ; --j) {
                if(arr[j] > value){
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+1] = value;
        }
    }

四、插入排序的优化
在有序数组中查找要插入数值时,有可能数组长度过大,可以使用二分法查找插入位置,这样可以避免过多的比较。

五、结论

插入排序是原地排序算法
插入排序是稳定的排序算法
插入排序时间复杂度为O(n^2)

如果文章有错的地方欢迎指正，大家互相交流。

排序算法之插入排序

相关推荐