冒泡排序

冒泡排序，每次比较两个相邻的元素, 如果他们的顺序错误就把他们交换位置，核心是 冒泡。把数组中最大的那个往上冒，冒的过程就是和他相邻的元素交换。这个冒的过程就是内循环，循环次数为元素个数 - 外循环的次数 - 2（因为数组的后面冒出已经是有序的并且为了保证对于数组下标+1时不会索引异常）；经过了一个冒的过程，可以使一个最小的元素冒出来，如果数组里面有 n 个元素，就得冒 n-1 次，这就是外循环。时间复杂度为O(n*n)。

• java实现

public class Bubble {

    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N - i - 1; j++) {
                if (!less(a[j], a[j + 1])) {
                    exch(a, j, j + 1);
                }
            }
        }
    }

    public static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    public static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i - 1])) {
                return false;
            }
        }
        return true;
    }

    public static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        String[] a = {"80", "30", "60", "40", "20", "10", "50", "70"};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

• python实现

class Bubble:
    def sort(self, data):
        for i in range(len(data)):
            for j in range(len(data) - i - 1):
                if not self.less(data[j], data[j + 1]):
                    self.exch(data, j, j + 1)

    def less(self, x, y):
        return x < y

    def exch(self, data, i, min_index):
        data[i], data[min_index] = data[min_index], data[i]


if __name__ == "__main__":
    s = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
    bubble = Bubble()
    bubble.sort(s)
    print(s)

可以对冒泡排序进行两个阶段优化：

1. 优化外循环

当里面一层循环在某次扫描中没有执行交换，则说明此时数组已经全部有序列，无需再扫描了。因此，增加一个标记，每次发生交换，就标记，如果某次循环完没有标记，则说明已经完成排序。例如n个元素已经是有序的，只循环一次判断是否需要冒泡即可，不需要再接着循环。

• java实现

    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            boolean flag = true;
            for (int j = 0; j < N - i - 1; j++) {
                if (!less(a[j], a[j + 1])) {
                    exch(a, j, j + 1);
                    flag = false;
                }
            }
            if (flag) break;
        }
    }

• python实现

    def sort(self, data):
        for i in range(len(data)):
            flag = True
            for j in range(len(data) - i - 1):
                if not self.less(data[j], data[j + 1]):
                    self.exch(data, j, j + 1)
                    flag = False
            if flag:
                break

2. 优化内循环

目前的内部循环次数是[0...N - i - 2]，因为后面的元素已经是有序的不需要再查询了。其实内部循环的界限也是可以再优化的：例如，如果R[i...n]已是有序区间，上次的扫描区间是R[0..i]，记上次扫描时最后 一次执行交换的位置为lastIndex，则lastIndex在0与i之间，不难发现R[lastIndex...n]区间也是有序的，否则这个区间也会发生交换；所以下次扫描区间就可以由R[0...i] 缩减到[0...lastIndex]。

另外，可以与优化方式1的标志位结合起来。创建temp 和lastIndex两个变量，当外部循环开始时将temp赋值给lastIndex，如果内部循环没有发生顺序更换，则lastIndex 与temp是相等的，直接break掉外部循环。

• java实现

    public static void sort(Comparable[] a) {
        int N = a.length;
        int temp = N - 1;
        int lastIndex;
        for (int i = 0; i < N; i++) {
            lastIndex = temp;
            for (int j = 0; j < lastIndex; j++) {
                if (!less(a[j], a[j + 1])) {
                    exch(a, j, j + 1);
                    temp = j;
                }
            }
            if (lastIndex == temp) break;
        }
    }

• python 实现

    def sort(self, data):
        temp = len(data) - 1
        for i in range(len(data)):
            last_index = temp
            for j in range(last_index):
                if not self.less(data[j], data[j + 1]):
                    self.exch(data, j, j + 1)
                    temp = j
            if last_index == temp:
                break

插入排序与冒泡排序很相似，都是O(n*n)时间复杂度，但是两者的原理是不同的：插入排序是先使前面的有序，后面的每一个插入到前面的有序数组里，当索引到最后一个元素时，整个序列就变成有序的了；冒泡排序是一直相邻两个元素比较，将较大的冒到后面，直到整个序列有序。