/*
    直接插入排序
    时间复杂度O(n2)，稳定
 */
void InsertSort(int a[], int n)
{
    int i, j;
    for (i = 1; i < n; i++)
    {
        int temp = a[i];
        for (j = i - 1; temp < a[j] && j >= 0; j--)
        {
            a[j+1] = a[j];
        }
        a[j+1] = temp;
    }
}

/*
    折半插入排序
    时间复杂度O(n2)，稳定
 */
void BinaryInsertSort(int arr[], int n)
{
    int i, j, low, high, mid;
    for(i = 1; i < n; i++)
    {
        int temp = arr[i];
        low = 0, high = i - 1;
        while(low <= high)
        {
            mid = (low + high) / 2;
            if (arr[mid] > temp)
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        for (j = i; j > low; j--)
        {
            arr[j] = arr[j-1];
        }
        arr[low] = temp;
    }
}

/*
    冒泡排序
    时间复杂度O(n2)，稳定
*/
void BubleSort(int a[], int n)
{
    int flag = true;
    for (int i = 1; i < n && flag ; i++)
    {
        flag = false;
        for (int j = n - 1; j >= i; j--)
        {
            if (a[j - 1] > a[j])
            {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
                flag = true;
            }
        }
    }
}

/*
    快速排序
    时间复杂度O(nlogn)，不稳定
 */

int Partition(int arr[], int low, int high)
{
    int pivot = arr[high];
    int i;
    int j = low;
    for(i = low; i < high; i++)
    {
        if (arr[i] < pivot)
        {
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            j++;
        }
    }
    int temp = arr[j];
    arr[j] = arr[high];
    arr[high] = temp;
    return j;
}

void QuickSort(int a[], int low, int high)
{
    if (low < high)
    {
        int pivot = Partition(a, low, high);
        QuickSort(a, low, pivot - 1);
        QuickSort(a, pivot, high);
    }
}

/*
    简单选择排序
    时间复杂度O(n2),不稳定
 */
void SelectSort(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        int min = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[min])
                min = j;
        }
        if (min != i)
        {
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

/*
 *归并排序
 *时间复杂度
 *时间复杂度O(nlogn)，稳定
 */
void Merge(int arr[],int tmp[], int L, int M, int R)
{
    for (int k = L; k <= R; k++)
        tmp[k] = arr[k];
    int pos, i, j;
    for (i = pos = L, j = M + 1; i <= M && j <= R; pos++)
    {
        if (tmp[i] <= tmp[j])
        {
            arr[pos] = tmp[i++];
        }
        else arr[pos] = tmp[j++];
    }
    while(i <= M)
    {
        arr[pos++] = tmp[i++];
    }
    while(j < R)
    {
        arr[pos++] = tmp[j++];
    }
}

void MergeSort(int arr[], int L, int R)
{
    int tmp[R - L + 1];
    if (L < R)
    {
        int M = L + (R - L) / 2;
        MergeSort(arr, L, M);
        MergeSort(arr, M + 1, R);
        Merge(arr, tmp, L, M, R);
    }
}

/*
 *堆排序
 *时间复杂度O(nlogn),不稳定
*/

void swap(int arr[], int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void heapify(int tree[], int n, int i)
{
    if (i >= n)
        return;
    int c1 = 2 * i + 1;
    int c2 = 2 * i + 2;
    int max = i;
    if (c1 < n && tree[max] > tree[c1])
    {
        max = c1;
    }
    if (c2 < n && tree[max] > tree[c2])
    {
        max = c2;
    }
    if (max != i)
    {
        swap(tree, max, i);
        heapify(tree, n, max);
    }
}

void build_heap(int tree[], int n)
{
        int last_node = n - 1;
        int parent = (last_node - 1) / 2;
        int i;
        for (i = parent; i >= 0; i--)
        {
            heapify(tree, n, i);
        }
}