template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
 
template<class T>
void BubbleSort3(T* x) {
    int last = -1;
    for (int i = 0; i < n; i++) {
        int k = i;
        if (last > 0 && last > i) {
            k = last;
        }
        for (int j = n-1; j > k; j-- ) {
            if (x[j-1] > x[j]) {
                swap(x, j-1, j);
                last = j;
            }
        }
        if (last == k) break;
    }
}

Добавляется отслеживание окончательно отсортированного отрезка исходного массива, чтобы в пустую уже не делать по нему сравнений. Такой отрезок может появляться с того края последовательности, в направлении которого мы проходимся по массиву в пределах каждой главной итерации.
Следует отметить, что даже при такой оптимизации, количество перестановок элементов не уменьшается даже по сравнению с базовой версией. Всей этой оптимизацией мы уменьшили только количество сравнений между элементами.

Производительность: ~ O(n²)
Расход памяти: - (только пара счетчиков цикла и вызов swap-а)