[電腦基礎(chǔ)知識]數(shù)據(jù)結(jié)構(gòu)9第八章：排序-全文預(yù)覽
【正文】 ； 5. 已知 ｛ k１ ， k２ ， ．．． ， kn｝ 是堆 ， 試寫一個算法將 ｛ k１ ， k２ ， ．． ， kn+1｝ 調(diào)整為堆 。 。 6. 一個線性表元素由正整數(shù)和負(fù)整數(shù)組成 ， 利用一趟快速排序思想編寫一個算法 ， 把正整數(shù)和負(fù)整數(shù)分開 ， 使線性表的前面部分為負(fù)整數(shù) ， 后面部分為正整數(shù) 。 2． 設(shè)有 5000個無序的結(jié)點 ， 希望用最快的速度挑選出其中前 10個最大鍵值的結(jié)點 ， 在快速排序 、 堆排序和歸并排序方法中 ， 采用哪種方法最好 ？ 3. 對于給定的鍵值序列 ｛ 12， 2， 16， 30， 8， 28， 4，10｝ ， 分別寫出直接插入排序 、 希爾排序 、 直接選擇排序 、 冒泡排序 、 快速排序 、 歸并排序 、 堆排序和基數(shù)排序的過程 ， 并算出比較次數(shù)和結(jié)點移動次數(shù) 。(r[j] r[j+1］ )) j++； if(xr[j］ ) ｛ r[i]=r[j]； i=j； j*=2； ｝ else j=w+1； ｝ r[i]=x； ｝ 堆排序的算法 下面給出堆排序的算法 。(ij)) j； if(ij){r［ i］ =r［ j］ ； i++； } while((r[i]=x)amp。(ji）） j if(ij){r[i]=r[j]； i++； } while((r[i]=x)amp。(r［ j］ .key)) ｛ r［ j＋ k］ =r［ j］ ； j=k； ｝ r［ j+k］ =x； } k=k／ 2； } ｝ 圖 例 冒泡排序算法 冒泡排序算法如下： void qppx(int r[]， int n) ｛ // int i， j， k， x； j=1； k=1； while ((jn)amp。amp。amp。amp。amp。(j=w)) ｛ k++； if(r[i]=r[j]) t[k]=r[i++]； else t[k]=r[j++]； } if（ im） while(j=w)t[++k]=r[j++]； else while(i=m) t[++k]=r[i++]；
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1