《排序算法設(shè)計(jì)》教學(xué)課件2

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

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

{14,23,36,49,52,58,61,75,80,97}排序基本概念關(guān)鍵字(key)假定被排序的數(shù)據(jù)是由一組記錄組成的表，而記錄則由若干個(gè)數(shù)據(jù)項(xiàng)組成，其中有一項(xiàng)可用來(lái)標(biāo)識(shí)一個(gè)記錄，稱(chēng)為關(guān)鍵字項(xiàng)，該數(shù)據(jù)項(xiàng)的值稱(chēng)為關(guān)鍵字。關(guān)鍵字可用作排序算法的依據(jù)。也稱(chēng)為排序碼。排序分類(lèi)按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存外部排序：排序過(guò)程中需對(duì)外存進(jìn)行訪問(wèn)的排序按排序依據(jù)原則插入排序：直接插入排序、折半插入排序、希爾排序交換排序：冒泡排序、快速排序選擇排序：簡(jiǎn)單選擇排序、堆排序歸并排序：2-路歸并排序基數(shù)排序排序算法的穩(wěn)定性：假定在待排序的記錄集中，存在多個(gè)具有相同鍵值的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序仍然保持不變，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱(chēng)這種排序算法是穩(wěn)定的；否則稱(chēng)為不穩(wěn)定的。排序算法的性能指標(biāo)1.時(shí)間開(kāi)銷(xiāo)：⑴比較：關(guān)鍵碼之間的比較；⑵移動(dòng)：記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。2.空間開(kāi)銷(xiāo)：輔助存儲(chǔ)空間3.算法的穩(wěn)定性我們從以下幾方面來(lái)學(xué)習(xí)每一種排序方法思想實(shí)現(xiàn)時(shí)間性能空間性能穩(wěn)定性適用情況直接選擇排序基本思想：將數(shù)據(jù)元素序列分成有序區(qū)和無(wú)序區(qū)兩部分。每趟排序都從無(wú)序區(qū)中選取出關(guān)鍵字最小的數(shù)據(jù)元素放在有序區(qū)的最后，直到全部數(shù)據(jù)元素排序完畢。要點(diǎn)：把元素集合劃分為有序區(qū)和無(wú)序區(qū)初始時(shí)，有序區(qū)為空每趟排序過(guò)程中，從無(wú)序區(qū)中選出關(guān)鍵字最小的數(shù)據(jù)元素與無(wú)序區(qū)的第一個(gè)元素交換，以達(dá)到擴(kuò)大有序區(qū)長(zhǎng)度的目的。初始：[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;//臨時(shí)變量，用于元素交換

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

intdata2;

intkey;};typedefRecordDataType;劃分為兩個(gè)表(i>=1)有序表：L[0]～L[i-1]（第i次排序前）無(wú)序表：L[i]～L[len-1]（第i次排序前）兩個(gè)循環(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或第一個(gè)符合tmp.key

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