冒泡排序在最佳情况下时间复杂度为O(n)

一颗蔬菜 2019-08-19 AM 99℃ 0条

本文摘抄并修改自Mr.Seven大佬的博客
Mr.Seven大佬提供了最佳和最坏情况下时间复杂度都是O(n^2)的代码实现,本文对原代码进行了优化,使得该算法在最佳情况下的时间复杂度为O(n)。

1.算法演示:

bubble-sort.gif

2.冒泡排序时间和空间复杂度

平均时间复杂度最好情况最坏情况空间复杂度
O(n²)O(n)O(n²)O(1)

冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).

Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.

3.代码实现

冒泡排序需要两个嵌套的循环. 其中, 外层循环移动游标; 内层循环遍历游标及之后(或之前)的元素, 通过两两交换的方式, 每次只确保该内循环结束位置排序正确, 然后内层循环周期结束, 交由外层循环往后(或前)移动游标, 随即开始下一轮内层循环, 以此类推, 直至循环结束.

最佳和最坏情况下都是O(n^2)的写法

public int[] bubblesort(int[] nums) {
        for (int i = nums.length - 1;i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j + 1];
                    nums[j + 1] = nums[j];
                    nums[j] = tmp;
                    System.out.print(Arrays.toString(nums));
                }
            }
        }
        return nums;
    }

最佳情况下时间复杂度为O(n)的写法

public int[] bubblesort(int[] nums) {
        boolean ordered = true;
        for (int i = nums.length - 1;i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j + 1];
                    nums[j + 1] = nums[j];
                    nums[j] = tmp;
                    ordered = false;
                    System.out.print(Arrays.toString(nums));
                }
            }
            if (ordered == true)
                return nums;
        }
        return nums;
    }
标签: 算法

非特殊说明,本博所有文章均为博主原创。