數(shù)據(jù)結(jié)構(gòu)教程第三十六課選擇排序，歸并排序

教學(xué)目的： 掌握選擇排序，歸并排序算法
    教學(xué)重點： 選擇排序之堆排序，歸并排序算法
    教學(xué)難點： 堆排序算法
    授課內(nèi)容：
    一、選擇排序
    每一趟在n-i+1(i=1,2,...n-1)個記錄中選取關(guān)鍵字小的記錄作為有序序列中第i個記錄。
    二、簡單選擇排序
    算法：
    Smp_Selecpass(ListType &r,int i)
    {
    k=i;
    for(j=i+1;j    if (r[j].key    k=j;
    if (k!=i)
    { t=r[i];r[i]=r[k];r[k]=t;}
    }
    Smp_Sort(ListType &r)
    {
    for(i=1;i    Smp_Selecpass(r,i);
    }
    三、樹形選擇排序
    又稱錦標(biāo)賽排序，首先對n個記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在其中一半較小者之間再進(jìn)行兩兩比較，如此重復(fù)，直到選出小關(guān)鍵字的記錄為止。
    四、堆排序
    只需要一個記錄大小的輔助空間，每個待排序的記錄僅占有一個存儲空間。
    什么是堆？n個元素的序列{k1,k2,...,kn}當(dāng)且僅當(dāng)滿足下列關(guān)系時，稱之為堆。關(guān)系一：ki<=k2i 關(guān)系二：ki<=k2i+1（i=1,2,...,n/2)
    堆排序要解決兩個問題：1、如何由一個無序序列建成一個堆？2、如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個新的堆？
    問題2的解決方法：
    sift(ListType &r,int k,int m)
    {
    i=k;j=2*i;x=r[k].key;finished=FALSE;
    t=r[k];
    while((j<=m)&&(!finished))
    {
    if ((jr[j+1].key)) j++;
    if (x<=r[j].key)
    finished:=TRUE;
    else {r[i]=r[j];i=j;j=2*i;}
    }
    r[i]=t;
    }
    HeapSort(ListType &r)
    {
    for(i=n/2;i>0;i--) sift(r,i,n);
    for(i=n;i>1;i--){
    r[1]<->r[i];
    sift(r,i,i-1)
    }
    }
    五、歸并排序
    將兩個或兩個以上的有序表組合成一個新的有序表的方法叫歸并。
    假設(shè)初始序列含有n個記錄，則可看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2或1的有序子序列；再兩兩歸并，如此重復(fù)。
    merge(ListType r,int l,int m,int n,ListType &r2)
    {
    i=l;j=m+1;k=l-1;
    while(i<=m) and(j    {
    k=k+1;
    if (r[i].key<=r[j].key) {r2[k]=r[i];i++;}
    else {r2[i]=r[j];j++}
    }
    if (i<=m) r2[k+1..n]=r[i..m];
    if (j<=n) r2[k+1..n]=r[j..n];
    }
    mergesort(ListType &r,ListType &r1,int s,int t)
    {
    if (s==t)
    r1[s]=r[s];
    else
    {
    mergesort(r,r2,s,s+t/2);
    mergesort(r,r2,s+t/2+1,t);
    merge(r2,s,s+t/2,t,r1);
    }
    ]
    六、總結(jié)