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

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

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

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

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

內(nèi)排序（8.1-

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

ii

n(n1)/

(n2移動次數(shù)

i

(n2平均情況

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

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