起泡排序是最简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误(大于或小于)就把它们交换过来。这样数组中最大或最小的元素会一步一步的浮到数组的最后。直到重复执行 n-1次起泡循环，数组变成一个有序数组。
图解：
描述：第一步到第三步index总是小于index+1 所以不选择置换，当第四步 97 > 45 置换元素，置换后继续遍历，第五步
97 > 11置换元素。此时已遍历到数组末尾，所以无需继续遍历。最大值97已经遍历到数组末尾完成一次循环起泡动作。
整个数组一共需要完成 （数组长度 - 1） 次起泡动作。
java源代码：
/** * 起泡排序，返回一个排好序的数组 * i i+1 * 7 16 9 11 16 18 7 - 16 不换 * i i+1 * 7 16 9 11 16 18 16 - 9 换 * i i+1 * 7 9 16 11 16 18 16 - 11 换 * i i+1 * 7 9 11 16 16 18 16 - 16 不换 * ------------------------------ 准备从7执行下一个起泡的循环 * 7 9 11 16 16 18 * @param array * @return */ public static Integer[] bubbleOrder(Integer[] array){ for(Integer i = 0;i<array.length-1;i++) { for (Integer j = 0; j < array.length - (i + 1); j++) { if (array[j] > array[j + 1]) { Integer temp = array[j + 1]; array[j + 1] = array[j]; array[j] = temp; } } } return array; }插入排序是一整直观的，易理解的排序算法。即一个元素再元素前找位置插入进去，不断的通过找寻位置插入移位，使得整个数组变得有序。虽然简单易懂，但是不断的移位插入使得算法时间复杂度基本保持在O(n2)。
图解：
描述：设置p遍历指针 q查位指针，在遍历时，q找寻比p的合适位置，既大于左边又小于右边的位置。找到一个key用来保存当前p指针的值。接着q从p的前一位开始向前遍历，这里的判断条件为如果q的值大于key那么q+1位置上的值就变成q的位置上的值，直到q找到比key值小的元素，使q+1位的值等于key值。
因为原位置值改变了，所以我们需要用key记录下原位置的初始值，也是在为初始值找到一个合适的插入位置。
源代码：
/** * 插入排序，返回一个排序好的数组 * 提出key = array[i] = 13 * j i j与key比较 j大把j给j+1然后j-- * 7 16 18 13 11 8 2 16 1 * j i j再与key比较 j大把j给j+1然后j-- * 7 16 18 18 11 8 2 16 1 * j i j再与key比较 key大跳出循环 把key给j+1 然后插入成功 * 7 16 16 18 11 8 2 16 1 * ----------------i------------- 准备执行下一个i 的插入 * 7 13 16 18 11 8 2 16 1 * @param array * @return */ public static Integer[] insertOrder(Integer[] array){ Integer key = 0; for(int i = 1 ; i<array.length ; i++){ key = array[i]; int j; for(j = i-1 ; (j >= 0 && array[j] > key ) ; j--){ array[j+1] = array[j]; } array[j+1] = key; } return array; }
选择排序算法也是很容易思考的排序算法，即里层遍历选择一个数组中最大或最小的元素，与当前外层遍历位的元素交换。每选择一次，就会确定一个排序位，数组排序成功一共需要选择n-1次。
图解：
描述：p是遍历的工作指针，min是查找数组中最小元素的指针，当第一步min为0，第二步13小于21，min为1，第三步9小于13，min为2 。 第四步 88大于9，所以min不变，总之就是记录最小的元素的下标。循环结束后，使min和外层遍历位index位交换元素位置。也就是图中 9 和 21 交换。外层继续循环 从index+1开始继续遍历。直到数组排序完成。
源代码：
/** * 选择排序，找到最小的，记录下标 * index = i //index记录最小的下标 * j 如果array[j]小于array[index] 那么就用index记录最小的下标 index = 1 * (3) 2 7 6 8 9 * j //7大不记录 * 3 (2） 7 6 8 9 * 知道j走完了 有小的就用index记录下标 * 3 (2) 7 6 8 9 * 最后把array[index]和array{i}换位置 * （2） 3 7 6 8 9 * @param array * @return */ public static Integer[] selectOrder(Integer[] array){ Integer index,temp; Integer time = array.length - 1; for(int i = 0 ; i < time ; i++){ index = i; for(int j = i+1;j<array.length;j++){ if(array[index] > array[j]){ index = j; } } temp = array[index]; array[index] = array[i]; array[i] = temp; index++; } return array; }希尔排序是由1959年Shell发明，第一个打破了O(n^2)的魔咒，是简单插入排序的改进版。与插入排序不同的是，希尔排序事先设置好了增量，即把序列按照一定的间隔分组，对每组分别进行插入排序。希尔排序的核心在于间隔序列的设定也就是增量值的设定，一个好的增量序列会给希尔排序带来质的变化。
图解：
描述：这时一个简单的长度为6的数组，动态定义间隔序列，算法为从1不断向上找最大的间隔序列 gap = gap*2 +1 一直向上找直到找到 gap < A.length/2为止。这里gap最大值为3 ， 也就是说最多分成三组，两两一组。，我们分别对每组元素进行排序。然后进行下一轮的gap计算分组，这时我们gap = gap /2 ，gap = 1 。整个序列分为一组做一次插入排序这时数组就变的有序了。
源代码：
/** * 希尔排序 传入数组和增量序列倍数 * @param array * @param addNum * @return */ public static Integer[] shellOrder(Integer[] array,Integer addNum){ Integer temp; Integer gap = 1; while(gap < array.length/addNum) { //计算最大的gap值 gap =gap*addNum+1; } while (gap> 0){ // 荡循环，维护gap for (Integer i = gap; i < array.length; i++) { //因gap位之前的元素都是每个组的第一位 temp = array[i]; // 从gap位开始 那么我们就从gap位开始对个元素做插入排序 Integer j; // 可能会问 每个元素所在的组不一样，怎么就插入了 for (j = i-gap; j >= 0 && array[j]> temp; j-=gap) { //正是因为每个元素所在的组不一样 那么我们在对每个元素做插入排序的时候 array[j+gap] = array[j]; //遍历的都是相隔gap位的元素，所以相隔gap位的元素都是一组的 } //做插入排序 array[j+gap] = temp; } gap = (int)Math.floor(gap/addNum); } return array; }归并排序是一种采用了分而治之的概念，一变二，二变四，四变八，不断的分治数组，直到数组为1不能再分了之后。返回当前的元素 采用两数组两指针合并的办法，不断的聚合收拢直至数组完成聚合，排序也随之完成。归并排序使用递归的话对程序的开销非常大，尤其是java会造成内存溢出的异常。由于在不断分裂又聚合的过程中开辟了太多数组资源，造成内存溢出。这里可以普及一下jvm内存管理，这里导致内存溢出的原因可能会有两种，一种是堆没有完成实例分配导致报内存溢出异常，另一种是java虚拟机栈无法扩展报内存溢出异常。
图解：
描述：上方图片描述了递归的分解和合并的过程，一分为二，向下取整留给左其余留给右。不断分解直到数组元素为1个时，不继续向下分解改为向上聚合。聚合 两个数组 看作两个栈 两个栈顶元素对比小的出去，不断加入到新数组中。完成聚合此时聚合后的数组是有序的。直到整个数组完成聚合，数组排序成功。
源代码：
/** * 归并排序入口 * 不需要设置其边界值的入口 * @param array * @return */ public static Integer[] defaultRecursionMergeOrder(Integer[] array){ if (array != null) array = Order.recursionMergeOrder(array,0,array.length-1); return array; } /** * 归并排序 * 传入待排序数组，以及待排序的左边界和右边界 * @param array * @param left * @param right * @return */ public static Integer[] recursionMergeOrder(Integer[] array,Integer left,Integer right){ if(left == right) { //如果数组左边界和右边界相同的话就不用继续递归归并了 并返回这个唯一的一个元素的数组 return new Integer[]{ array[right] }; } Integer mid = (right + left) / 2; //如果还可以二分归并那么算出中间值 Integer[] lArray = Order.recursionMergeOrder(array,left,mid); //左的给左 右的给右依次递归 Integer[] rArray = Order.recursionMergeOrder(array,mid+1,right); return leftMergeRight(lArray,rArray); //合并俩数组的值 } /** * 归并排序：和并两个有序数组 * @param leftArray * @param rightArray * @return */ public static Integer[] leftMergeRight(Integer[] leftArray,Integer[] rightArray){ Integer newLength = leftArray.length + rightArray.length; Integer[] newArray = new Integer[newLength]; //申请一个长度为左右数组长度之和的新数组 Integer point = 0,leftPoint = 0,rightPoint = 0; //数组元素比较和记录指针 while (leftPoint < leftArray.length && rightPoint < rightArray.length) { //两个引用分别指向两个数组 从0开始比较大的计入新数组中 新数组指针 比较者大的数组指针+1 newArray[point++] = leftArray[leftPoint] < rightArray[rightPoint] ? leftArray[leftPoint++] : rightArray[rightPoint++]; } //一旦左右数组有一个指针不能继续比较了，那么就对剩下的单个数组进行合并 while (leftPoint < leftArray.length) { //左面数组没合并玩 依次合并入新数组 newArray[point++] = leftArray[leftPoint++]; } while (rightPoint < rightArray.length) { //右边数组没合并完 依次合并入新数组 newArray[point++] = rightArray[rightPoint++]; } return newArray; }
前面讲的五种排序算法应用的场景比较少，我们一般不会使用这些排序算法为一组数据排序，当然还有更为快捷的算法，如快速排序和堆排序，时间复杂度低空间利用率低，排序效果块，都能进行原址排序。详情请见下一篇 易解排序算法 - 中 。
