排序算法之——冒泡排序分析

引言

好吧，据说是最简单的排序算法之一。

思路

排序过程中较小元素从后往前冒，因此称为冒泡排序；
过程如下：

• 通过从后向前依次的比较相邻两个数的大小
• 重复地走访过要排序的序列，一次比较两个元素，如果它们的顺序错误则交换

上图是我们随机生成的原始数组，接下来进行一趟排序：

i=0，这趟排序完成后，如上图中右边数组所示，发送交换的情况是：2/5；2/7;2/4;2/3; 然后比较2与1,不需要交换；最后比较最后两个元素，1/8 。从这趟排序我们可以感受到2往前冒了，但是碰到了更小的元素，没能坐到第一把交椅；接下来就是1与8交换，1成功坐得第一把交椅；

i=1该趟排序，主要是解决了二当家属于谁的问题。其中发生了5和7的交换以及2与8的交换。老二成功成为了二当家的。

左边橙色代码已经排序好的了元素，右边绿色的待排序元素中不存在更小的元素。

剩下的几趟排序就不一一分析了。

代码

/**
* 冒泡排序
* 通过从后向前依次的比较相邻两个数的大小；
* 重复地走访过要排序的序列，一次比较两个元素，如果它们的顺序错误则交换；
* 每趟排序后较小的元素冒上来，因此称为冒泡排序；
*
* @param a
* @param <E>
*/
public static <E extends Comparable<? super E>> void bubbleSort(E[] a) {
for (int i = 0; i < a.length; i++) {
boolean swapped = false;//优化：若没有发生交换，则说明已经有序了，可以直接返回
for (int j = a.length - 1; j > i; j--) {//从后向前比较,因此j取数组最后一个元素
if (a[j].compareTo(a[j - 1]) < 0) {//比较相邻两个数的大小
swap(a, j, j - 1);
swapped = true;
}
}
//System.out.println("i="+i +":"+ Arrays.toString(a));
if (!swapped) {
//若没有发生交换，则说明已经有序了，可以直接返回
System.out.println("returned");
return;
}
}
}


private static <E> void swap(E[] array, int i, int j) {
E tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}

生成随机数组的代码如下:

public static void main(String[] args) {
/* Random rand = new Random();
Integer [] array = rand.ints(8000,1,500000).boxed()
.collect(Collectors.toList()).toArray(new Integer[]{});*/

List<Integer> list = IntStream.range(1, 9).boxed().collect(Collectors.toList());
Collections.shuffle(list);
Integer[] array = list.toArray(new Integer[]{});


System.out.println(Arrays.toString(array));

bubbleSort(array);
System.out.println(Arrays.toString(array));
}

复杂度和稳定性

• 时间复杂度

最坏情况下是

• 稳定性

大小相等的情况下可以不交换，所以冒泡排序是稳定的；