知识点6：常见的排序算法

知识点6：常见的排序算法"/>

知识点6：常见的排序算法

说起排序算法，绝对是很多公司会要求现场手写的部分，虽然我还没有经历过这个，毕竟只面试了一次，但难免会在下一次出现。我原本是打算在一个章节里面全部写完所有的排序算法，但想来想去，与其一窝端，不明原理的记下来，不如拆分开来，一个一个地尝试去解释，说明。这样便不用担心面试官针对你的代码问问题而回答不出的尴尬，同时也可以加深自己的印象，所以在这里便将常见的排序算法拆分开来，今天先介绍最常见的冒泡排序及其优化方案。闲话少说，精彩立即开启：

冒泡算法

冒泡算法的原理：

通过对n位随意排放的数据，进行n-1次的数组排列。每次排列都把最大（或最小）的数据挪到数组的最前面。直到最终全部排列完毕，就好像水里的泡泡，一个个的往上挪，故而成为冒泡算法。

冒泡排序的算法（java为例）：

public class BubbleSort{public static void main(String[] args){bubbleSort(testArray);{/**冒泡排序算法*@author:邓明立*/private void bubbleSort(int[] arrays){for(int i=0;i<arrays.length;i++){for (int j = arrays.length-1; j > i; j--) {if(arrays[j] < arrays[j-1]){int t =arrays[j];arrays[j] = arrays[j-1];arrays[j-1] = t;}}}}
}

这是冒泡排序的一个实现，但是并不是最佳的冒泡排序，为什么呢？因为在我们这个程序中，是必须经历过所有的循环之后才能得出一个结果。那么，如果我们的数据足够简单，只循环一轮便可以得到结果呢？那我们还要继续执行所有的循环的话，可就在时间上有所偏颇了，怎么办呢？我们可以对程序进行如下的优化：添加一个监测标志符，用来监测程序是否进行过排序，如果程序进行过排序，则标注为true。表示上一次优化过一次了，这次可能还需要优化一次。如果为false，则表示上一次没有进行过优化，即排序已经完成，直接退出循环即可。在每次进行排序前，我们首先判断上一次有没有经历过排序，如果为true，则继续进行排序操作，并将标识符重定位为false。实例如下：

优化后的冒泡排序算法

public class BubbleSort{public static void main(String[] args){bubbleSort(testArray);{/**优化的冒泡排序算法*@author:邓明立*/private static void bubbleSort(int[] arrays){//添加监测控制符boolean isSort = true;for(int i=0;i<arrays.length-1;i++){if (isSort) {//如果为true,表示需要排序isSort = false;//退出标识符，如果程序没有经历过排序，则标识符为falsefor (int j = arrays.length-1; j > i; j--) {if(arrays[j] < arrays[j-1]){int t =arrays[j];arrays[j] = arrays[j-1];arrays[j-1] = t;isSort = true;//经历过排序之后，将标识符设为true/*** 后面这段为测试代码，方便动态观察排列过程，可忽略*/for(int k = 0;k< arrays.length;k++){System.out.print(arrays[k]+" ");}System.out.println();}}}   }   }}

至此，关于冒泡排序的讲解到一降落，但对于对冒泡排序的不同理解，其实也会有不同的实现方式，但其原理都是一样的，只是实现思维的不一样。所以本章可以作为你的思路参考，但不代表标准答案，因为并没有标准答案。或者说，你基于原理，根据你自己的思路写出来的冒泡排序算法，就是你自己的标准算法。因为那样才是你最理解它的地方。
下一章：常见的排序算法—-选择排序，敬请期待。