冒泡排序(Bubble Sort)

介绍

  冒泡排序是一种最基础的交换排序(两两比较待排序的关键字,交换不满足次序要求的那对数,直到整个表都满足次序要求为止),工作方式如同碳酸饮料中的二氧化碳气泡最终会上浮到顶端一样,故名"冒泡排序"。

算法描述

  一次比较相邻的数据,将小数据放在前(假设非递减排列),大数据放在后。即第一趟比较第1个和第2个数,小数在前,大数在后,再比较第2个数与第3个数,小数在前,大数在后,以此类推比较第n - 1个和第n个数,小数在前,大数在后;第一趟后最大元素已放在正确位置,以此类推,直到全部元素放在正确的位置。

动图演示

冒泡排序(Bubble Sort)

性能分析

  时间复杂度:O(N2)

  空间复杂度:O(1)

  稳定性:稳定

代码实现

void bubbleSort(int a[], int length) {
    // i表示这一趟要填入正确元素的位置,最后一个位置不需要比较
    // 因为n-1个元素在正确位置,最后一个位置自然填入正确元素
    for (int i = 0; i < length - 1; ++i) {
        // 从后往前依次比较,将最小元素"冒泡"到最前方,要填入正确元素的位置i
        for (int j = length - 1; j > i; --j) {
			// 交换不满足次序要求的元素
            if (a[j] < a[j - 1]) { 
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
        }
    }
}

算法优化

考虑一些特殊情况
  1、待排序序列已经有序,整个代码任然会执行无效的遍历和比较。

  2、数据已经排好序,但任然会进行下一轮比较,直到length-1次,后面的比较都是无意义的。

  可以通过设置标志位flag,如果发生了交换就改变flag设置为true,如果没有交换就保持false。当一轮比较结束后如果flag仍为false,即:这一轮没有发生交换,说明数据的顺序已经排好,没有必要继续进行下去。退出循环,排序完成。

void bubbleSort2(int a[], int length) {
    bool flag = false;  // 标记第i趟是否发生元素交换
    // i表示这一趟要填入正确元素的位置,最后一个位置不需要比较
    // 因为n-1个元素在正确位置,最后一个位置自然填入正确元素
    for (int i = 0; i < length - 1; ++i) {
        flag = false;  // 每趟默认未进行元素交换
        // 从后往前依次比较,将最小元素"冒泡"到最前方,要填入正确元素的位置i
        for (int j = length - 1; j > i; --j) {
            if (a[j] < a[j - 1]) {  // 交换不满足次序要求的元素
                flag = true;  // 发生元素交换,改变flag
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
        }
        if (flag == false) {  // 未发生交换,序列满足要求,完成排序
            break;  // 跳出循环
        }
    }
}
上一篇:数据结构-学习笔记-冒泡排序


下一篇:普里姆算法求图(邻接矩阵存储)的最小生成树