冒泡排序

#include <iostream>
#include <vector>
#include <chrono>
#include "math.h"
using namespace std;

// Time Complexity O(n^2)
// Space Complexity O(1)
// neighbours change places until a pass makes no swaps:
// the largest element "bubbles up" to the end on every pass
vector<int> bubbleSort(vector<int> arr)
{
    long len = arr.size();
    vector<int> items(arr);
    for (long end = len; end > 1; end--) {
        bool swapped = false;
        for (long j = 1; j < end; j++) {
            if (items[j] < items[j - 1]) {
                int tmp = items[j];
                items[j] = items[j - 1];
                items[j - 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
    return items;
}

vector<int> items = { 4, 1, 5, 3, 2 };

vector<int>sortItems = bubbleSort(items);
// sortItems is {1, 2, 3, 4, 5}

for (int i : sortItems) cout << i << ", ";
cout << endl;

// *** simplified speed test ***

items = vector<int>(200, 0);
for (int i = 0; i < items.size(); i++) {
    items[i] = items.size() - 1 - i;
}
int count = 10000;

auto start = chrono::steady_clock::now();

for (int i = 0; i < count; i++) {
    bubbleSort(items);
}

long milliseconds = chrono::duration_cast<chrono::milliseconds>(
    chrono::steady_clock::now() - start).count();

cout << milliseconds << " milliseconds";
// about 2210 milliseconds