《排序算法設計》教學課件2

排序算法設計排序基本概念定義排序是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。例如，將下列記錄序列

{52,49,80,36,14,58,61,23,97,75}調(diào)整為序列

{14,23,36,49,52,58,61,75,80,97}排序基本概念關鍵字(key)假定被排序的數(shù)據(jù)是由一組記錄組成的表，而記錄則由若干個數(shù)據(jù)項組成，其中有一項可用來標識一個記錄，稱為關鍵字項，該數(shù)據(jù)項的值稱為關鍵字。關鍵字可用作排序算法的依據(jù)。也稱為排序碼。排序分類按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存外部排序：排序過程中需對外存進行訪問的排序按排序依據(jù)原則插入排序：直接插入排序、折半插入排序、希爾排序交換排序：冒泡排序、快速排序選擇排序：簡單選擇排序、堆排序歸并排序：2-路歸并排序基數(shù)排序排序算法的穩(wěn)定性：假定在待排序的記錄集中，存在多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。排序算法的性能指標1.時間開銷：⑴比較：關鍵碼之間的比較；⑵移動：記錄從一個位置移動到另一個位置。2.空間開銷：輔助存儲空間3.算法的穩(wěn)定性我們從以下幾方面來學習每一種排序方法思想實現(xiàn)時間性能空間性能穩(wěn)定性適用情況直接選擇排序基本思想：將數(shù)據(jù)元素序列分成有序區(qū)和無序區(qū)兩部分。每趟排序都從無序區(qū)中選取出關鍵字最小的數(shù)據(jù)元素放在有序區(qū)的最后，直到全部數(shù)據(jù)元素排序完畢。要點：把元素集合劃分為有序區(qū)和無序區(qū)初始時，有序區(qū)為空每趟排序過程中，從無序區(qū)中選出關鍵字最小的數(shù)據(jù)元素與無序區(qū)的第一個元素交換，以達到擴大有序區(qū)長度的目的。初始：[49386597761327]minjjjjjjmin一趟：13[386597764927]minminjjjjj二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]min直接選擇排序flash演示void

SelectSort(DataTypeL[],intlen){ inti,j,min;

DataTypetmp;//臨時變量，用于元素交換

for(i=0;i<len-1;i++) {//i+1為排序次數(shù) min=i; for(j=i+1;j<len;j++)//查找最小元素 if(L[j].key<L[min].key) min=j;if(min!=i) { tmp=L[i];L[i]=L[min];L[min]=tmp; }}}劃分為兩個表(i>=0)有序表：L[0]～L[i]（第i+1次排序后）無序表：L[i+1]～L[len-1]（第i+1次排序后）兩個循環(huán)大循環(huán)for(i=0;i<len-1;i++)確定比較的新元素L[i]，min=i小循環(huán)for(j=i+1;j<len;j++)確定當前的最小值排序前無序表最小值下標為min直接選擇排序性能分析直接選擇排序比較和移動的次數(shù)無論記錄序列的初始狀態(tài)如何，比較次數(shù)均相同；移動次數(shù)取決于待排記錄序列的狀態(tài)，當待排記錄處于“正序”的情況時，所需進行的記錄移動的次數(shù)最少；當待排記錄處于“逆序”的情況時，所需進行的記錄移動的次數(shù)最多；直接選擇排序性能分析算法評價時間復雜度：T(n)=O(n2)空間復雜度：S(n)=O(1)只使用i、j、k和tmp4個輔助變量，與問題規(guī)模n無關。直接選擇排序算法是一種不穩(wěn)定的排序算法；直接選擇排序算法簡單、容易實現(xiàn)，適用于從大量記錄中選擇一部分排序；插入排序插入排序的基本思想是：將待排序表看做是左、右兩部分，其中左邊為有序區(qū)，右邊為無序區(qū)，整個排序過程就是將右邊無序區(qū)中的記錄依次按關鍵字大小逐個插入到左邊有序區(qū)中，以構成新的有序區(qū)，直到全部記錄都排好序。三種插入排序方法：直接插入排序、二分法插入排序（也叫折半插入排序）和希爾排序。直接插入排序基本思想：將數(shù)據(jù)元素集合分成兩部分，一部分為有序區(qū)，一部分為無序區(qū)。每次從無序區(qū)中取出一個數(shù)據(jù)元素，按其關鍵字大小將其插入到有序區(qū)的適當位置上，直到全部數(shù)據(jù)元素都插入到有序區(qū)中為止。有序序列無序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……需解決的關鍵問題：（1）如何構造初始的有序序列？（2）如何查找待插入記錄的插入位置?直接插入排序要點：把元素集合劃分為有序區(qū)和無序區(qū)初始時，第一個元素默認構成有序區(qū)每趟排序過程中，將無序序列的第一個元素插入到有序序列的適當位置，以達到擴大有序區(qū)長度的目的。查找的方向：將待插入元素對有序區(qū)按照從后向前的順序比較查找其插入位置；查找的標準：對有序區(qū)從后向前查找第一個不大于待插入元素的記錄位置，即在查找插入位置過程中，若待插入元素小于當前有序區(qū)元素，則將當前有序區(qū)元素后移。49386597761327i=1(3849)6597761327i=2(384965)97761327i=3

(38496597)761327i=4

(3849657697)1327i=5

(133849657697)27初始

()i=6(133849657697)27271376976538jjjjjj977665493827直接插入排序flash演示void

InsertSort(DataTypeL[],intlen){ inti,j; DataTypetmp;

for(i=1;i<len;i++) {//i代表排序次數(shù) tmp=L[i];;//存放待插入元素 for(j=i-1;j>=0;j--)//有序表數(shù)據(jù)比較和移動 ｛ if(tmp.key<L[j].key)//關鍵字比較 L[j+1]=L[j];//記錄移動 else break; ｝ L[j+1]=tmp;//插入位置為j+1 }}structRecord{ intdata1;

intdata2;

intkey;};typedefRecordDataType;劃分為兩個表(i>=1)有序表：L[0]～L[i-1]（第i次排序前）無序表：L[i]～L[len-1]（第i次排序前）兩個循環(huán)大循環(huán)for(i=1;i<len;i++)確定插入到有序表的新元素L[i]小循環(huán)for(j=i-1;j>=0;j--)有序表排序新元素L[i]插入在j+1位置上j的起始位置是i-1，終止位置為-1或第一個符合tmp.key

>=L[j].key的位置直接插入排序性能分析排序中的兩個基本操作是：（關鍵字間的）比較和（記錄的）移動。排序的時間性能取決于排序過程中這兩個操作的次數(shù)。直接插入排序這兩個操作的次數(shù)操作次數(shù)取決于待排記錄序列的狀態(tài)，當待排記錄處于“正序”的情況時，所需進行的關鍵字比較和記錄移動的次數(shù)最少，當待排記錄處于“逆序”的情況時，所需進行的關鍵字比較和記錄移動的次數(shù)最多，直接插入排序性能分析算法評價時間復雜度：T(n)=O(n2)空間復雜度：S(n)=O(1)只使用i、j和tmp3個輔助變量，與問題規(guī)模n無關。直接插入排序算法是一種穩(wěn)定的排序算法。直接插入排序算法簡單、容易實現(xiàn)，適用于待排序記錄基本有序或待排序記錄較少時。當待排序的記錄個數(shù)較多時，大量的比較和移動操作使直接插入排序算法的效率降低。已知一組數(shù)據(jù)的排序碼為：{265，301，751，129，937，863，742，694，76，439}要求排序后數(shù)據(jù)從小到大排列，寫出利用直接插入排序和直接選擇排序的過程。初始26530175112993786374269476439第1趟第2趟第3趟第4趟第5趟第6趟第7趟第8趟第9趟初始26530175112993786374269476439第1趟76301751129937863742694265439第2趟76129751301937863742694265439第3趟76129265301937863742694751439第4趟76129265301937863742694751439第5趟76129265301439863742694751937第6趟76129265301439694742863751937第7趟76129265301439694742863751937第8趟76129265301439694742751863937第9趟76129265301439694742751863937直接選擇排序初始26530175112993786374269476439第1趟26530175112993786374269476439第2趟26530175112993786374269476439第3趟12926530175193786374269476439第4趟12926530175193786374269476439第5趟12926530175186393774269476439第6趟129265301