跟我学算法（四）——简单的插入排序

上一节我们一起看了快速排序，是不是很给力。这节我们来学习一个简单的排序，思想简单，实现起来也很简单。

插入排序，插入排序有两种，一种是直接插入，一种是二分插入。我们这里暂时先介绍直接插入，二分插入这个之后我们在说二分查找法的时候会提到。大家如果迫不及待的话，也可以在网上搜索一下相关的内容。这两种方法只是插入的方式不同而已。

插入排序，顾名思义就是把数字列表以一个一个元素的插入的方式来排序。

遍历整个数字列表，然后根据数字的位置插入到应该的位置完成排序。

我们以下面的数字序列为例介绍：6、9、3、10、4、5、1 。我们要排序这样的序列，

首先我们需要存储这个列表：

然后我们开始插入，首先6也就是第一个元素可以直接插入我们不用管，我们从第二个元素开始处理。

接着我们开始插入9，发现9比6大，所以不需要管，9就该在6后面。

这时候我们接着开始排序3，3和上一位比，发现3比9小，所以我们需要把9向后移动变为下图样子：

发现也比6小，于是6也移动变为下图样子：

发现已经到头了，所以把3插入到空位（首位），使序列变为

3、6、9、10、4、5、1 。

接着我们排序10，先与上一个比较，发现比9大不需要操作，继续排4，发现比10小，则10需要后移，发现比9小，9后移，比6小，6后移，发现比3大，所以可以把4放在原有的6的位置上。

5、1也是如此排序。

这样插入排序就完成了。这里实现的代码也很简单，我就先放上来了。之后我会总结之前所讲的所有的代码实现。

public static void main(String[] args) {

int[] x = {6, 9, 3, 10, 4, 5, 1};

insertionSort(x);

for (int i : x) {

System.out.print(i);

System.out.print(" ");

}

private static void insertionSort(int[] unsorted) {

for (int i = 1; i < unsorted.length; i++) {

if (unsorted[i] < unsorted[i - 1]) { int temp = unsorted[i]; int j = i; while (j > 0 && unsorted[j - 1] > temp) {

unsorted[j] = unsorted[j - 1];

j--;

}

unsorted[j] = temp;

}

最后总结一下时间复杂度吧，因为是双重循环，所以时间复杂度还是O(N²)，空间复杂度是O(1)，其实只是需要一个空间去存储一下这个待比较值而已，并没有需要额外的空间，还是用的以前的空间去排序的。

本文原创于本人博客，请访问 http://irfen.me

“跟我学算法（四）——简单的插入排序”的31个回复