首页 > 代码库 > 借助bool判断使冒泡排序效率提高

借助bool判断使冒泡排序效率提高

排序问题是编程中最常见的问题。实际应用中,计算机有接近一半时间是在处理有关数据排列的问题,提高排序的效率有助于更快地解决问题。

先来说说平常一般的冒泡算法,使用两个循环,外循环作为整体排序,每趟循环使未排序元素中的最大(小)值归位(到达其最终位置)。内循环用于两两相邻元素比较。每次对一组n个数据进行排序时都要进行n-1次全体扫描交换。比如对5,1,2,3,4进行升序排列,进行一趟整体扫描后变为1,2,3,4,5,实际已经达到要求可以输出,可是还要进行3次整体扫描排序,比较繁琐。

这里提供的算法可以解决上述普通算法效率比较低的问题。核心思想是这样的:

1.定义一个布尔变量sorted作为判断是否整体排序的标志,初始化其为false。

2.每趟排序判断 !sorted 的值为1才进行整体扫描,进入循环。

3.进入循环,先把sorted赋值为ture,对两两相邻元素进行比较,若发现有元素不符合顺序,操作使元素换位并将sorted赋值为false,若比较完这一趟未发现有元素乱序,则sorted保持为true,然后n--。

由此,借助布尔变量sorted,可及时提前退出,而不致于总是蛮力地做n - 1趟扫描交换。 如对5,1,2,3,4升序排列操作,进行2趟扫描后即可输出,若用普通冒泡则需4趟扫描。

 

下面是冒泡排序的实现代码。

#include<iostream>using namespace std;void swap(int &a, int &b) {    int c;    c = a;    a = b;    b = c;}void booblesort(int a[], int n) {    bool sorted = false;    while (!sorted) {        sorted = true;        for (int i = 0; i < n - 1; i++) {            if (a[i] > a[i + 1]) {                swap(a[i], a[i + 1]);                sorted = false;            }        }        n--;    }}int main() {    cout << "please enter ten integers:" << endl;    int a[10];    for (int i = 0; i < 10; i++) {        cin >> a[i];    }    booblesort(a, 10);    for (int i = 0; i < 10; i++) {        cout << a[i] << " ";    }    cout << endl;    return 0;}

参考资料:《数据结构(C++语言版)》(第3版)—— 邓俊辉

借助bool判断使冒泡排序效率提高