排序算法:冒泡排序

这篇具有很好参考价值的文章主要介绍了排序算法:冒泡排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

冒泡排序是入门级的算法,但也有一些有趣的玩法。通常来说,冒泡排序有三种写法:

  • 一边比较一边向后两两交换,将最大值 / 最小值冒泡到最后一位;
  • 经过优化的写法:使用一个变量记录当前轮次的比较是否发生过交换,如果没有发生交换表示已经有序,不再继续排序;
  • 进一步优化的写法:除了使用变量记录当前轮次是否发生交换外,再使用一个变量记录上次发生交换的位置,下一轮排序时到达上次交换的位置就停止比较。

冒泡排序的第一种写法

代码如下:

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 如果左边的数大于右边的数,则交换,保证右边的数字最大
                swap(arr, j, j + 1);
            }
        }
    }
}
// 交换元素
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

        最外层的 for 循环每经过一轮,剩余数字中的最大值就会被移动到当前轮次的最后一位,中途也会有一些相邻的数字经过交换变得有序。总共比较次数是  (n−1)+(n−2)+(n−3)+…+1。

        这种写法相当于相邻的数字两两比较,并且规定:“谁大谁站右边”。经过 n−1 轮,数字就从小到大排序完成了。整个过程看起来就像一个个气泡不断上浮,这也是“冒泡排序法”名字的由来。

冒泡排序的第二种写法

代码如下:

public static void bubbleSort(int[] arr) {
    // 初始时 swapped 为 true,否则排序过程无法启动
    boolean swapped = true;
    for (int i = 0; i < arr.length - 1; i++) {
        // 如果没有发生过交换,说明剩余部分已经有序,排序完成
        if (!swapped) break;
        // 设置 swapped 为 false,如果发生交换,则将其置为 true
        swapped = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 如果左边的数大于右边的数,则交换,保证右边的数字最大
                swap(arr, j, j + 1);
                // 表示发生了交换
                swapped = true;
            }
        }
    }
}
// 交换元素
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

        最外层的 for 循环每经过一轮,剩余数字中的最大值仍然是被移动到当前轮次的最后一位。这种写法相对于第一种写法的优点是:如果一轮比较中没有发生过交换,则立即停止排序,因为此时剩余数字一定已经有序了。

冒泡排序的第三种写法

第三种写法比较少见,它是在第二种写法的基础上进一步优化:

public static void bubbleSort(int[] arr) {
    boolean swapped = true;
    // 最后一个没有经过排序的元素的下标
    int indexOfLastUnsortedElement = arr.length - 1;
    // 上次发生交换的位置
    int swappedIndex = -1;
    while (swapped) {
        swapped = false;
        for (int i = 0; i < indexOfLastUnsortedElement; i++) {
            if (arr[i] > arr[i + 1]) {
                // 如果左边的数大于右边的数,则交换,保证右边的数字最大
                swap(arr, i, i + 1);
                // 表示发生了交换
                swapped = true;
                // 更新交换的位置
                swappedIndex = i;
            }
        }
        // 最后一个没有经过排序的元素的下标就是最后一次发生交换的位置
        indexOfLastUnsortedElement = swappedIndex;
    }
}
// 交换元素
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

经过再一次的优化,代码看起来就稍微有点复杂了。最外层的 while 循环每经过一轮,剩余数字中的最大值仍然是被移动到当前轮次的最后一位。

在下一轮比较时,只需比较到上一轮比较中,最后一次发生交换的位置即可。因为后面的所有元素都没有发生过交换,必然已经有序了。

*交换的技巧

一般来说,交换数组中两个数字的函数如下:

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

更好的方案是通过位运算完成数字交换:

arr[i] = arr[i] ^ arr[j];
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[i] ^ arr[j];

使用异或运算来进行交换时,要注意的是:参与运算的变量所指的地址不能相同,若有相同地址值参与运算,所得结果为0。文章来源地址https://www.toymoban.com/news/detail-664807.html

到了这里,关于排序算法:冒泡排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包