必须掌握的八种基本排序算法:冒泡排序

1.1 原理

  这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。


image.png
1.2 代码
    private static void sort(int[] array) throws Exception {
        if (array == null || array.length == 0) {
            throw new Exception("the array is null or no element...");
        }
        System.out.println("冒泡排序优化前...");
        int n = array.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
            System.out.println("第" + (i + 1) + "轮后: " + Arrays.toString(array));
        }
    }

    第1轮后: [3, 1, 4, 2, 7, 8, 6, 5, 9]
    第2轮后: [1, 3, 2, 4, 7, 6, 5, 8, 9]
    第3轮后: [1, 2, 3, 4, 6, 5, 7, 8, 9]
    第4轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    第5轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    第6轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    第7轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    第8轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    第9轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]

  从上述的log打印中,可以看出来:在第4轮时就已经排好序了,所以从第5轮到第9轮均是无用操作。

    private static void optimizeSort(int[] array) throws Exception {
        if (array == null || array.length == 0) {
            throw new Exception("the array is null or no element...");
        }
        System.out.println("冒泡排序优化后...");
        int n = array.length;
        for (int i = 0; i < n; i++) {
            // 设定一个排序完成的标记
            // 若为 true,则表示此次循环没有进行交换,即待排序列已经有序,排序已然完成
            boolean success = true;
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    success = false;
                }
            }
            if (success) {
                break;
            }
            System.out.println("第" + (i + 1) + "轮后: " + Arrays.toString(array));
        }
    }
    第1轮后: [3, 1, 4, 2, 7, 8, 6, 5, 9]
    第2轮后: [1, 3, 2, 4, 7, 6, 5, 8, 9]
    第3轮后: [1, 2, 3, 4, 6, 5, 7, 8, 9]
    第4轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
1.3 复杂度
  • 时间复杂度:
    两层循环,第1次遍历n次(n个元素),第二次遍历n-1次,... 依次类推。因此,表达式如下:
    n + (n - 1) + (n - 2) + ... + 1 = n * (n + 1) / 2 = O(n^2)
  • 空间复杂度:
    没有利用新的数组来帮助完成排序算法,我们认为其空间复杂度为O(1)
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 本文总结十大经典排序算法及变形,并提供Java实现。参考文章:十大经典排序算法总结(Java语言实现)快速排序算法...
    Steven1997阅读 17,726评论 3 185
  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可...
    意识流丶阅读 3,221评论 2 9
  • 排序算法基础 排序算法,是一种能将一串数据按照特定的排序方式进行排列的一种算法,一个排序算法的好坏,主要从时间复杂...
    jackyshan阅读 4,037评论 3 11
  • 写给张雨(3) 傻里傻气母亲啊, 是你把 傻里傻气的孩子 带到世上! 感谢有你, 让这个世界 多了一份童真! 看起...
    东原郡人阅读 102评论 0 1
  • 关系攻略 一、如何好好说话 1 控制语速 不说太快,联系自我一背书模式就容易加快语速啊,一紧张就会支吾 2 控制声...
    思远同学阅读 372评论 4 0