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

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

引言

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

思路

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

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

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

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 */public static > 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 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 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));}

复杂度和稳定性

时间复杂度

稳定性

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。