冒泡排序

冒泡排序
强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

冒泡排序顾名思义就是整个过程就像气泡一样往上升,单向冒泡排序的基本思想是(假设由小到大排序):对于给定的 n 个记录,从第一个记录开始依次对相邻的两个记录进行比较,当前面的记录大于后面的记录时,交换位置,进行一轮比较和换位后,n 个记录中的最大记录将位于第 n位;然后对前(n-1)个记录进行第二轮比较;重复该过程直到进行比较的记录只剩下一个为止。

以数组 {45,3,2,5,7,8,32,9,1,22,0} 为例,冒泡排序的具体步骤如下:
[3, 2, 5, 7, 8, 32, 9, 1, 22, 0, 45]
[2, 3, 5, 7, 8, 9, 1, 22, 0, 32, 45]
[2, 3, 5, 7, 8, 1, 9, 0, 22, 32, 45]
[2, 3, 5, 7, 1, 8, 0, 9, 22, 32, 45]
[2, 3, 5, 1, 7, 0, 8, 9, 22, 32, 45]
[2, 3, 1, 5, 0, 7, 8, 9, 22, 32, 45]
[2, 1, 3, 0, 5, 7, 8, 9, 22, 32, 45]
[1, 2, 0, 3, 5, 7, 8, 9, 22, 32, 45]
[1, 0, 2, 3, 5, 7, 8, 9, 22, 32, 45]
[0, 1, 2, 3, 5, 7, 8, 9, 22, 32, 45]

程序示例如下:

/**
 * 冒泡排序: 先将最大的数沉下去,再进行第二次-1 的排序
 */
public class BubbleSorting {
    //temp 是过度字段
    int i,j,temp;
    //排序方法:从小到大排序
    public void sort(Integer[] arr){
        for(int i =1;i<arr.length;i++) {
            for(int j=0;j<arr.length-i;j++) {
                if(arr[j]>arr[j+1]) {
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
            System.out.println(Arrays.asList(arr).toString());
        }
    }

    public static void main(String[] args) {
        Integer[] s = {45,3,2,5,7,8,32,9,1,22,0};
        new BubbleSorting().sort(s);
    }

}

程序输入为:[0, 1, 2, 3, 5, 7, 8, 9, 22, 32, 45]

总结:若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数 C 和记录移动次数 M 均达到最小值:所以,冒泡排序最好的时间复杂度为 O(n) ;若初始文件是反序的,需要进行 n-1 趟排序。每趟排序要进行 n-i 次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:O(n^{2})冒泡排序的最坏时间复杂度为:O(n^{2})综上,因此冒泡排序总的平均时间复杂度为:O(n^{2})

本文来源程序猿进阶,由javajgs_com转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/8266

发表评论