Java实现:冒泡排序

Java实现:冒泡排序冒泡排序

Java实现:冒泡排序"

三种冒泡排序写法

目录


一、原始写法

一边比较一边向后两两交换,将最大值冒泡到最后一位

最外层的 for 循环每经过一轮,剩余数字中的最大值被移动到当前轮次的最后一位

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;
}

二、原始写法改进

这种写法相对于第一种写法的优点是:如果一轮比较中没有发生过交换,则立即停止排序,因为此时剩余数字一定已经有序了。

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;

        //每次循环都将最大的移到右边,如果返回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;
}

三、改进写法

while

最外层的 while 循环每经过一轮,剩余数字中的最大值仍然是被移动到当前轮次的最后一位

indexOfLastUnsortedElement         swappedIndex

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

swapped

当一轮比较中从头到尾都没有发生过交换,则表示整个列表已经有序,排序完成

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;
}

今天的文章Java实现:冒泡排序分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/28950.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注