冒泡排序各种实现

冒泡排序是最简单的排序算法，其时间复杂度O(n2)，但是在数据量不是很大的情况，经优化过的冒泡乃是一种高效的算法。

简单粗暴的思路：

前面元素依次和后面元素进行比较
如果前面元素大于后面元素则进行交换（这样进行一轮交换后，第一个元素就是最小的）
重复上面，直到前面所有位置的元素都跟后面的元素进行了一轮比较，排序完成。

按照这个思路写出的代码如下：


    public static void bubble(int arr[]) {
        int i, j;
        int length = arr.length;
        for (i = 0; i < length; i++) {
            for (j = i + 1; j < length; j++) {
                if (arr[i] > arr[j]) {
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
//                    swap(arr[i], arr[j]);这样是不行的
                }
            }
        }
    }

验证：

    public static void main(String[] args) {
        int array[] = {45, 234, 13, 45, 565, 76, 5, 3, 23, 45};
        bubble(array);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
//output:
3
5
13
23
45
45
45
76
234
565

我们看一下另一个版本的冒泡，设数据的大小为N，其思路是这样的:

依次比较相邻的二个数据
如果前面数据大于后面的数据，就将二个数据交换（这样进行一轮交换后，即数组的第0个数据到N-1个数据进行一次遍历，最大的元素就沉在数组的末尾N-1的位置）
N=N-1，重复上面，直到N=0或者没有交换发生

按照这个想法写出的代码如下：


    public void bubble2(int arr[]) {
        int i, j;
        int length = arr.length;
        for (i = length - 1; 0 < i; i--) {
            for (j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }

下面进行优化，很明显如果一轮比较没有发生交换，说明数组已经是有序的了。


    public void bubble3(int arr[]) {
        int j;
        int len = arr.length;
        Boolean flag = Boolean.TRUE;
        while (flag) {
            flag = Boolean.FALSE;
            for (j = 1; j < len; j++)
                if (arr[j - 1] > arr[j]) {
                    int tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                    flag = Boolean.TRUE;
                }
            len--;
        }
    }

进一步优化，如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。


    public void bubble4(int arr[]) {
        int j, len;
        int flag = arr.length;
        while (flag > 0) {
            len = flag;
            flag = 0;
            for (j = 1; j < len; j++)
                if (arr[j - 1] > arr[j]) {
                    int tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                    flag = j;
                }
        }
    }

这里可以观看冒泡排序的动画演示：

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html