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

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

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

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

內排序（8.1-

?排序問題的基本概?排序（S排序?選擇排序（堆排序?交換排–8.4.1冒泡排–8.4.2快速排?歸并排?分配排序和索引排?排序算法的時間代內排序（8.1- 直 排思想 利用有序表 操作進行排 :將一個記錄 例，序列 內排序（8.1- 內排序（8.1- template 排序算voidInsertSort(RecordArray[],intn)//Array[]為待排序數組，n為數組長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]=}}內排序（8.1- 穩空間代價時間代價情況：比較次數

ii

n(n1)/

(n2移動次數

i

(n2平均情況

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

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