基本排序算法总结

插入排序

直接插入排序

void InsertSort(ElemType A[] ,int n){
    int i,j;
    for(i=2;i<=n;i++)            //依次将A[2]~A[n]插入前面已排序序列
        if(A[i]<A[i-1]){        //若A[i]关键码小于其前驱，将A[i]插入有序表
            A[0]=A[i];            //复制为哨兵,A[0]不存放元素
            for(j=i-1;A[0]<A[j];--j)    //从后往前查找待插入位置
                A[j+1]=A[j];    //向后挪位
            A[j+1]=A[0];        //复制到插入位置
        }
}

折半插入排序(不考)

void InserSort(ElemType A[],int n){
    int i,j,low,hign,mid;
    for(i=2;i<=n;i++){            //依次将A[2]~A[n]插入前面的已排序序列
        A[0]=A[i];                //将A[i]暂存到A[0]
        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)
            A[j+1]=A[j];        //统一后移元素
        A[high+1]=A[0];            //插入操作
    }
}

希尔排序

void ShellSort(ElemType A[],int n){
    //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for(dk=n/2;dk>=1;dk=dk/2)        //步长变化
        for(i=dk+1;i<=n;++i)        
            if(A[i]<A[i-dk]){        //需将A[i]插入有序增量子表
                A[0]=A[i];            //暂存在A[0]
                for(j=i-dk;j>0&&A[0]<A[j];j-=dk)
                    A[j+dk]=A[j];    //记录后移
                A[j+dk]=A[0];        //插入
            }//if
}

交换排序

冒泡排序

void BubbleSort(ElemType A[],int n){
    for(i=0;i<n-1;i++){
        flag=false;                //表示本趟冒泡是否发生交换的标志
        for(j=n-1;j>i;j--)        //一趟冒泡过程
            if(A[j-1]>A[j]){    //若为逆序
                swap(A[j-1],A[j]);    //交换
                flag=true;
            }
        if(flag==false)
            return;                //本趟遍历后没有发生交换，说明表已经有序
    }
}

快速排序

void QuickSort(ElemType 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(ElemType A[],int low,int high){    //一趟划分
    ElemType pivot=A[low];                //将当前表中第一个元素设为枢轴，对表进行划分
    while(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;                        //枢轴元素存放的最终位置
    return low;                            //返回存放枢轴的最终位置
}

选择排序

简单选择排序

void SelectSort(ElemType A[],int n){
    for(i=0;i<n-1;i++){                    //一共进行n-1趟
        min=i;                            //记录最小元素位置
        for(j=i+1;j<n;j++)                //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])    min=j;        //更新最小元素位置
        if(min!=i)    swap(A[i],A[min]);    //封装的swap()函数共移动元素3次
    }
}

堆排序

void BuildMaxHeap(ElemType A[],int len){
    for(int i=len/2;i>0;i--)    //从i=[n/2]~1，反复调整堆
        HeadAdjust(A,i,len);
}

void HeadAdjust(ElemType A[],int k,int len){
//函数HeadAdjust将元素k为根的子树进行调整
    A[0]=A[k];                    //A[0]暂存子树的根节点
    for(i=2*k;i<=len;i*=2){        //沿key较大的子节点向下筛选
        if(i<len&&A[i]<A[i+1])    
            i++;                //取key较大的子节点的下标
        if(A[0]>=A[i])    break;    //筛选结束
        else{
            A[k]=A[i];            //将A[i]调整到双亲节点上
            k=i;                //修改k值，以便继续向下筛选
        }
    }
    A[k]=A[0];                    //被筛选节点的值放入最终位置
}

void HeapSort(ElemType A[],int len){
    BuildMaxHeap(A,len);        //初始建堆
    for(i=len;i>1;i--){            //n-1趟的交换和建堆过程
        Swap(A[i],A[1]);        //输出堆顶元素(和堆底元素交换)
        HeadAdjust(A,1,i-1);    //调整，把剩余的i-1个元素整理成堆
    }
}

归并排序和基数排序

归并排序

ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));    //辅助数组B
void Merge(ElemType A[],int low,int mid,int high){
//表A的两段A[low...mid]和A[mid+1...high]各自有序，将它们合并成一个有序表
    for(int k=low;k<=high;k++)
        B[k]=A[k];                        //将A中所有元素复制到B中
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
        if(B[i]<=B[j])                    //比较B的左右两段中的元素
            A[k]=B[i++];                //将较小值复制到A中
        else
            A[k]=B[j++];
    }//for
    while(i<=mid)    A[k++]=B[i++];        //若第一个表未检测完，复制
    while(j<=high)    A[k++]=B[j++];        //若第二个表未检测完，复制
}
void MergeSort(ElemType 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);            //归并
    }//if
}

基数排序

通过关键字的各分位来进行位数次的分配(位次上相同的关键字按照链表的先后顺序链接在一起)和链接(将各个子序列首尾相连)