/**
 * 排序的基本操作——比较、移动、交换
 * 插入排序：直接插入、折半插入、希尔插入
 * 交换排序：冒泡、快排
 * 选择排序：简单选择、堆选择
 * 归并排序
 * 基数排序
*/

#include <stdio.h>
#include <stdlib.h>

void printFromZero(int A[], int len)
{
    for (int i = 0; i < len; ++i)
    {
        printf("%d-", A[i]);
    }
}
void printFromOne(int A[], int len)
{
    for (int i = 1; i < len; ++i)
    {
        printf("%d-", A[i]);
    }
}
//直插
void insertSort(int A[], int len)
{
    if (len == 1){
        return;
    }
    int sortingNum;
    for (int i = 1; i < len; ++i)
    {
        sortingNum = A[i];
        //有序移动
        int j = i-1;
        while (j >= 0 && sortingNum < A[j]){
            A[j+1] = A[j];
            j--;
        }
        A[j + 1] = sortingNum;//j是比较位,应将待排数放到比较位后面
    }
}
//折半插入
void binInsertSort(int A[], int len)
{
    int j,low,high,mid,tmp;
    for (int i = 1; i < len; ++i)//从头部开始，保证前方有序才能使二分查找有效
    {
        tmp = A[i];
        //折半（二分）查找插入位置
        low = 0; high = i-1;
        while(low <= high){
            mid = (low + high) / 2;
            if(tmp < A[mid]){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        //移动并插入
        j = i - 1;
        while ( j > high ){
            A[j + 1] = A[j];
            j--;
        }
        A[j+1] = tmp;
    }
}
//希尔/增量(直接插入排序的一般化)：
//以某步长来将元素分组，位置为步长倍数的元素属于同组，各组起始位为i,i+dt,i+2dt...,在组内进行直接插入排序
//注意分组是逻辑的，不是物理的，所以同组内元素不一定物理相邻
void shellSort(int A[], int len)
{
    int sortingNum,j;
    for (int dt = len/2; dt >= 1; dt = dt /2)
    {
        for (int i = dt; i < len; ++i)
        {
            if(A[i] < A[i - dt]){
                sortingNum = A[i];
                //移动分组内有序表(移动后待排数不一定与较小值相邻，其间距是dt)
                j = i - dt;
                while( j >= 0 && sortingNum < A[j]){
                    A[j + dt] = A[j];
                    j -= dt;
                }
                A[j + dt] = sortingNum;
            }
        }
    }
}
int quickSortPartition(int A[], int low, int high)
{
    int pivot = low, pivotVal = A[low];
    while(low < high && A[high] >= pivotVal ){
        high--;
    }
    A[pivot] = A[high];//将高值部分小于基准值的数放到基准值位置，留下一个高值部分的空位
    while(low < high && A[low] <= pivotVal){
        low++;
    }
    A[high] = A[low];//将低值部分大于基准值的数放到高值部分的空位，留下一个低值部分的空位
    A[low] = pivotVal;//将低值部分空位填充基准值，并返回基准值位置
    return low;
}
//快排
void quickSort(int A[], int low, int high)
{
    if(low < high){
        int pivot = quickSortPartition(A, low, high);
        quickSort(A, low, pivot-1);
        quickSort(A, pivot+1, high);
    }
}
//简单选择(子序列是全局有序的):选出最小值
void selectionSort(int A[], int len)
{
    int min,minVal;
    for (int i = 0; i < len-1; ++i)
    {
        min = i;
        for (int j = i+1; j < len; ++j)
        {
            if(A[j] < A[min]){
                min = j;
            }
        }
        if(min != i){
            minVal = A[i];
            A[i] = A[min];
            A[min] = minVal;
        }
    }
}
//从最后一个节点开始调整可以保证下方是有序的，
//这样在调节上方节点时，可以直接调整根节点与孩子构造大顶堆，
//然后再循环构造孩子为大顶堆时并不影响上方（因为孩子中最大值的节点已经在上方了）
void maxHeapAjustdown(int A[], int subRoot, int len)
{
    int originRootVal = A[subRoot];
    //调整子树根节点与其左右孩子构成子树大顶堆
    for (int child = 2*subRoot; child <= len; child *= 2)
    {
        if(child < len && A[child] < A[child + 1]){//若左孩子小于右孩子则指向右孩子
            child ++;
        }
        //根节点大于左右孩子时可以直接跳出，因为是从深层构建堆的，所以左右孩子已经是其子树的最大值了
        if(originRootVal >= A[child]){
            break;
        }else{
            //根节点小于孩子时将大孩子作为根节点，原根节点指向原大孩子，然后继续调整原大孩子子树。
            //这里可以看到当child为右孩子时，此函数就无法处理此child的侄节点了。
            //因此构建的堆中有可能节点值大于叔伯节点的值，但这不违背堆的特性
            A[subRoot] = A[child];
            subRoot = child;
        }
    }
    A[subRoot] = originRootVal;
}
void maxHeapBuild(int A[], int len)
{
    //从底层往上层构建
    for (int i = len/2; i > 0; i--)
    {
        maxHeapAjustdown(A, i, len);
    }
}
//最大堆：注意二叉树父子结点间的位置关系是基于序号的，不能从0开始(虽然从零开始也可以实现，但是结点关系计算麻烦，强烈不推荐使用从0开始)
void maxHeapSort(int A[], int len)
{
    //构建最大堆
    maxHeapBuild(A, len);
    int tmp;
    for (int i = len; i > 1; --i)
    {
        //将最大的根节点与最后一个节点交换
        tmp = A[1];
        A[1] = A[i];
        A[i] = tmp;
        //因为数据在构建最大堆时已经整体有序了，所以只需调整根节点即可
        maxHeapAjustdown(A, 1, i-1);
    }
}
// 归并的合并部分
void merge(int A[], int B[], int low, int mid, int high)
{
    int resIndex;
    //1赋值辅助数组
    for (resIndex = low; resIndex <= high; ++resIndex){
        B[resIndex] = A[resIndex];//需要辅助数组
    }
    int lowIndex,highIndex;//lowIndex是低值部分下标，highIndex是高值部分下标
    //2依次比较低值部分与高值部分的值，将大值存到目标数组中
    for (lowIndex = low, highIndex=mid+1, resIndex = lowIndex; lowIndex <= mid && highIndex<=high; resIndex++){//resIndex作为目标数组的下标
        //通过辅助数组来给目标数组排序
        if(B[lowIndex] <= B[highIndex]){
            A[resIndex] = B[lowIndex++];
        }else{
            A[resIndex] = B[highIndex++];
        }
    }
    //3将剩余部分拼接到目标数组中
    while( lowIndex <= mid) A[resIndex++] = B[lowIndex++];
    while( highIndex <= high) A[resIndex++] = B[highIndex++];
}
// 归并
void mergeSort(int A[], int B[], int low, int high)
{
    if(low < high){
        int mid = (low + high)/2;

        mergeSort(A, B, mid+1, high);//排序高值部分
        mergeSort(A, B, low, mid);//排序低值部分
        merge(A, B, low, mid, high);//最终合并（递归部分会调用到）
    }
}
int main(int argc, char const *argv[])
{
#define LENGTH 10
    // 50,26,38,80,70,90,8,30,40,20
    int A[LENGTH] = {2,1,7,3,6,4,5,8,10,9};
    // insertSort(A, LENGTH);
    // binInsertSort(A, LENGTH);
    // shellSort(A, LENGTH);
    // quickSort(A, 0, LENGTH-1);
    // selectionSort(A, LENGTH);
    // int B[LENGTH+1] = {0,2,1,7,3,6,4,5,8,10,9};
    // maxHeapSort(B, LENGTH);
    // printFromOne(B, LENGTH+1);

    int C[LENGTH] = {0};//归并排序的辅助数组
    mergeSort(A,C, 0, LENGTH-1);

    printFromZero(A, LENGTH);
    return 0;
}