美文网首页
排序算法:冒泡排序O(n)~O(n^2)

排序算法:冒泡排序O(n)~O(n^2)

作者: Alisallon | 来源:发表于2021-06-08 19:46 被阅读0次

核心思想

冒泡排序是基于相邻元素相互比较的排序算法,算法的核心有2点:

  1. 内外双循环:
  • 外循环遍历数组;
  • 内循环遍历数组并比较相邻元素大小和互换位置。
  1. 内循环结束后都会把最大/最小值移动到数组的头部或末尾。

时间复杂度和稳定性

当数组的元素是 n 个 0 到 m 之间的整数时,最坏时间复杂度是O(n),最好时间复杂度是O(n^2),空间复杂度是O(1)。
冒泡排序是一个稳定的排序算法。

适用范围

无限制。

Java 实现

注意点

  1. 排序什么时候完成:
  • 使用一个flag来标记内循环是否发生过数据交换,如果没有发生过,表示排序完成。
  1. 基于“内循环结束后都会把最大/最小值移动到数组的头部或末尾”这一点,尽量减少内循环的循环次数:
  • 外循环循环到第i次时,内循环无需比较数组末尾的i个元素。
import java.util.Arrays;

/**
 * 冒泡排序
 *
 * @author Alisallon
 * Created on 2021/6/5 2:45 下午.
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] nums = {2, 3, 6, 8, 4, 2, 1, 8, 9, 4, 8, 0, 2, 3, 4, 9, 6, 5, 7, -3, -1, -7, -4, -9, -10, -5, -6};
        System.out.println(Arrays.toString(sort(nums)));
    }

    /**
     * 冒泡排序实现
     *
     * @param nums 原数组
     * @return 排序后的数组
     */
    private static int[] sort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            // 标记内循环是否发生过数据交换
            boolean hadSwap = false;
            // 内循环无需比较数组末尾的i个元素
            int maxIndex = nums.length - 1 - i;
            for (int j = 0; j < maxIndex; j++) {
                if (nums[j] > nums[j + 1]) {
                    // 交换方式1
//                    int temp = nums[j];
//                    nums[j] = nums[j + 1];
//                    nums[j + 1] = temp;
                    // 交换方式2(三次相同异或计算即可)
                    nums[j] = nums[j] ^ nums[j + 1];
                    nums[j + 1] = nums[j] ^ nums[j + 1];
                    nums[j] = nums[j] ^ nums[j + 1];
                    // 标记已发生过数据交换
                    hadSwap = true;
                }
            }
            if (!hadSwap) {
                // 没有发生数据交换,排序完成
                return nums;
            }
        }
        return nums;
    }
}

相关文章

  • python 八大算法

    排序算法总结 排序算法 平均时间复杂度 冒泡排序O(n2) 选择排序O(n2) 插入排序O(n2) 希尔排序O(n...

  • 排序算法小总结

    排序算法时间复杂度冒泡排序O(n2)选择排序O(n2)插入排序O(n2)希尔排序O(n1.5)快速排序O(N*lo...

  • 算法比较

    排序算法平均时间复杂度冒泡排序O(n²)选择排序O(n²)插入排序O(n²)希尔排序O(n1.5)快速排序O(N*...

  • 排序算法总结

    排序算法总结 分类编程技术 排序算法平均时间复杂度 冒泡排序O(n2) 选择排序O(n2) 插入排序O(n2) 希...

  • LeetCode-排序算法

    LeetCode-排序算法 时间复杂度 排序算法平均时间复杂度冒泡排序O(n2)选择排序O(n2)插入排序O(n2...

  • 2020-11-19 排序算法一(冒泡和快排多种实现)

    主流的排序算法 时间复杂度为O(n^2):冒泡排序选择排序插入排序希尔排序(介于O(n^2)与O(nlogn)之间...

  • 排序

    冒泡排序:最简单的排序算法之一;平均复杂度O(n2),最好的情况O(n),最坏的排序O(n2) 选择排序: 快速排...

  • 常见排序算法总结

    排序算法总结 冒泡排序 时间复杂度 O(n2) 【 O(n)~On(n2)】空间复杂度 O(1)稳定性 ...

  • 算法时间复杂度比较

    排序算法比较 排序算法平均时间最差情形稳定度额外空间备注冒泡O(n2)O(n2)稳定O(1)n小的时候较好交换O(...

  • 排序技术

    排序算法平均时间复杂度最好最差空间复杂度稳定性直接插入排序O(n2)O(n)O(n2)O(1)稳定冒泡排序O(n2...

网友评论

      本文标题:排序算法:冒泡排序O(n)~O(n^2)

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