#include <bits/stdc++.h>

using namespace std;

// 冒泡排序 O(n^2) 稳定

void bubbleSort(int a[], int n)
{
    for(int i = n - 1; i > 0; i--)
    {
        for(int j = 0; j < i; j++)
        {
            if(a[j] > a[j+1]) swap(a[j], a[j+1]);
        }
    }
}

// 快速排序 O(nlogn)

void quickSort(int a[], int l, int r)
{
   if(l>=r) return;

   int i = l, j = r, tmp = a[l];

   while(i < j)
   {
        while(i < j && a[j] >= tmp) j--;
        if(i < j) a[i++] = a[j];
        while(i < j && a[i] <= tmp) i++;
        if(i < j) a[j--] = a[i]; 
   }
   a[i] = tmp;
   quickSort(a,l,i-1);
   quickSort(a,i+1,r);
}

// 插入排序 O(n^2) 稳定

void insertSort(int a[], int n)
{
    for(int i = 1; i < n; i++)
    {
        int tmp = a[i], j;
        for(j = i; j > 0 && tmp < a[j-1];j--)
            a[j] = a[j-1];
        a[j] = tmp;
    }
}

// 选择排序 O(n^2)

void selectSort(int a[], int n)
{
    for(int i = 0; i < n - 1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(a[i] > a[j]) swap(a[i], a[j]);
        }
    }
}

// 归并排序 O(nlogn) 稳定
void mergeSort(int a[], int l, int r)
{
    if(l >= r) return;

    int tmp[r-l+1];

    int mid = l + r >> 1;
    mergeSort(a,l,mid), mergeSort(a,mid+1,r);

    int i = l , j = mid + 1, k = 0;

    while(i <= mid && j <= r)
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];

    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];

    for(int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
}

// 堆排序 O(nlogn)
void adjust_heap(int a[], int x, int n)
{
    int l = x * 2 + 1;
    int r = x * 2 + 2;
    int max = x;

    if(l < n && a[l] > a[max]) max = l;
    if(r < n && a[r] > a[max]) max = r;

    if(max != x)
    {
        swap(a[x], a[max]);
        adjust_heap(a,max,n);
    }
}

void heapSort(int a[], int n)
{
    for(int i = n/2-1; i >= 0; i--)
        adjust_heap(a, i, n);

    for(int i = n-1; i > 0; i--)
    {
        swap(a[0], a[i]);
        adjust_heap(a,0,i);
    }
}

int main()
{
    int a[] = {3, 2, 1, 5, 3, 10, 3, 7, 6, 7, 9, 8, 1};
    int n = sizeof(a)/sizeof(int);
    // bubbleSort(a,n); 
    // quickSort(a,0,n-1);
    // insertSort(a,n);
    // selectSort(a, n);
    // heapSort(a, n);
    // mergeSort(a, 0, n-1);
    for(int i = 0; i < n; i++) cout << a[i] << ' ';
    cout << endl;

}