冒泡排序算法

发布时间:2024年01月02日

????????冒泡排序,也称为Bubble Sort,是一种简单的计算机科学排序算法。该算法重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序错误就把他们交换过来。这个过程会不断重复,直到没有再需要交换的相邻元素为止,也就是说该数列已经排序完成。

????????冒泡排序的名字来源于越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

????????冒泡排序的基本思想是通过对待排序序列从前向后(从下标较小的元素开始),依次对相邻两个元素的值进行两两比较,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就像水底下的气泡一样逐渐向上冒出。例如,对于一个待排序数组:3,9,-1,10,20,第一轮排序后,将最大的元素20固定到了最后的位置;然后在第二轮排序时,因为20的位置已经固定,所以只对前4个进行排序即可。

优化:

? ? ? ? 因为排序的过程中,个元素不断接近自己的位置,如果一次比较下来没有进行交换过,说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行交换过。从而减少不必要的比较。

推敲冒泡排序中:?
public class Sort {
    public static void main(String[] args) {
        //原始的冒泡排序
        int arr[] = {3, 9, -1, 10, -2};
        System.out.println("====排序前====");
        System.out.println("第0轮:" + Arrays.toString(arr));

        System.out.println("===开始排序===");
        int temp;
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第1轮:" + Arrays.toString(arr));

        for (int j = 0; j < arr.length - 1 - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第2轮:" + Arrays.toString(arr));

        for (int j = 0; j < arr.length - 1 - 2; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第3轮:" + Arrays.toString(arr));

        for (int j = 0; j < arr.length - 1 - 3; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第4轮:" + Arrays.toString(arr));
    }
}

?

?传统的冒泡排序:
public class BubbleSort {
    public static void main(String[] args) {
        int[] arrays = {12, 5, 8, 9, 4, 2};
        System.out.println("===排序之前的数据===");
        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + "\t");
        }
        System.out.println();

        //排序操作
        int temp = 0;
        for (int i = 0; i < arrays.length - 1; i++) {
            for (int j = 0; j < arrays.length - i - 1; j++) {
                if (arrays[j + 1] < arrays[j]) {
                    temp = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = temp;
                }
            }
        }
        System.out.println("===排序之后的数据===");
        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + "\t");
        }
        System.out.println();
    }
}

优化之后的冒泡排序:

优化的内容,只是检验该数组是否具备提前结束的必要,如果数组在每次排序后都需要进行交换,其运行的时间效率并不能提高。

public class BubbleSortUpdate {
    public static void main(String[] args) {
        int[] arrays = {5, 2, 8, 9, 4, 12};
        System.out.println("排序前:" + Arrays.toString(arrays));
        boolean flag = false;
        int temp = 0;
        for (int i = 0; i < arrays.length - 1; i++) {
            for (int j = 0; j < arrays.length - i - 1; j++) {
                if (arrays[j] > arrays[j + 1]) {
                    flag = true;
                    //代表在一次排序中,进行交换过,如果交换过,说明排序还未结束,下次接着进行排序
                    temp = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = temp;
                }
            }
            if (!flag) { //在一次排序中,一次都没有进行交换
                break;
            } else {
                flag = false; //重置flag,进行下次判断
            }
            System.out.println("轮数" + (i + 1) + " :" + Arrays.toString(arrays));
        }
        System.out.println("排序后:" + Arrays.toString(arrays));
    }
}

?

文章来源:https://blog.csdn.net/qq_58341172/article/details/135340772
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。