冒泡排序四种方法c++

冒泡排序是一种简单的排序算法，它通过不断比较相邻的元素并交换位置来实现排序。以下是四种常见的冒泡排序方法的介绍：

1. 基本冒泡排序：
基本冒泡排序是最简单的冒泡排序方法。它通过多次遍历数组，每次比较相邻的两个元素并交换位置，将最大的元素逐渐“冒泡”到数组的末尾。时间复杂度为O(n^2)。

2. 优化冒泡排序：
优化冒泡排序在基本冒泡排序的基础上进行了一些改进。它增加了一个标志位，用于记录每次遍历中是否发生了元素交换。如果某次遍历中没有发生交换，说明数组已经有序，可以提前结束排序。这样可以减少不必要的比较和交换操作，提高效率。

3. 鸡尾酒排序（双向冒泡排序）：
鸡尾酒排序是对基本冒泡排序的改进，它从数组的两端同时进行遍历和比较。每次遍历时，先从左到右比较并交换元素，然后再从右到左比较并交换元素。这样可以同时将最大值和最小值“冒泡”到数组的两端，减少排序的遍历次数。

4. 短冒泡排序：
短冒泡排序是对基本冒泡排序的一种改进。它在每次遍历时记录下最后一次交换的位置，下一次遍历只需要比较到该位置即可。这样可以排除已经有序的部分，减少比较次数。

相关问题

c++四种冒泡排序完整代码

冒泡排序是一种简单的排序算法，通过多次比较和交换来实现排序。以下是四种冒泡排序的完整代码示例：

1. 基本冒泡排序：

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2. 优化冒泡排序（添加标记）：

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 标记是否发生交换
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        // 如果没有发生交换，表示已经有序，提前退出循环
        if (!swapped) {
            break;
        }
    }
}

3. 优化冒泡排序（记录最后一次交换位置）：

void bubbleSort(int arr[], int n) {
    int lastSwapIndex = n - 1;  // 记录最后一次交换的位置
    while (lastSwapIndex > 0) {
        int k = lastSwapIndex;
        lastSwapIndex = 0;
        for (int j = 0; j < k; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                lastSwapIndex = j;
            }
        }
    }
}

4. 优化冒泡排序（同时记录首次和最后一次交换位置）：

void bubbleSort(int arr[], int n) {
    int firstSwapIndex = 0;     // 记录首次交换的位置
    int lastSwapIndex = n - 1;  // 记录最后一次交换的位置
    while (firstSwapIndex < lastSwapIndex) {
        int k = lastSwapIndex;
        lastSwapIndex = 0;
        for (int j = firstSwapIndex; j < k; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                if (lastSwapIndex == 0) {
                    lastSwapIndex = j;
                }
            }
        }
        k = firstSwapIndex;
        firstSwapIndex = n - 1;
        for (int j = lastSwapIndex; j > k; j--) {
            if (arr[j] < arr[j - 1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                if (firstSwapIndex == n - 1) {
                    firstSwapIndex = j;
                }
            }
        }
    }
}

希望以上代码可以帮助到你！如果你还有其他问题，请继续提问。

冒泡排序实现降序排序c++

以下是使用动态数组实现降序冒泡排序的C++代码，同时统计排序次数并去除相同值：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr; // 动态数组存储元素
    int n, temp, count = 0;
    cin >> n; // 输入元素个数
    for (int i = 0; i < n; i++) {
        cin >> temp;
        arr.push_back(temp); // 将输入的元素加入动态数组
    }
    for (int i = 0; i < n - 1; i++) { // 排序轮数
        for (int j = 0; j < n - i - 1; j++) { // 每轮比较次数
            if (arr[j] < arr[j + 1]) { // 降序排序
                swap(arr[j], arr[j + 1]); // 交换元素
                count++; // 统计排序次数
            }
        }
    }
    for (int i = 0; i < n; i++) { // 去除相同值
        if (i == 0 || arr[i] != arr[i - 1]) {
            cout << arr[i] << " ";        }
    }
    cout << endl << "排序次数：" << count << endl; // 输出排序次数
    return 0;
}