概念
冒泡排序算法需要遍历几次数组。每次遍历都要比较连续相邻的元素，如果某一对相邻元素是降序，则互换它们的值，否则保持不变。由于较小的值像“气泡”一样逐渐浮向顶部，而较大的值沉向底部，所以叫冒泡排序。时间复杂度
最差的情况下，冒泡排序算法需要进行n-1次遍历。第一次遍历需要n-1次比较，第二次遍历需要n-2次比较，依次进行；因此比较总数为：(n-1)+(n-2)+…+2+1=n(n-1)/2=O(n2)冒泡排序的时间复杂度为O(n^2) /** * 冒泡排序（基本）：时间复杂度O(n^2) * @param array */ private static void bubbleSort (int[] array) { int len = array.length;// 数组长度 // 每次会确定几个数，比如第一次会确定一个最大值，第二次会确定最后两个值 for( int i = 1; i < len; i++ ) { // 从第0位开始，然后循环到最后一个没有确定排序的前一位(因为会有j+1代表最后一位) for( int j = 0; j < len - i; j++) { // 大于则互换 if( array[j] > array[j + 1] ) { array[j] = array[j] + array[j + 1];// 两者之和，比如 1和2 array[j + 1] = array[j] - array[j + 1];// 两者之和减去其中之一，则为另一个(1 + 2 - 2) array[j] = array[j] - array[j + 1];// 两者之和减去上面的值，即为另一个值(1 + 2 - 1) } } } } 优化 冒泡排序的效率比较低，所以我们要通过各种方法改进。在上例中，第四轮排序之后实际上整个数组已经是有序的了，最后两轮的比较没必要进行。注意：如果某次遍历中没有发生交换，那么就不必进行下一次遍历，因为所有元素已经排好了。 /** * 冒泡排序(优化) * @param array */ private static void bubbleSortOpt (int[] array) { boolean flag;// 是否执行排序的判断 int len = array.length;// 数组长度 // 每次会确定几个数，比如第一次会确定一个最大值，第二次会确定最后两个值 for( int i = 1; i < len; i++ ) { flag = false;//默认没执行 // 从第0位开始，然后循环到最后一个没有确定排序的前一位(因为会有j+1代表最后一位) for( int j = 0; j < len - i; j++) { // 大于则互换 if( array[j] > array[j + 1] ) { array[j] = array[j] + array[j + 1];// 两者之和，比如 1和2 array[j + 1] = array[j] - array[j + 1];// 两者之和减去其中之一，则为另一个(1 + 2 - 2) array[j] = array[j] - array[j + 1];// 两者之和减去上面的值，即为另一个值(1 + 2 - 1) flag = true;// 执行了，然后直接赋值true } } if( !flag ) return;// 如果没执行，则返回，因为没有排序的必要，已经排好了 } } 泛型冒泡排序 元素实现comparable接口。排序的元素需要实现comparable接口 class test implements Comparable<String> { private int aString; private int bString; @Override public int compareTo(String o) { if( aString > bString ) return 1; else if( aString < bString ) return -1; else return 0; } } /** * 泛型冒泡排序，使用Comparable对元素进行排序 * @param array */ public static <E extends Comparable<E>> void bubbleGenericTypeSort(E[] array) { boolean flag;// 是否执行排序的判断 int len = array.length;// 数组长度 E temp; // 每次会确定几个数，比如第一次会确定一个最大值，第二次会确定最后两个值 for( int i = 1; i < len; i++ ) { flag = false;//默认没执行 // 从第0位开始，然后循环到最后一个没有确定排序的前一位(因为会有j+1代表最后一位) for( int j = 0; j < len - i; j++) { // 大于则互换 if( array[j].compareTo( array[j + 1] ) > 0 ) { temp = array[j]; array[j] = array[j + 1];// 两者之和，比如 1和2 array[j + 1] = temp;// 两者之和减去其中之一，则为另一个(1 + 2 - 2) flag = true;// 执行了，然后直接赋值true } } if( !flag ) return;// 如果没执行，则返回，因为没有排序的必要，已经排好了 } }