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