C++冒泡排序代码优化 |21xrx.com

C++冒泡排序代码优化

2023-07-13 10:14:53 深夜i -- --

C++ 冒泡排序代码优化算法

冒泡排序是 C++ 中常用的排序方法之一。虽然它的时间复杂度较高，但实现起来相对简单。然而，在实际应用中，我们需要考虑如何优化这个算法，以提高效率。下面将介绍一些 C++ 冒泡排序代码的优化方法。

1. 减少比较次数

冒泡排序的核心操作是比较和交换，而比较操作是最费时的。因此，我们可以通过减少比较次数来优化算法的效率。具体来说，当一次循环中没有进行任何交换操作时，就可以认为序列已经排好了序，此时可以直接跳出循环。

实现如下：


void bubbleSort(int arr[], int n) {
  bool flag = false;
  for (int i = 0; i < n - 1; ++i) {
    flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
        flag = true;
      }
    }
    if (!flag) break;
  }
}

2. 减少交换次数

交换操作也是比较费时的，当我们已经确定了最大值或最小值的位置时，就可以不再交换，而是直接记录其位置，最后再统一交换。

实现如下：


void bubbleSort(int arr[], int n) {
  bool flag = false;
  int lastExchangeIndex = 0;
  int sortBorder = n - 1;
  for (int i = 0; i < n - 1; ++i) {
    flag = false;
    for (int j = 0; j < sortBorder; ++j) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
        flag = true;
        lastExchangeIndex = j;
      }
    }
    sortBorder = lastExchangeIndex;
    if (!flag) break;
  }
}

3. 使用快速排序

当数据量较小的时候，使用冒泡排序的效率还是比较高的。但是，当数据量很大时，冒泡排序的效率会非常低。此时，我们可以使用快速排序来替代冒泡排序。

快速排序原理是将一个数组分为两个子数组，一般来说，每个子数组的大小都是原数组大小的一半，然后递归地对两个子数组进行排序，直至排序完毕。快速排序的时间复杂度为 O(nlogn)，效率比冒泡排序要高得多。

代码实现如下：


void quickSort(int arr[], int left, int right) {
  if (left < right) {
    int i = left, j = right, pivot = arr[i];
    while (i < j) {
      while (i < j && arr[j] >= pivot) j--;
      if (i < j) arr[i++] = arr[j];
      while (i < j && arr[i] < pivot) i++;
      if (i < j) arr[j--] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
  }
}

如果数据量较小，可以继续使用冒泡排序，否则可以使用快速排序来提高效率。

以上就是一些 C++ 冒泡排序代码的优化方法。对于其它的排序算法也可以进行相应的优化，以提高效率。

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

下一篇: "探讨C++程序的可移植性"

评论区

()

相似文章