用c++编写一个双向起泡的排序算法

下面是使用 C++ 实现双向起泡排序算法的代码：

#include <iostream>
#include <vector>

using namespace std;

vector<int> cocktail_sort(vector<int>& arr) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        // 从左到右排序
        for (int i = left; i < right; i++) {
            if (arr[i] > arr[i+1]) {
                swap(arr[i], arr[i+1]);
            }
        }
        right--;

        // 从右到左排序
        for (int j = right; j > left; j--) {
            if (arr[j-1] > arr[j]) {
                swap(arr[j-1], arr[j]);
            }
        }
        left++;
    }

    return arr;
}

int main() {
    vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    vector<int> sorted_arr = cocktail_sort(arr);

    for (auto num : sorted_arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

该算法的时间复杂度为 O(n^2)，空间复杂度为 O(1)。