[電腦基礎(chǔ)知識(shí)]數(shù)據(jù)結(jié)構(gòu)9第八章：排序(參考版)
2025-01-22 15:30本頁面
【正文】 。 6. 一個(gè)線性表元素由正整數(shù)和負(fù)整數(shù)組成 ， 利用一趟快速排序思想編寫一個(gè)算法 ， 把正整數(shù)和負(fù)整數(shù)分開 ， 使線性表的前面部分為負(fù)整數(shù) ， 后面部分為正整數(shù) 。 （ 1） {100， 85， 98， 77， 80， 60， 82， 40， 20， 10， 66}； （ 2） {100， 98， 85， 82， 80， 77， 66， 60， 40， 20， 10}； （ 3） {100， 85， 40， 77， 80， 60， 66， 98， 82， 10， 20}； （ 4） {10， 20， 40， 60， 66， 77， 80， 82， 85， 98， 100}； 5. 已知 ｛ k１ ， k２ ， ．．． ， kn｝ 是堆 ， 試寫一個(gè)算法將 ｛ k１ ， k２ ， ．． ， kn+1｝ 調(diào)整為堆 。 2． 設(shè)有 5000個(gè)無序的結(jié)點(diǎn) ， 希望用最快的速度挑選出其中前 10個(gè)最大鍵值的結(jié)點(diǎn) ， 在快速排序 、 堆排序和歸并排序方法中 ， 采用哪種方法最好 ？ 3. 對(duì)于給定的鍵值序列 ｛ 12， 2， 16， 30， 8， 28， 4，10｝ ， 分別寫出直接插入排序 、 希爾排序 、 直接選擇排序 、 冒泡排序 、 快速排序 、 歸并排序 、 堆排序和基數(shù)排序的過程 ， 并算出比較次數(shù)和結(jié)點(diǎn)移動(dòng)次數(shù) 。amp。(r[j] r[j+1］ )) j++； if(xr[j］ ) ｛ r[i]=r[j]； i=j； j*=2； ｝ else j=w+1； ｝ r[i]=x； ｝ 堆排序的算法 下面給出堆排序的算法 。(ji)) i++； if(ij){r［ j］ =r［ i］ ； j； } ｝ while(ij) r［ i］ =x； if((i+1)w)｛ s1［ ＋＋ k］ =i+1； s2［ k］ =w； ｝ w=i1； ｝ if(k0){t=s1［ k］ ； w=s2［ k］ ； } }while((k０ ） ||（ tw） )； ｝ 直接選擇排序的算法 直接選擇排序的算法如下： void zjxzpx(int r[]， int n) ｛ // int i， j， k， x； for (i=0； in1； j++) {k=i； for(j=i+1， jn； j++ if(r[j]r[k]) k=j； if(i!=k) ｛ x=r［ i］ ； r［ i］ =r［ k］ ； r［ k］ =x； ｝ ｝ ｝ 樹形選擇排序 樹形選擇排序 圖 例 圖 例 堆排序 圖 例 圖 例 堆的篩選
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1