关于java:排序算法入门之插入排序

借用《算法导论》里的例子，就是咱们打牌的时候，每新拿一张牌都会把它按程序插入，这，其实就是插入排序。

齐姐申明：尽管咱们用打牌的例子，然而可不能学胡适学生啊。

对于数组来说怎么做呢？

有一个重要的思维，叫做 挡板法，就是用挡板把数组分成两个区间：

挡板右边：已排序
挡板左边：未排序

那么排序分三步走：

最后挡板是在数组的最右边，index = 0 的地位，也就是保障了已排序区间里一个数都没有，或者也能够蕴含一个数啦；
核心思想就是：
顺次遍历 未排序区间 里的元素，在已排序区间里找到正确的地位插入；
反复这个过程，直到未排序区间为空。

第一步，挡板最后在这里：

第二步，
把 2 插入已排序区间的正确地位，变成：

反复这个步骤，把 1 排好：

最初把 0 排好：

那代码也很简略：

public void insertionSort(int[] input) {if (input.length <= 1) {return;}
    for(int i = 1; i < input.length; i++) {int tmp = input[i];
        int j = i - 1;
        while(j >= 0 && input[j] > tmp) {input[j+1] = input[j];
            j --;
        }
        input[j+1] = tmp;
    }
}

咱们来剖析一下这个算法的时空复杂度。

对于工夫复杂度有两个要点：

是形容随着自变量的增长，所需工夫的增长率；
是渐近线复杂度，就是说
- 不看系数
- 只看最高阶项

那么咱们关怀的 worst case 的状况就是：
如果数组是近乎倒序的，每次插入都要在数组的第一个地位插入，那么已排序区间内的所有的元素都要往后挪动一位，这一步均匀是 O(n)，那么反复 n 次就是 O(n^2).

重点是一个峰值的概念，并不是累计应用的空间。
这里是 O(1) 没什么好说的。

引入一个概念：sorted in place，也就是 原地排序。

原地排序就是指空间复杂度为 O(1) 的算法，因为没有占用额定的空间，就是原地打转嘛。

其实 in-place 的思维并不是只在排序算法里有，只不过排序算法是一个最广为人知的例子罢了。实质上就是一个 节俭应用空间 的思维。

然而对于排序算法，只剖析它的时空复杂度是不够的，还有另外一个重要指标：

这个是排序算法的一个重要指标，意思是元素之间的绝对程序是否放弃了不变。

比如说：{5, 2, 2, 1, 0}

这个数组排序实现后这外面的两个 2 的绝对程序没有变，那么这个排序就是一个稳固排序。

那有同学可能就想，程序变了又有什么关系呢？

其实，在理论工作中咱们排序的对象不会只是一个数字，而是一个个的对象 (object)，那么先依照对象的一个性质来排序，再依照另一个性质来排序，那就不心愿原来的那个程序被扭转了。如同有点形象，咱们举个例子。

比方在股票交易零碎里，有买卖双方的报价，那是如何匹配的呢？

先依照价格排序；
在相等的价格中，依照出价的 工夫程序 来排序。

那么一搬来说零碎会维持一个按工夫排序的价格序列，那么此时只须要用一个 具备稳定性的排序算法，再依照价格大小来排序就好了。因为稳定性的排序算法能够放弃大小雷同的两个对象仍维持着原来的工夫程序。

那么插入排序是否是稳定性的排序呢？答案是必定的。因为在咱们插入新元素的时候是从后往前查看，并不是像打牌的时候轻易插一个地位不能保障绝对程序。

大家能够看下上面的动画就十分分明了～

插入排序其实是有很大的优化空间的，你能够搜一下“希尔排序”。

在刚开始学习的时候，深度诚然重要，但因为广度不够，如果学的太深可能会很苦楚，一个知识点就无穷无尽的延展，这并不是一个高效的学习形式。

所以如果工夫无限，就要做好深度和广度的均衡：

在罕用常考的知识点上多花工夫精力，谋求深度；
在一些拓展性的知识点上点到为止，先晓得有这么回事就行。

放弃 open minded 的心态，前期就会有质的进步。

如果你喜爱这篇文章，记得给我点赞留言哦～你们的反对和认可，就是我创作的最大能源，咱们下篇文章见！

我是小齐，纽约程序媛，终生学习者，每天晚上 9 点，云自习室里不见不散！

更多干货文章见我的 Github: https://github.com/xiaoqi6666…

插入排序

举个例子：{5, 2, 1, 0}

工夫复杂度

空间复杂度

稳定性

优化