C++冒泡排序优化示例 |21xrx.com

C++冒泡排序优化示例

2023-06-25 20:05:26 深夜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++冒泡排序是一个简单但效率较低的排序算法，通过优化可以提高其效率，使其更适用于大规模数据的排序。

上一篇: idea打包java可执行jar包

下一篇: C++程序实现俩个人分糖果，详细教程

评论区

()

相似文章