您的位置: 首页  >  文章  >  排序之冒泡排序

排序之冒泡排序

分类: 文章 • 2023-12-15 11:56:46

1.算法由来

越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
**

图片来自极客时间王争老师的算法课程

**

2.算法原理（升序）

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

3.算法分析

  1. 数组的初始状态是正序的，一趟扫描就可以完成排序，所需的比较次数C和移动次数M均为最小，Cm = n-1,
    Mm = 0;所以冒泡排序的最好时间复杂度为O(n)。
    例：0 1 2 3 4 5 6 7 8 9 长度为10
    两两比较对为[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9]共9次,n-1
    移动步数0
  2. 数组的初始状态是倒序的，需要进行n-1趟排序；每次排序次数为n-i；每次移动三次记录来交换位置。这种情况下，为最坏情况：Cm = (n-1)n/2 Mm = (n-1)n/23,所以冒泡排序的最坏时间复杂度为O(nn)。
  3. 综上，因此冒泡排序总的平均时间复杂度为O(n*n) 。

4.稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

5.图解（升序）

相邻元素之间依次进行比较：

排序之冒泡排序

经过n-1趟排序后：

排序之冒泡排序

分析整个算法的过程以及上述图片可以得出：

长度为n的数组

  1. 每一趟排序都确定一位最大的数并处于数组尾端，长度为n就需要进行n-1趟排序
  2. 每趟排序都需要进行n-i-1次排序
    分析：n = 6（下标从0开始） a = {4,5,6,3,2,1}，排序趟 = n-1 = 6-1=5次；
    每趟次数为： n-1-i 次
第几趟 = i 排序次数(数对)
0 确定6的位置；5次 ；{[4,5],[5,6],[6,3],[3,2],[2,1]}
1 确定5的位置；4次；{[4,5],[5,3],[3,2],[2,1]}
2 确定4的位置；3次；{[4,3],[3,2],[2,1]}
3 确定3的位置；2次；{[3,2],[2,1]}
4 确定2的位置；1次；{[2,1]}

6.程序

package com.wdl.kt.java;


import java.util.Scanner;

//冒泡排序
public class MaoPao {
    public static void main(String... args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            if (n<=0)return;
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = scanner.nextInt();
            int count = 0;
            for (int i = 0; i < n - 1; i++) {   //排序趟数
                for (int j = 0; j < n - 1 - i; j++) {  //每趟排序的次数
                    count++;
                    if (a[j] > a[j + 1]) {    //进行数据交换
                        int tmp = a[j];
                        a[j] = a[j + 1];
                        a[j + 1] = tmp;
                    }
                }
            }
            for (int i = 0; i < n; i++)
                System.out.print(a[i] + " ");
            System.out.println("排序次数："+count);
        }
    }
}

相关推荐