美文网首页算法
排序算法系列(1)——冒泡排序

排序算法系列(1)——冒泡排序

作者: 阿飞不理飞 | 来源:发表于2021-06-28 22:19 被阅读0次

    本着朴素的原则,笔者准备记录的第一个算法是入门级也是最简单、最容易实现的算法——冒泡排序

    冒泡排序呢,是交换排序的一种,什么是交换排序呢,其实很好理解哈,就可以简单的理解为:每次比较两个元素,然后判断两个元素是否符合排序规则,如果不符合即交换,交换后二者的相对位置即可确认。

    换个说法
    对于一个size=n的数组,进行交换排序:
    每进行一次交换,那么就能确定两个元素的相对位置。

    冒泡排序,对于一轮交换来说,如下图:
    第一轮,依次两两比较,如果不符合排序规则,直接交换位置,
    这样一直比较到最后两个元素,能够确定最后一个元素为最大值,
    那就能选择出最大的元素,放到了第n个位置。
    接下来只要对剩下的n-1个元素进行下一次冒泡即可~

    冒泡排序.png
        public void bubbleSort(int[] arrays, int start, int end) {
            if (start == end) {
                return;
            }
            for (int i = end; i >= start + 1; i--) {
                for (int j = start; j < i; j++) {
                    if (arrays[j] > arrays[j + 1]) {
                        swap(arrays, j, j + 1);
                    }
                }
            }
        }
    

    最后谈一下冒泡排序的算法复杂度,我们只要来看比较的次数:
    第一轮:n-1次比较
    第二轮:n-2次比较
    ……
    第n-1轮:1次比较
    综上:O(n^2)

    下一篇会继续展开交换排序的另一个算法,也是10大排序中最容易被问被手撸代码的算法——快速排序~

    相关文章

      网友评论

        本文标题:排序算法系列(1)——冒泡排序

        本文链接:https://www.haomeiwen.com/subject/gejcultx.html