简单排序之冒泡排序

冒泡排序算法运行起来非常慢，但在概念上它是排序算法中最简单的，因此冒泡排序算法是在刚开始研究排序技术时一个非常好的算法

冒泡排序例程执行如下：从队列的最左边开始，比较0号和1号位置的队员，如果左边的（0号）高，就让两个队员交换。如果右边的队员高，就什么也不做。然后右移一个位置，比较1号位置和2号位置的队员，和刚才一样，如果左边的队员高，则两个队员交换位置

public class bubbleSort {
    private long[] a;
    private int nElems;//队列中元素的个数

    public bubbleSort(int max){
        a=new long[max];
        nElems=0;
    }

    public void insert(long value){
        a[nElems]=value;
        nElems++;
    }

    public void display(){
        for(int j=0;j<nElems;j++){
            System.out.println(a[j]);
        }
    }

    public void sort(){
        int out,in;
        for(out=nElems-1;out>1;out--){
            for(in=0;in<out;in++){
                if(a[in]>a[in+1]){
                    swap(in,in+1);
                }
            }
        }
    }

    public void swap(int one,int two){
        long tmp=a[one];
        a[one]=a[two];
        a[two]=tmp;
    }

    public static void main(String[] args) {
        bubbleSort arr=new bubbleSort(100);

        arr.insert(77);
        arr.insert(99);
        arr.insert(44);
        arr.insert(55);
        arr.insert(22);
        arr.display();
        System.out.println("-----------------");
        arr.sort();
        arr.display();
    }
}

这个算法的思路是将最小的数据方外数组的最开始（数组下表为0），并将最大的数据项放在数组的最后（数组下表为nElems-1）,外层for循环的计数器out从数组的最后开始，即out等于nElems-1,每经过一次循环out减1.下标大于out的数据都已经是排好序的了。变量out在每完成一次内部循环（计数器in）后就左移一位，因此算法就不再处理那些已经排好序的数据了

内存for循环计数器in从数据的最开始算起，即in=0，每完成一次内部循环体加一，当它等于out时结束一次循环。在内层for循环体中，数组下标为in和in+1的两个数据进行比较，如果下标为in的数据项大于下标为in+1的数据项，则交换两个数据项

为了清晰起见，使用了一个独立swap（）方法来执行交换操作。它只是交换数组中的两个项的值，使用一个临时变量来存储第一个数据项的值，然后把第二项的值复制给第一项，之后让第二项的值等于临时变量的值。实际上，使用一个独立的swap（）方法不一定好，因为方法调用会增加一些额外的消耗。如果写自己使用的排序程序，最好将交换操作这段代码直接放到程序中，这样可以提高一些速度

不变性

在许多算法中，有些条件执行时是不变的。这些条件被称为不变性。认识不变性对理解算法是有用的。在一定的情况下她们对调试也有用；可以反复地检查不变性是否为真，如果不是的话就标记出错

在上面的程序中，不变性是指out右边的所有数据项为有序，在算法的整个运行过程中这个调教始终为真。（在第一趟排序开始前，尚未排序，因为out开始在数据项的最右边，没有数据项在普通的右边）

冒泡排序的效率

无论何时，只要看到一个循环嵌套在另一个循环里，就可以怀疑这个算法的运行时间未O(N²)级，所以冒泡排序的效率较慢