/*
 * 简单排序包括了：冒泡排序和插入排序
 * 简单排序都需要扫描一遍整个数组 而且还有需要调整I个逆序对 故时间复杂度为O(n + I)
 * 定理1：任意N个元素组成的序列平均有 N * (N-1) / 4个逆序对
 * 定理2： 任何以交换相邻2个元素来排序的算法  其时间复杂度为Ω（n^2).
   所以要提高算法的效率，必须:
   1.每次消去不止一个逆序对
   2.每次交换相隔较远的2个元素
*/
#include "iostream"
using namespace std;
int v[10] = { 8,7,6,5,4,3,2,1,0,5 };
void swap(int *a, int* b) {
    int c;
    c = *a;
    *a = *b;
    *b = c;
}
void bubble_sort() { /* 冒泡排序是稳定的 时间复杂度最好情况O(n) 最坏情况O(n^2) 对与用单链表存储的数据排序~ 冒泡排序容易实现*/
    int n = 10;
    for (int i = n - 1; i > 0; i--) {
        bool flag = 0;
        for (int j = 0; j < i; j++) {
            if (v[j] > v[j + 1]) {
                swap(&v[j], &v[j + 1]);
                flag = 1;
            }
        }
        if (flag == 0)
            break;
    }
}
void insertion_sort() { /* 插入排序是稳定的排序 最好情况O(n) 最坏情况O(n^2)*/
    int n = 10;
    int i, j;
    for (i = 1; i < n; i++) {
        int temp = v[i]; /* 当前要插入的数 */
        for (j = i - 1; j >= 0; j--) {
            if (temp >= v[j])
                break;
                v[j + 1] = v[j];
        }
        v[j+1] = temp;
    }
}
void print() {
    int n = 10;
    for (int i = 0; i < n; i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}
int main() {
    //bubble_sort();
    insertion_sort();
    print();
}