C++实现双向冒泡排序算法

算法介绍

双向冒泡排序，也称为鸡尾酒排序或定向冒泡排序，是冒泡排序的改进版本。其基本思路与冒泡排序相同，不同之处在于每次排序时同时从数组两侧开始，分别向中间移动。这种方法能够更快地将大数和小数分别冒泡到数组的两端，从而减少了排序次数，提高了排序效率。

下面是双向冒泡排序的具体步骤：
1. 从左往右进行一轮冒泡排序，将最小的数排到数组的最左边；
2. 从右往左进行一轮冒泡排序，将最大的数排到数组的最右边；
3. 重复上述步骤，直到数组有序。

C++代码实现

以下是用C++语言实现双向冒泡排序算法的代码，其中参数arr为待排序的数组，参数n为数组长度。

void CocktailSort(int arr[], int n) {
    bool flag = true;
    int left = 0, right = n - 1;
    while (flag) {
        flag = false;
        // 从左往右
        for (int i = left; i < right; i++) {
            if (arr[i] > arr[i+1]) {
                swap(arr[i], arr[i+1]);
                flag = true;
            }
        }
        right--;
        // 从右往左
        for (int i = right; i > left; i--) {
            if (arr[i] < arr[i-1]) {
                swap(arr[i], arr[i-1]);
                flag = true;
            }
        }
        left++;
    }
}

示例说明

下面通过两个示例说明双向冒泡排序的具体应用。

示例1：从小到大排序

#include <iostream>
using namespace std;

int main() {
    int arr[] = {23, 56, 12, 67, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前：" << endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    CocktailSort(arr, n);

    cout << "排序后：" << endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

输出结果：

排序前：
23 56 12 67 9 
排序后：
9 12 23 56 67

示例2：从大到小排序

#include <iostream>
using namespace std;

int main() {
    int arr[] = {23, 56, 12, 67, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前：" << endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    CocktailSort(arr, n);

    cout << "排序后：" << endl;
    for (int i = n-1; i >= 0; i--) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

输出结果：

排序前：
23 56 12 67 9 
排序后：
67 56 23 12 9

通过以上两个示例，可以看出双向冒泡排序算法对于不同的排序要求可以进行灵活的应用，并且比冒泡排序更加高效。