计算机考研：数据结构常用算法精析(9)

考研网

数据结构是计算机考研408计算机学科专业基础综合的重要组成部分，考生需要认真复习，尤其是对于数据结构中一些常用的算法问题，考生一定要弄懂弄会，理解的去掌握。新东方在线小编下面一一为大家分析一下，帮助考生更好地去掌握。
        第十章
    内部排序(在内存中进行的排序不需要访问外存的)外部排序(排序量很大，通过分批的读写外存，最终完成排序)
    稳定排序和非稳定排序：看相同记录的相对次序是否回发生改变。主要看在排序过程中的比较是不是相邻记录，如果是相邻比较，一定是稳定的排序。如果不是相邻的比较，就是不稳定的。
    内排序方法 截止目前，各种内排序方法可归纳为以下五类：
    (1)插入排序;(2)交换排序;(3)选择排序;(4)归并排序; (5)基数排序。
    插入排序：包括直接插入排序和希尔排序
    直接插入排序：(稳定的)
    算法描述
    void Insort (sqList &L) ∥对顺序文件F直接插入排序的算法∥
    { int i,j;
    for (i=2;i=2;i--) ∥最多n-1趟排序∥
    { flag=0; //记录每一趟是否发生了交换
    for (j=1;jL.R[j+1].key) ∥两两比较∥
    { temp=L.R[j]; ∥R[j] Û R[j+1]∥
    L.R[j]=L.R[j+1];
    L.R[j+1]=temp;
    flag=1;
    }
    if (flag==0) break; ∥无记录交换时排序完毕∥
    }
    }
    算法分析
    设待排长度为n，算法中总的key比较次数为C。若正序，第一趟就无记录交换，退出循环，Cmin=n-1=O(n);若逆序，则需n-1趟排序，每趟key的比较次数为i-1(2≤i≤n)，故：
    同理，记录的最大移动次数为：
    故起泡排序的时间复杂度T(n)=O(n2)。并且是稳定的。
    快速排序：(不稳定的，时间复杂度O(nlogn))，不需要辅助空间，但有最好和最差之分
                    

kytwo

    分割算法
    int Partition(Sqlist&L,int low,int high)
    { L.R[0]=L.R[low];
    pivotkey=L.R[low].key;
    while(low
    { while(low=pivotkey)
    --high;
    L.R[low]=L.R[high];
    while(low
    ++low;
    L.R[high]= L.R[low];
    }
    return low;
    }
    总控函数：
    void QSort(Sqlist&L,int low,int high)
    { if(low
    {
    pivotloc=Partition(L,low,high);
    QSort(L,low,pivotloc-1);
    QSort(L,pivotloc+1,high);
    }
    }
    调用方法：QSort(L,1,L,lenght);
    算法分析：
    若
原本就正序或逆序，每次调用一次后，记录数只减少了一个，故此时T(n)=C(n+(n-1)+……+1)=O(n2)。这是快速排序效率最差的情况。所以快速排序算法有待改进。
    简单选择排序： 属于稳定排序时间复杂度(O(n2))
    算法描述
    void Slectsort (Sqlist& L) ∥直接选择排序的算法∥
    {
    for (i=1;i
    {
    j=SeloctMinkey(L,i); //从i到L.len中选择key最小的记录
    if (i!=j)
    { temp=L.R[i];
    L.R[i]=L.R[j];
    L.R[j]=temp;
    }
    }
    }
    堆排序：属于选择排序 不稳定，时间复杂度(O(nlogn))，没有最好和最差的分别，也需 要辅助的栈空间
    若ki≥k2i、ki≥k2i+1。此时，根结点k1的值最大，称为“大根堆”。
    若ki≤k2i、ki≤k2i+1满足“”关系，则k1最小，称为“小根堆”。
    在堆排序中，我们采用的是大根堆，原因是大根堆中，根最大，对删除很方便，直接把它与最后一个叶子结点交换就可以了。
    记录key集合k={k1 k2……kn}， 排序 分两步进行：
    (1)将{k1 k2……kn}建成一个大根堆;
    (2)取堆的根(key最大者)，然后将剩余的(n-1)个key又调整为堆，再取当前堆
    的根(key次大者)，……，直到所有key选择完毕。
                    

kyone

    一个元素的堆调整算法：
    //已知H.R[s...m]除H.R[s]之外，均满足堆的定义，本函数只是将H.R[s]放到已经是堆的堆中
    void HeapAdjust (SqList& H, int s, int m) ∥将(H.R[s]……H.R[m])调整成大根堆∥
    {
    rc=H.R[s]; ∥暂存H.R[s]∥
    for(j=2*s;jL.R[j].key)
    break;//说明H.R[s]已经比当前堆中的所有元素大，已经是堆了，不需要调整了
    L.R[s]=L.R[j]; ∥把最大的放到根结点
    s=j; ∥把s与j交换，使得s与下层的堆比较
    }
    L.R[s]=rc; ∥最初的根回归∥
    }
    void Heapsort (SqList& H) ∥ 堆排序算法∥
    {
    //初始建堆
    for (i=L.len/2; i>=1; i--) //从完全二叉树的最后一个非叶子结点开始
    HeapAdjust (L,i,L.len); ∥调整(R[i]……R[n])为堆∥
    //每次取下根(最大的元素)所谓的取下，只是放到数组最后，改变一下数组的下界
    for (i=L.len;i>=2;i--) ∥总共摘n-1次∥
    { temp=F.R[1]; ∥根与当前最后一个结点互换∥
    F.R[1]=F.R[i];
    F.R[i]=temp;
    HeapAdjust (L ,1,i-1); ∥把最后一个元素调整到合适的位置∥
    }
    }
    二路归并排序：(稳定的，时间复杂度O(nlogn)又稳定又效率高，但需要辅助空间TR[1....n]
    二路归并得核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列
    (注意这就是线型表中我们常考的那个，两个有序链表合成一个新的有序表)
    算法描述如下：
    void Merge(RcdType SR[],RcdType&TR[],int i,int m,int n)
    //将有序的SR[i...m]和SR[m+1....n]归并为有序的TR[i....n]
    {
    for(j=m+1,k=i; i<=m&&j<=n; ++k) //谁小就先将谁放进TR
    { if(SR[i].key<=SR[j].key)
    TR[k]=SR[i++];
    else
    TR[k]=SR[j++];
    }
    if(i<=m) //将剩余的SR 直接放到TR
    TR[k....n]=SR[i...m];
    if(j<=n) //将剩余的SR 直接放到TR
    TR[k...n]=SR[j....n];
    }
    void MSort(RcdType SR[], RcdType&TR1[], int s, int t)
    { //将SR[s...t]归并排序为TR1[s...t]
    if(s= =t) //只有一个元素
    TR1[s]=SR[s];
    else
    {
    m=(s+t)/2;//将SR[]平分为两半
    MSort(SR, TR2, s, m);
    MSort(SR, TR2, m+1, t);
    Merge(TR2, TR1, s, m, t);
    }
    }