八大排序算法——冒泡排序
摘要
冒泡排序是排序算法中比较简单的一个排序。它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，知道没有要交换的数据元素为止。
冒泡排序的原理
首先我们肯定要有一个数组，里面存放着待排序的数据元素，我们如果需要把比较大的元素排在前面，把小的元素排在后面，那么需要从尾到头开始下面的比较操作。
1.从尾部开始比较相邻的两个元素，如果尾部的元素比前面的大，就交换两个元素的位置。
2.往前对每个相邻的元素都做这样的比较、交换操作，这样到数组头部时，第一个元素成为最大的元素
3.重新从尾部开始第1、2步的操作，除了在这之前已经排好的元素
4.继续对越来越少的数据进行比较、交换操作，知道没有可比较的数据为止，排序完成。
我们来看一个冒泡排序的例子，加入我们要把12、35、99、18、76这5个数从大到小进行排序，那么数越大，越需要把它放在前面。冒泡排序的思想就是在每次遍历一遍未排序的数列后，将一个数据元素浮上去。
我们从后开始遍历，首先比较18和76两个数，发现76比18大，就把这两个数交换顺序，得到12 35 99 76 18；接着比较76和99，发现76比99小，所以不用交换；接着比较99和35，发现99比35大，交换顺序；接着比较99和12，发现99比12大，交换顺序，最终第1趟排序的结果变成了99 12 35 76 18，排序的过程如下图所示：
经过第一趟排序，我们已经都找到最大的元素，接下来的第二趟排序就只对剩下的4个元素进行排序，第2趟排序的过程如下图所示
经过第二趟排序，结果为99 76 12 35 18,接下来应该进行第3趟排序，剩下的元素越来越少，比较的次数也在减少。
第三躺排序结果应该是99 76 35 12 18，第四趟排序的结果是99 76 35 18 12，经过4趟排序后，只剩下一个12需要排序了，这时已经没有可比较的元素了，所以排序完成。
这个算法让我想起了小时候在操场上排队跑步，老师总是说：“高的站前面，低的站后面”。我们一开始并不一定会站到准确的位置上，接着老师又说：“你比前面的高，和前面的缓缓，还高，再和前面的换换”，这样就找到了自己的位置。
冒泡排序的代码实现
通过冒泡排序的原理，我们应该很容易地写出实现代码了。首先我们需要从后往前地遍历待排序的数组，然后重复这个步骤，继续遍历剩下的待排序的数列，这样我们需要一个双重循环去完成这个算法、
public class BubbleSort {
private int[] array;
public BubbleSort(int[] array){
this.array = array;
}
/**
* 从小到大
*/
public void sort(){
int length = array.length;
if(length >0){
for(int i =0; i<length;i++){
for(int j=0;j<length-i;j++){
if (array[j] > array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
/**
* 从大到小
*/
public void sort2(){
int length = array.length;
if(length>0){
for(int i=length-1;i>0;i--){
for (int j=length-1;j>length-1-i;j--){
if (array[j] > array[j-1]){
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
}
}
}
public void print(){
for (int i =0;i<array.length;i++){
System.out.println(array[i]);
}
}
}冒泡排序算法特点以及性能分析
通过冒泡排序算法的思想，我们发现冒泡排序算法在每轮排序中会使一个元素排到一端，也就是说，在最坏的情况，每次比较之后度需要交换位置，所以这种算法的时间复杂度是O(n2)。其实冒泡排序在最好的情况下，时间复杂度可以达到O(n)，这当然是在待排序数列有序的情况下。在待排序数列本身就是我们想要的排序结果时，时间复杂度就是O(n)，因为只需要一轮排序并且不用交换。但是实际上这种情况很少，所以冒泡排序的平均时间复杂度是O(n2)。
对于空间复杂度来说，冒泡排序用到的额外的存储空间就只有一个，那就是用于交换位置的临时变量，其他的所有操作都是在原有待排序列上处理的，所以空间复杂度是O(1)。
冒泡排序是稳定的，因为在比较的过程中，只有最后一个元素比前面的大时才会对它们交换位置并向上冒出，对于同样大消息的元素是不需要交换位置的。