冒泡排序法示意图,冒泡排序法举例

首页 > 教育 > 作者:YD1662024-05-15 15:09:40

如果需要查看排版好看的请搜索微信公众号放开我我还能学

前言

这次我们介绍交换类排序中的冒泡排序,和简单插入排序相似,冒泡排序虽然时间复杂度也是O(n^2),但是对于有序数组的排序,时间复杂度也可以降为O(n),效率是比较高的。

冒泡排序

对数组[1, 4, 3, 2, 5, 6, 7, 8]从小到大排序,使用冒泡排序步骤如下:

  1. 依次比较相邻元素的大小。
  2. 如果前面的数据大于后面的数据,就交换这两个数据,然后向右移动一步,接着比较。经过第一轮的多次比较交换后,最大的数据就移动到了最后。
  3. 以此类推,经过 n 轮循环,数组就排序好了。

下图展示了冒泡排序的过程:

冒泡排序法示意图,冒泡排序法举例(1)

冒泡排序代码:

public static void sort(Comparable[] arr) {    int n = arr.length;    for (int i = n; i > 0; i--) {        for (int j = 1; j < i; j ) {            if (arr[j - 1].compareTo(arr[j]) > 0) {                swap(arr, j - 1, j);           }       }   } } ​ private static void swap(Object[] arr, int i, int j) {    Object t = arr[i];    arr[i] = arr[j];    arr[j] = t; }

优化1

如果对于一个有序的数组,使用上述冒泡排序的话,同样会执行n(n-1)/2次。实际上,在内循环中每一次比较只要没有发生逆序,即元素之间进行交换,那么就说明数组已经有序,这时已经可以退出程序了。

优化思路就是设置一个交换标志swapped,只要发生了交换,就让swapped = true,外部循环判断swapped是否为true,不是就结束程序,说明排序完成。

下面展示了优化思路的过程:

冒泡排序法示意图,冒泡排序法举例(2)

优化代码:

public static void sort(Comparable[] arr) {    int n = arr.length;    boolean swapped = false;    do {        swapped = false;        for (int i = 1; i < n; i ) {            if (arr[i - 1].compareTo(arr[i]) > 0) {                swap(arr, i - 1, i);                swapped = true;           }       }        // 每一次for循环将最大的元素放在了最后的位置        // 所以下一次排序, 最后的元素可以不再考虑,n--        n--;   } while (swapped); } ​ private static void swap(Object[] arr, int i, int j) {    Object t = arr[i];    arr[i] = arr[j];    arr[j] = t; }

优化2

在上述优化的基础上,我们还可以进一步优化。

对于数组:[1, 4, 3, 2, 5, 6, 7, 8],按照上面的优化思路,我们在第一轮比较时,需要让5, 6, 7, 8比较,第二轮比较时,需要让5, 6, 7比较,然而它们都是有序的排列,因此,我们是否能减少这些不必要的比较呢?答案是可以的。

优化思路就是每一轮循环完后,更新n的值,更新为最后一次交换的位置,这样,在此之后的元素都已经是有序的了,那么下次循环中就不用再比较了。

下图展示了优化思路的过程:

冒泡排序法示意图,冒泡排序法举例(3)

优化代码:

public static void sort(Comparable[] arr) { ​    int n = arr.length;    int newn;    do {        newn = 0;        for (int i = 1; i < n; i ) {            if (arr[i - 1].compareTo(arr[i]) > 0) {                swap(arr, i - 1, i);                // 记录最后一次的交换位置,在此之后的元素都是已经有序的,因此下一轮扫描中不再考虑                newn = i;           }       }        n = newn;   } while (newn > 0); } ​ private static void swap(Object[] arr, int i, int j) {    Object t = arr[i];    arr[i] = arr[j];    arr[j] = t; }

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.