21xrx.com
2024-11-22 02:46:03 Friday
登录
文章检索 我的文章 写文章
C++冒泡排序优化示例
2023-07-09 22:54:12 深夜i     --     --
C++ 冒泡排序 优化 示例

冒泡排序是一种简单的排序算法,但是其时间复杂度为O(n^2),效率较低。为了提高冒泡排序的效率,我们可以对其进行优化。

一种优化的方式是利用flag标志,当一轮排序中没有元素进行交换,则说明已经完成排序,可以提前退出循环。

另一种优化的方式是在每一轮排序中记录最后一次交换的位置,下一轮排序时只需要循环到该位置即可。

下面是一个使用优化的C++冒泡排序示例:


#include <iostream>

using namespace std;

void bubbleSort(int a[], int n) {

  bool flag = true;//使用flag标志

  for (int i = 0; i < n && flag; i++) {

    flag = false;

    int lastSwap = 0;//记录最后一次交换的位置

    for (int j = 0; j < n - i - 1; j++) {

      if (a[j] > a[j + 1]) {

        swap(a[j], a[j + 1]);

        flag = true;

        lastSwap = j;

      }

    }

    n = lastSwap + 1;//下一轮只需要循环到最后一次交换的位置

  }

}

int main() {

  int a[] = 2;

  int n = sizeof(a) / sizeof(a[0]);

  bubbleSort(a, n);

  for (int i = 0; i < n; i++) {

    cout << a[i] << " ";

  }

  cout << endl;

  return 0;

}

在这个优化后的程序中,我们使用了flag标志和lastSwap变量,在每一轮排序中记录最后一次交换的位置,下一轮排序时只需要循环到该位置即可。这样,我们大大减少了排序的次数和比较的次数,提高了冒泡排序的效率。

总之,C++冒泡排序是一个简单但效率较低的排序算法,通过优化可以提高其效率,使其更适用于大规模数据的排序。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复