分类： Java
2013-12-30 21:05:13
一、简介
冒泡排序属于简单排序中的一种，是一种真的很简单的无脑排序。冒泡排序可以这么想，大的气泡往上冒。例如：有五个数字，(3,5,1,43,6)，要对这几个数字进行冒泡排序，期望的结果是(1,3,5,6,43)。
二、算法浅析
如上所述，我们要对(3,5,1,43,6)进行排序。
第一轮排序：
由3开始比较，大的数字往后移动。
第一次比较：3、5比较，3和5没有发生变动，变为---(3,5,1,43,6)
第二次比较：5、1比较，5和1 当然变动，变为---(3,1,5,43,6)
第三次比较：5、43比较，5比43小，数据位置保持不变---(3,1,5,43,6)
第四次比较：43、6比较，43比6大，数据位置变为---(3,1,5,6,43)
第一轮排序结束。此时发现最后一个位置的数字是最大的，说明我们已经排好一个位置了，剩下四个位置需要我们继续无脑排序，当然这种事情肯定是交给计算机来做。
第一轮排序只是排好一个位置的数据，所以我们要继续想第一轮排序一样排4次。总共需要排序4轮排序。其实不是真总共需要5轮才能排出正确的，4轮就可以了，因为后面的位置都已经确定了，最后剩下一个位置就没得排了。
其实，lz觉得，冒泡排序只是在一堆数据中找到最大的数据，然后给定一个位置，在找到次大的数据，再给定一个位置，置于位置你想怎么给就怎么给。
三、算法实现（Java）
class Array {
private long[] array; //排序数组
private int nElements; //数组元素
private int max; //数组最大容量
public Array(int max){
this.max = max;
array = new long[this.max];
nElements = 0;
}
/**
* 插入数据
* @param value 插入的数数据
* @return
*/
public boolean insert(long value){
if(nElements < this.max){
array[nElements] = value;
nElements ++;
return true;
}else{
return false;
}
}
/**
* 冒泡排序
* @return
*/
public void bubbleSort(){
for(int i = nElements - 1; i > 0; i--){
for(int j = 0; j < i; j++){
if(array[j] > array[i]){
swap(i, j);
}
}
}
}
/**
* 交换位置
* @param i
* @param j
*/
private void swap(int i,int j){
long tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
/**
* 转换为字符
*/
public String toString(){
String result = "";
for(int i=0; i < nElements; i++){
result += array[i]+" ";
}
return result;
}
}
测试代码：
public static void main(String[] args) {
Array array = new Array(100);
array.insert(3);
array.insert(5);
array.insert(1);
array.insert(43);
array.insert(6);
System.out.println("冒泡排序： ");
array.bubbleSort()
System.out.println(array.toString());
}
四、时间复杂度分析
由上述，既然是无脑排序，那么肯定会付出血一样的代价。性能肯定往下掉。如果排序n个数字，那么要进行n-1轮循环，第一轮进行n-1次比较，第二轮进行n-2次比较，一次类推，可得到进行了n*(n-1)/2次比较。时间复杂度就为O(n2)，这种排序效率不高。
注：第一次写博客，望各位路过大神指出错误。
