課件-8.1內(nèi)排序問(wèn)題基本概念

8內(nèi)排序(8.1-?排序問(wèn)題的基本概?排序（S排序?選擇排序（堆排序?交換排–8.4.1冒泡排–8.4.2快速排?歸并排?分配排序和索引排?排序算法的時(shí)間代內(nèi)排序（8.1- 館員書 、上獎(jiǎng)學(xué)大考試成榜排列圖輸入法排內(nèi)排序（8.1- 排序:指的是待排序記錄存放在計(jì)算機(jī)隨機(jī) 外部排序指的是待排序記錄的數(shù)量很大，以致內(nèi)存一的排序過(guò)程內(nèi)排序（8.1- 小規(guī)模的排序問(wèn)題-內(nèi)排一個(gè)元已經(jīng)有序兩個(gè)元一次比若逆序一次交3次移動(dòng)（賦值n個(gè)元素內(nèi)排序（8.1- 8.1記錄結(jié)點(diǎn)，進(jìn)行排序的基本單關(guān)鍵碼唯一確定記錄的一個(gè)或多個(gè)排序碼(Sort作為排序運(yùn)算依據(jù)的一個(gè)或多個(gè)–由記錄組內(nèi)排序（8.1- 給定一個(gè)序列Rr1r2–其排序碼分別為kk1k2排序的目的：將記錄按排序–形成新的有序序列R'–相應(yīng)排序碼為排序碼的順–其中k'1≤k'2≤…≤k'n，稱為不減–或k'1≥k'2≥…≥k'n，稱為不增內(nèi)排序（8.1- 正序vs.“正序”序列待排序序列正好符合排序要“逆序”序列逆序正序–逆序正序––內(nèi)排序（8.1- 穩(wěn)定

存在多個(gè)具有相同排序碼的記排序后這些記錄的相對(duì)次序保持不穩(wěn)定性例– 96穩(wěn)定–內(nèi)排序（8.1- 穩(wěn)定

存在多個(gè)具有相同排序碼的記排序后這些記錄的相對(duì)次序保持不穩(wěn)定性例

不穩(wěn)––––穩(wěn)定–形式化證不穩(wěn)定，反例說(shuō)––內(nèi)排序（8.1- 時(shí)間代記錄的比較和移動(dòng)次空間代算法本身的繁雜內(nèi)排序（8.1- 對(duì)記錄的排序碼進(jìn)行比較和記錄的移動(dòng)過(guò)最小時(shí)間代最大時(shí)間代平均時(shí)間代

內(nèi)排序（8.1-

?排序問(wèn)題的基本概?排序（S排序?選擇排序（堆排序?交換排–8.4.1冒泡排–8.4.2快速排?歸并排?分配排序和索引排?排序算法的時(shí)間代內(nèi)排序（8.1- 直 排思想 利用有序表 操作進(jìn)行排 :將一個(gè)記錄 例，序列 內(nèi)排序（8.1- 內(nèi)排序（8.1- template 排序算voidInsertSort(RecordArray[],intn)//Array[]為待排序數(shù)組，n為數(shù)組長(zhǎng)Record 臨時(shí)變for(inti=1;i<n;i++) //依 第i個(gè)記TempRecord=intj=i-1;//將那些大于等于記錄i的記錄后while((j>=0) (TempRecord<Array[j]))Array[j+1]= j=j-}//此時(shí)j后面就是記錄i的正確位置Array[j+1]=}}內(nèi)排序（8.1- 穩(wěn)空間代價(jià)時(shí)間代價(jià)情況：比較次數(shù)

ii

n(n1)/

(n2移動(dòng)次數(shù)

i

(n2平均情況

內(nèi)排序（8.1- 8.2.2 直 排序的兩個(gè)性質(zhì)對(duì)于短序列，直 排序比較有 內(nèi)排序（8.1- 列內(nèi)進(jìn)行排序逐漸擴(kuò)大小序列的規(guī)模，而減少小序列個(gè)數(shù)，使得待排序序列逐漸處于更有序的狀態(tài)最后對(duì)整個(gè)序列進(jìn)行掃尾直接排序，內(nèi)排序（8.1- 內(nèi)排序（8.1- 排template<classvoid Sort(RecordArray[],intn) 排序，Array[]為待排序數(shù)組，n為數(shù)組長(zhǎng)inti,//增量delta每次除以2遞for(delta=n/2;delta>0;delta/=for(i=0;i<delta;//分別對(duì)delta個(gè)子序列進(jìn) 排//“&”傳Array[i]的地址，數(shù)組總長(zhǎng)度為n-ModInsSort(&Array[i],n-i,如果增量序列不能保證最后一個(gè)delta間距為可以安排下面這個(gè)掃尾性質(zhì)的排ModInsSort(Array,n,}內(nèi)排序（8.1- 針對(duì)增量而修改 template<classvoidModInsSort(RecordArray[],intn,intdelta)//修改 排序算法，參數(shù)delta表示當(dāng)前的增inti,for(i=delta;i<n;i+=//對(duì)子序列中第i個(gè)記錄，尋找合適 位for(j=i;j>=delta;j-=delta)j以dealta為步長(zhǎng)向前尋找逆置對(duì)進(jìn)行調(diào)if(Array[jArray[j- 置swap(Arrayjj- else}}內(nèi)排序（8.1- 不穩(wěn)空間代價(jià)增量每次除以2遞減，時(shí)間代價(jià)內(nèi)排序（8.1- 增量每次除以2遞減”時(shí)，效率仍然為問(wèn)題：選取的增量之間并不互內(nèi)排序（8.1- Hibbard增量序–{2k-1，2k-1- –如knuth的方法n/3-內(nèi)排序（8.1- 8.38.3.1直接選擇排直接與數(shù)組中第i個(gè)記錄交換，比冒泡排序8.3.2堆排堆排序：基于最大值堆來(lái)實(shí)內(nèi)排序（8.1- 內(nèi)排序（8.1- template<classvoidSelectSort(RecordArray[],intn)//依次選出第i小的記錄，即剩余記錄中最小的那for(inti=0;i<n-1;i++)//首先假設(shè)記錄i就是最小intSmallest=//開始向后掃描所有剩余記for(intj=i+1;j<n;//如果發(fā)現(xiàn)更小的記錄，記錄它的位if(Array[j]<Smallest=//將第i小的記錄放在數(shù)組中第i個(gè)位swap(Array,i,}}內(nèi)排序（8.1- 不穩(wěn)定(見上面的例子空間代價(jià)時(shí)間代比較次數(shù)：Θ(n2)，與冒泡排序一交換次數(shù)：n-內(nèi)排序（8.1- 8.3.2選擇類內(nèi)排直接選擇排序直接從剩余記錄中線性查找最大記堆排序基于最大值堆來(lái)實(shí)現(xiàn)，效率更選擇類外排置換選擇排贏者樹、敗方內(nèi)排序（8.1- 內(nèi)排序（8.1- 內(nèi)排序（8.1- 內(nèi)排序（8.1- 內(nèi)排序（8.1- template<classvoidsort(RecordArray[],intn)intMaxHeap<Record>max_heap=MaxHeap<Record>(Array,n,n堆//算法操作n-1次，最小元素不需要出for(i=0;i<n-1;//依次找出剩余記錄中的最大記錄，即堆max_heap.}內(nèi)排序（8.1- 例，序列 按順序依次構(gòu)造成完全二叉樹的結(jié)點(diǎn)把完全二從下向上，父子交換7取得最小值7刪除13取得次小值刪除27，重新改造成新堆取得次次小值內(nèi)排序（8.1- 建堆刪除堆頂重新建:Θ(log一次建堆，n次刪除總時(shí)間代價(jià)為Θ(nlog空間代價(jià)為內(nèi)排序（8.1- 二分 算法思想 內(nèi)排序（8.1- 二分 由于直 排序算法利用了有序表 操作 234設(shè)已形成有序表{ } 234設(shè)已形成有序表{ }

內(nèi)排序（8.1- 二分 void emTypeR[],int{for(inti=1;i<ni++)//共進(jìn)行n-1 intleft=0,right=i-1;Ele