排序算法相关

//递增排序
void InsertSort(int A[],int n){//长度为n的int型数组
    int i,j,temp;
    for (i = 1; i < n; i++)
        if (A[i] < A[i-1]) {//如果A[i]的小于其前驱则进行A[i]的移动
            temp=A[i];//临时保存A[i]
            for (j = i-1; j>=0 && A[j]>temp; j--)//依次检查A[i]之前已经排好序的元素
                A[j+1]=A[j];//大于temp的后移
            A[j+1]=temp;//最终复制到插入位置
        }
}

void InsertSort(int A[],int n){
    int i,j,low,high,mid;
    for (i = 2; i < n; i++) {
        A[0]=A[i];
        low=1,high=i-1;//折半查找的范围
        while (low<=high) {
            mid=(low+high)/2;
            if (A[mid>A[0]]) high=mid-1;//查找左部分
            else low=mid+1;//查找右部分
        }
        for (j = i-1; j>=high+1; j--)//i之前元素全部后移
            A[j+1]=A[j];
        A[high+1]=A[0];//插入
    }
}

void ShellSort(int A[],int n){
    int i,j,d;
    for (d = n/2; d >= 1; d=d/2) //步长不断衰减
        for ( i = d+1; i <= n; i++) //遍历各步长为d的子表,从子表第二个元素开始处理即可
            if(A[i]<A[i-d]){//如果发现逆序
                A[0]=A[i];//暂存需要交换位置的A[i]
                for ( j = i-d; j > 0 && A[0]<A[j]; j-=d) //当子表中存在元素，判断与A[i]大小，寻找A[i]插入位置
                    A[j+d]=A[j];//子表记录后移
                A[j+d]=A[0];//插入
            }//if
}

void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}
void BubbleSort(int A[],int n){
    for (int i = 0; i < n; i++){ //i之前的所有元素必然已经有序
        bool flag=false;
        for (int j = n-1; j > i; j--) //从后往前的一趟冒泡
            if (A[j-1] > A[j]) {//逆序,(相等不会交换，是稳定的)
                swap(A[j-1],A[j]);
                flag=true;
            }//if
        if (!flag) {
            return;//本趟遍历flag未改变，说明已经有序,可能会提前结束
        }
    }//for
}

void QuickSort(int A[],int low,int high) {//快速排序
    if (low<high) {//递归跳出的条件
        int pivotpos=Partition(A,low,high);//进行“划分”
        QuickSort(A,low,pivotpos-1);//处理左子表
        QuickSort(A,pivotpos+1,high);//处理右子表
    }
}
int Partition(int A[],int low,int high){//"划分"函数，返回 枢轴 位置
    int pivot=A[low];//取low作为枢轴
    while (low<high) {//用low,high搜寻枢轴位置
        while (low<high && A[high]>pivot) high--;
        A[low]=A[high];//比枢轴小的元素移动到左端
        while (low<high && A[low]<pivot) low++;
        A[high]=A[low];//比枢轴大的元素移动到右端
    }
    A[low]=pivot;//改变枢轴low位置
    return low;
}

void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}

void SelectSort(int A[],int n) {
    for (int i = 0; i < n-1; i++) {//从头开始遍历，最后一个元素无需处理(最终一定是最大)
        int min=i;//初始最小元素位置
        for (int j = i+1; j < n; j++) //在i之后所有元素中寻找最小元素位置
            if (A[j]<A[min]) min=j;//更新最小元素位置
        if (min!=i) swap(A[min],A[i]);//将最小元素置于表头
    }
}

void BuildMaxHeap(int A[],int len){
    for (int i = len/2; i > 0; i--)//从编号最大非终端节点开始 
        HeadAdjust(A,i,len);
}

//调整以k为根节点的树为大根堆
void HeadAdjust(int A[],int k,int len){
    A[0]=A[k];
    //寻找A[k]应该插入的位置--“下坠”
    for (int i = 2*k; i <= len; i*=2) {
        if (i<len&&A[i]<A[i+1]) //找到key更大的子结点的下标
            i++;
        if(A[0]>=A[i]) break;//满足“根”>左、右，end for
        else{
            A[k]=A[i];//将A[i]调整到双亲结点上
            k=i;
        }
    }//for
    A[k]=A[0];//已找到应该插入的位置
}

void BuildMaxHeap(int A[],int len);
void HeadAdjust(int A[],int k,int len);
void swap(int &a,int &b);

void HeapSort(int A[],int n){
    BuildMaxHeap(A,n);//初始建立大根堆
    for (int i = n; i > 1; --i) { //n-1趟交换与建堆
        swap(A[i],A[1]);//堆底与堆顶元素互换
        HeadAdjust(A,i,i-1);//剩余待排序元素整理成堆
    }
}

int *B=(int *)malloc(n*sizeof(int));//辅助数组，长度等于A数组

//A[low...mid]和A[mid+1...high]各自有序，将两个部分归并
void Merge(int A[],int low,int mid,int high) {
    int i,j,k;
    for (k = low; k <= high; k++) //将A[low...high]复制到B
        B[k]=A[k];
    for (i = low,j=mid+1,k=i; i <= mid&&j<=k; k++) {//归并
        if (B[i]<=B[j]) //较小者复制到A中
            A[k]=B[i++];
        else A[k]=B[j++];
    }//for
    while (i<=mid) A[k++]=B[i++];
    while (j<=high) A[k++]=B[j++];
}

void MergeSort(int A[],int low,int high) {
    if (low<high) {
        int mid=(low+high)/2;//从中间划分
        MergeSort(A,low,mid);//左部分归并
        MergeSort(A,mid+1,high);//右部分归并
        Merge(A,low,mid,high);//两部分归并
    }
}