算法（二）初等排序前篇[插入和冒泡排序]
前言
排序是算法的基础，排序有很多种方法，有些方法实现起来很简单，但是效率较差，我们可以将这些排序的方法称之为初等排序。这篇文章我们就来学习初等排序中的插入排序和冒泡排序。
1.插入排序
插入排序比较容易想到，思路与打扑克时排列牌的顺序是类似的。比如我们左手拿牌，然后用右手将牌从左到右，从小到大来排序，这就需要我们把需要进行排列的牌抽出来放到合适的位置，并且不断的重复，直到牌的顺序排好，这个过程就可以理解为插入排序。
图解插入排序
插入排序过程中会将需要排序的数组，分为两个部分：已排序部分和未排序部分，如下图所示。
从图中可以看出这个数组分为两个部分，其中下标为0、1、2的元素为已排列部分，其余的则为未排列部分。
插入的排序规则： 将开头元素视为以排序部分。接着执行如下的处理，直到没有未排序部分。 - 取出未排序部分的开头元素赋值给临时保存数据的变量v。 - 在已排列的部分将所有比v大的元素向后移动一个位置。 - 将取出的元素v插入空位。
按照这个规则，我们来举一个简单的例子。我们对数组 a={8,3,1,5,2,1} 进行从小到大排序，数组a如下图所示。
我们对数组a进行排序，共需要5个步骤： 1.接着我们将a[0]=8视为已排序，我们从a[1]开始操作，将a[1]的值3取出，3要小于a[0]的值8，因此将a[0]的值8移动到a[1]，再把3插入到a[0]，如下图所示。
2.a[2]的值1要比a[0]和a[1]的值要小，则将a[0]和a[1]顺次向后移一个位置，然后将1插入a[0]，如下图所示。
3.将a[3]中的5拿出来，比它大的是a[2]的8，因此8向后移，将5插入a[3]。如下图所示。
4.将a[4]中2拿出来，发现a[1]、a[2]、a[3]中的值都比2大，因此将它们依次向后移，将2插入到a[1]中，如下图所示。
5.最后将a[5]中的1移到合适的位置，过程和上面一样，最后的排序结果如下图所示。
实现插入排序
接下来要实现插入排序，针对下图来定义变量。
如上图所示，i代表未排序部分的开头元素，v是临时保存a[i]值的变量， j代表已排序部分v要插入的位置。 根据定义的这三个变量，插入排序的实现思路就是：外层循环i从1开始自增，并在每次循环开始时将a[i]的值保存在v中；内层循环则是j从i-1开始向前自减，并将比v大的元素从a[j]移动到a[j+1]，并将v插入到当前j+1的位置（内层循环后j会先自减1，因此插入的地方则是j+1的位置），当j等于-1或者a[j]小于等于v则内层循环结束。 接下来我们用代码来实现插入排序，如下所示。
其中负责打印数组的ArrayUtils类如下所示。
输出结果为： {8, 3, 1, 5, 2, 1} {1, 1, 2, 3, 5, 8}
插入排序的复杂度
根据算法（一）时间复杂度所讲的，我们来算一下插入排序的时间复杂度。在最坏的情况下，每个i循环都需要执行i次移动，总共需要1+2+......+n-1=n²/2+n/2，根据此前讲过的推导大O阶的规则的我们得出插入排序的时间复杂度为O(n²)。
2.冒泡排序
冒泡排序应该是开发者最容易理解的排序算法，它的基本思想就是每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。需要进行排序的元素则向水中的气泡一样慢慢的移向水面。
图解冒泡排序
与插入排序一样，需要进行冒泡排序的数组也分为已排序部分和未排序部分。 冒泡排序的规则为：从数组末尾开始依次比较相邻的两个元素，如果大小关系相反则交换位置，直到数组中不再有顺序相反的相邻元素。
我们对数组 a={5,3,2,4,1} 进行从小到大排序，排序过程如下所示。 第一轮排序：
我们将数组末尾的a[4]的值和a[3]的值进行对比，发现a[4]的值比a[3]的值小，则将它们交换，再接着对剩下的相邻的两个元素进行对比和交换，最终得到的结果为a={1,5,3,2,4}，已排序的部分的元素为1。
第二轮排序：
首先对比a[3]和a[4]的值，发现a[3]的值比a[4]的值小，则不需要进行排序。最终得到的结果为a={1,2,5,3,4}，已排序部分的元素为1、2。
第三轮排序：
经过第三轮排序，已排序部分的元素为1、2、3。
第四轮排序：
经过四轮排序我们最终得到的结果为a={1,2,3,4,5}
实现冒泡排序
实现插入排序时，我们要先定义两个变量，i为循环变量，表示未排序部分的开头元素，从数组开头向末尾移动。j也为循环变量，用于对未排序部分中相邻元素两两比较，从数组的末尾n-1开始减小到 i 结束(i=1)。
代码实现如下所示。
其中ArrayUtils的printArray方法此前讲过，这里就不再给出，打印结果为： {5, 3, 2, 4, 1} {1, 2, 3, 4, 5}
冒泡排序的复杂度
最坏的情况下，冒泡排序对未排序部分的相邻元素进行了(n-1)+(n-2)+(n-3)+……+1次比较，也就是n²/2+n/2次比较，根据推导大O阶的规则我们得出冒泡排序的时间复杂度为O(n²)。