提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

经典算法——冒泡排序

算法 执行 排序
2023-03-07 09:40:53 时间

1. 什么是算法？

任何被明确定义的计算过程都可以称作 算法 ，它将某个值或一组值作为输入，并产生某个值或一组值作为输出。所以 算法可以被称作将输入转为输出的一系列的计算步骤 。

说白了就是步骤明确的解决问题的方法。由于是在计算机中执行，所以通常先用伪代码来表示，清晰的表达出思路和步骤，这样在真正执行的时候，就可以使用不同的语言来实现出相同的效果。

2. 算法的效率

算法效率是指算法 执行的时间，算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。在现在的计算机硬件环境中，比较少需要考虑这个问题了，特别是pc机的编程， 内存空间 越来越大，所以被考虑得也越来越少，不过一个好的程序员，都应该对自己的程序有要求，每一个for比别人少一次判断1000个for就能够少掉很多的运行时间。所以能够理解，能够大概的去运用"效率度量"还是有很大意义的。我们一般通过两个方面来衡量一个算法的效率

  • 时间复杂度?

算法的时间复杂度是一个函数，它定性描述一个算法的运行时间。 一个算法的执行所需要的时间，从理论上来说是算不出来的，必须通过上机测试才能得到，但这并不是说我们对于每个算法都要上机测试，我们只需要知道哪个算法所花的时间多，哪个算法所花的时间少就行。 一个算法花费的时间与算法中的语句执行次数成正比，算法中的语句执行次数越多，它花费的时间就越多。一个算法中的语句执行次数成为语句频度或时间频度，记为T(n)，n为问题的规模。

  • 空间复杂度?

空间复杂度是指执行这个算法所需要的内存空间。 空间复杂度需要考虑在运行过程中为 局部变量分配的存储空间的大小 ，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。 空间复杂度也就是对一个算法在运行过程中 临时占用存储空间大小 的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2)，空间复杂度是O(1) 。

  • 稳定性?

算法稳定性指的是在一组待排序记录中，如果存在任意两个相等的记录R和S，且在待排序记录中R在S前，如果在排序后R依然在S前，即它们的前后位置在排序前后不发生改变，则称为排序算法为稳定的。

常见排序算法的稳定性：堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

3. 冒泡排序

冒泡排序，也被称为气泡排序或泡沫排序。

冒泡排序是一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止！

3.1 代码实践

java代码

  /**
     * 冒泡排序
     *
     * @param a 待排序的数组
     * @param n 数组的长度
     */
    public static void bubbleSort1(int[] a, int n) {
        int i, j;

        for (i = n - 1; i > 0; i--) {
            // 将a[0...i]中最大的数据放在末尾
            for (j = 0; j < i; j++) {

                if (a[j] > a[j + 1]) {
                    // 交换a[j]和a[j+1]
                    int tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;
                }
            }
        }
    }

    /**
     * 冒泡排序(改进版)
     *
     * @param a 待排序的数组
     * @param n 数组的长度
     */
    public static void bubbleSort2(int[] a, int n) {
        int i, j;
        int flag;                 // 标记

        for (i = n - 1; i > 0; i--) {
            // 初始化标记为0
            flag = 0;
            // 将a[0...i]中最大的数据放在末尾
            for (j = 0; j < i; j++) {
                if (a[j] > a[j + 1]) {
                    // 交换a[j]和a[j+1]
                    int tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;

                    flag = 1;    // 若发生交换，则设标记为1
                }
            }

            if (flag == 0)
                break;            // 若没发生交换，则说明数列已有序。
        }
    }

    public static void main(String[] args) {
        int i;
        int[] a = {20, 40, 30, 10, 60, 50};

        System.out.printf("before sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");

        bubbleSort1(a, a.length);
//        bubbleSort2(a, a.length);

        System.out.printf("after  sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");
    }

3.2 算法效率

  • 时间复杂度

假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(n)，需要遍历多少次呢？n-1次！因此，冒泡排序的时间复杂度是O(n2)。

  • 空间复杂度

冒泡排序的辅助变量空间仅仅是一个临时变量，并且不会随着排序规模的扩大而进行改变，所以空间复杂度为O(1)。

  • 稳定性

冒泡排序是针对相邻的元素且存在相对大小时才交换元素位置，对于大小相等的相邻元素，不会交换两者位置，所以冒泡排序是稳定的。

相关文章