常见算法之排序一【冒泡排序】

冒泡排序是我们编程刚入门基本都会接触的一个排序算法，以来它比较简洁，也比较形象。

它的思想就是，让每一个相邻的元素进行比较，假如他们不是按照升序或降序，则交换他们位置，重复这个操作，最大或最小的元素就像泡泡一样，升到了最上面，对剩下的元素重复这个操作，所有的元素就可以排好序了。

它的运作方式：

1.从头向后比较，假如相邻的元素之间的大小不是按升序或降序则将他们进行比较，若不是指定规则，则交换他们的位置

2.按照（1）的方式，依次对每一对进行比较，直至末尾

3.除了上述挑出的最大或最小元素外，重复以上的步奏，直到没有数字需要比较

所以我们可以看到，在不经仍任何优化的前提下，它需要比较的次数是o(n^2)，需要o(n) + o(1)的空间

下面我们看看代码：

    private static void swap(int[] array, int from, int to){
        int temp;
        temp = array[from];
        array[from] = array[to];
        array[to] = temp;
    }

    public static void sort(int[] array){

        for (int i = 0; i < array.length - 1; i++){
            for (int j = 0; j < array.length - i - 1; j++){
                if (array[j] > array[j+1]){
                    swap(array, j+1, j);
                }
            }
        }
    }

    public static void sort(int[] array){

        for (int i = 0; i < array.length - 1; i++){
            boolean flag = true;
            for (int j = 0; j < array.length - i - 1; j++){
                if (array[j] > array[j+1]) {
                    swap(array, j + 1, j);
                    flag = false;
                }
            }
            if (flag){
                return;
            }
        }
    }

    public static void sort(int[] array){
        int exchange = array.length - 1 ;           //最后一次交换的位置

        while(exchange > 0) {
            int bound = exchange;                   //每次交换的最后位置
            exchange  = 0;
            for (int j = 0; j < bound; j++){
                if (array[j] > array[j+1]) {
                    swap(array, j + 1, j);
                    exchange = j;
                }
            }
        }
    }

到这，我们总结一下：

冒泡排序，平均时间复杂度O(n^2),最差时间复杂度O(n^2),最优时间复杂度O(n),最差空间复杂度O(n) + O(1)

好了，假如你有更好的方法，欢迎留言讨论。