/**  * 排序的基本操作——比较、移动、交换  * 插入排序：直接插入、折半插入、希尔插入  * 交换排序：冒泡、快排  * 选择排序：简单选择、堆选择  * 归并排序  * 基数排序 */ #include 
     
      #include 
      
       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;}