#include <iostream>
using namespace std;

// 优化 buddleSort ，每次记录 参与交换的最后一个元素

template<typename T>
void buddleSort(T arr[], int n) { 

    do {

        int newN = 0;
        for (int i = 0; i < n - 1; i ++ ) {
            if(arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                newN = i + 1;
            }
        }
        // n--;    // 最后一个元素是当前趟中最大的值，不需要再比较
        n = newN;

    } while(n);
}

template<typename T>
void insertionSort(T arr[], int n) {

    for (int i = 1; i < n; i ++ ) {
        T e = arr[i];   // 保存现在的值
        int j;  // j 从 i 处向前走

        for (j = i; j > 0; j -- ) {

            if(arr[j - 1] > e) {
                arr[j] = arr[j - 1];
            } else break;
        }

        arr[j] = e; // j 是 e 合适的位置
    }


}

template <typename T>
void selectionSort(T arr[], int n) {

    for (int i = 0; i < n; i ++ ) {
        int minIndex = i;
        for (int j = i + 1; j < n; j ++ ) {
            if(arr[j] < arr[minIndex]) minIndex = j;
        }
        swap(arr[i], arr[minIndex]);
    }

}


int main() {

    int arr[8] = {1,2,6,4,7,3,9,0};

    // selectionSort(arr, 8);
    // insertionSort(arr, 8);
    buddleSort(arr, 8);

    for(int i=0; i < 8; i ++) cout << arr[i] << " "; 

    return 0;
}