排序算法——冒泡排序分析

访客 阅读:204 2021-06-15 11:20:19 评论:0

一、冒泡排序

       冒泡排序是一种基础的交换排序。首先来看一个例子。由8个数字组成一个无序数列{5,8,6,3,9,2,1,7},希望按照从小到大的顺序对其进行排序。

       按照冒泡排序的思想,相邻的元素两两比较,当一个元素大于右侧相邻元素时,交换它们的位置;当一个元素小于或等于右侧相邻元素时,位置不变

       经过第一轮排序元素9作为数列中最大的元素,飘到了最右侧。这时第一轮就结束了。数列最右侧元素9的位置可以认为是一个有序区。这个有序区目前只有1个元素。56382179。 

       接下来进行第2轮排序。第2轮排序结束后,数列右侧的有序区有了2个元素。顺序如下。53621789.

       53216 789      第3轮

       3215 6789      第4轮

       213 56789      第5轮 

       12 356789      第6轮 

       1 2356789      第7轮   

        

共8个元素 
 
第一轮比较7次。 
第二轮比较6次。 
第三轮比较5次。 
第四轮比较4次。 
第五轮比较3次。 
第六轮比较2次。 
第七轮比较1次。

       到此为止,所有的元素都是有序的,这就是冒泡排序的整体思路。

       冒泡排序是一种稳定的排序,值相等的元素并不会打乱原本的顺序。由于该排序算法每一轮都有遍历所有元素,总共遍历(元素数量-1)轮,所以平均时间复杂度是O(n²)

       

public static void sort(int array[]) { 
        for (int i = 0; i < array.length - 1; i++) { 
            for (int j = 0; j < array.length - i - 1; j++) { 
                int tmp = 0; 
                //当1个元素大于右边相邻元素时,交换位置 
                if (array[j] > array[j + 1]) { 
                    tmp = array[j]; 
                    array[j] = array[j + 1]; 
                    array[j + 1] = tmp; 
                } 
            } 
        } 
    } 
 
    public static void main(String[] args) { 
        int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7}; 
        sort(array); 
        System.out.println(Arrays.toString(array)); 
    }

         代码非常简单,使用双循环进行排序。外部循环控制所有的回合,内部循环实现每一轮的冒泡处理,先进行元素比较,再进行元素交换。

二、冒泡排序的优化。

       原始的冒泡排序有哪些可以优化的点呢?仍然以{5,8,6,3,9,2,1,7}这个数列为例,当排序算法分别执行到第6、第7轮时,数列状态如下。

      12 356789   第6轮。

      1 2356789   第7轮。

      经过第6轮排序后整个数列已经是有序的了。可是排序算法仍然继续执行了第7轮排序。如果能判断出数列已经有序,并做出标记,那么剩下的几轮排序就不必执行了,可以提前结束工作。

      冒泡排序第2版代码如下:

public static void sort1(int array[]) { 
        for (int i = 0; i < array.length - 1; i++) { 
            //有序标记,每一轮的初始值都是true\ 
            boolean isSorted=true; 
            for (int j = 0; j < array.length - i - 1; j++) { 
                int tmp = 0; 
                //当1个元素大于右边相邻元素时,交换位置 
                if (array[j] > array[j + 1]) { 
                    tmp = array[j]; 
                    array[j] = array[j + 1]; 
                    array[j + 1] = tmp; 
                    //因为有元素进行交换,所以不是有序的,标记变为false 
                    isSorted=false; 
                } 
            } 
 
            if (isSorted){ 
                break; 
            } 
 
        } 
    }

       与第1版代码相比,第2版代码做了小小的改动,利用布尔变量isSorted作为标记。如果在本轮排序中,没有元素交换,则说明数列已经有序,然后直接跳出大循环。

三、再次优化

        其实右边的许多元素已经是有序的了,可以每一轮还是白白地比较了许多次。这个问题的关键点在于对数列有序区的界定。 按照现有的逻辑,有序区的长度和排序的轮数是相等的。例如地1轮排序过后的有序区长度是1,第2轮排序过后有序区长度是2。。。。。。

       实际上,数列真正的有序区长度可能会大于这个长度,如上述例子中再第2轮排序时,后面5个元素与实际上都是有序区了。因此后面的多次元素比较是没有意义的。那么,如何避免这种情况呢?我们可以在每一轮排序后,记录下来最后一次元素交换的位置,该位置即为无序数列的边界,在往后就是有序区了。

        冒泡排序第3版代码如下:

        

public static void sort2(int array[]) { 
        for (int i = 0; i < array.length - 1; i++) { 
            //有序标记,每一轮的初始值都是true 
            //无序数列的边界,每次比较只需要比到这里为止 
            int sortBorder = array.length - 1; 
            boolean isSorted = true; 
            for (int j = 0; j < sortBorder; j++) { 
                int tmp = 0; 
                //当1个元素大于右边相邻元素时,交换位置 
                if (array[j] > array[j + 1]) { 
                    tmp = array[j]; 
                    array[j] = array[j + 1]; 
                    array[j + 1] = tmp; 
                    //因为有元素进行交换,所以不是有序的,标记变为false 
                    isSorted = false; 
                    //把无序数列的边界更新为最后一次交换元素的位置 
                    sortBorder = j; 
                } 
            } 
 
            if (isSorted) { 
                break; 
            } 
 
        } 
    } 

         在第3版代码中,sortBorder就是无序数列的边界。在每一轮排序过程中,处于sortBorder之后的元素就不需要再进行比较了,肯定是有序的。


标签:程序员
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号