《內(nèi)部排序》課件

Chapter10排序Chapter10排序1排序的基本概念直接插入排序起泡排序簡(jiǎn)單選擇排序快速排序堆排序排序的基本概念6.1基本概念6.1基本概念3排序排序在計(jì)算機(jī)程序設(shè)計(jì)中有著非常重要的地位，許多具體應(yīng)用要求對(duì)數(shù)據(jù)進(jìn)行排序，而許多復(fù)雜的算法也要求以排序?yàn)榛A(chǔ)。排序排序在計(jì)算機(jī)程序設(shè)計(jì)中有著非常重要的地位，許多具體應(yīng)用要排序排序：將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。

數(shù)據(jù)表(datalist):它是待排序數(shù)據(jù)對(duì)象的有限集合。主關(guān)鍵字(key):數(shù)據(jù)對(duì)象有多個(gè)屬性域,即多個(gè)數(shù)據(jù)成員組成,其中有一個(gè)屬性域可用來(lái)區(qū)分對(duì)象,作為排序依據(jù)，稱為關(guān)鍵字。也稱為排序碼。排序排序：將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有排序有關(guān)排序的幾個(gè)基本問(wèn)題穩(wěn)定與不穩(wěn)定內(nèi)部排序與外部排序（本章只關(guān)注內(nèi)部排序）性能的衡量排序有關(guān)排序的幾個(gè)基本問(wèn)題排序方法的分類按照排序思想插入排序交換排序選擇排序歸并排序基數(shù)排序按照時(shí)間復(fù)雜度簡(jiǎn)單排序先進(jìn)排序其他排序方法的分類按照排序思想6.2直接插入排序6.2直接插入排序8直接插入排序基本思想：如果要向一個(gè)已經(jīng)排序的順序表中插入元素且保持表的有序性，則只需先依次比較，找到該元素的位置，然后移動(dòng)元素進(jìn)行插入即可。時(shí)間復(fù)雜度是O(n).基于這一思想，如果要對(duì)一個(gè)表進(jìn)行排序，則可以將表看作兩個(gè)部分，前N個(gè)元素已經(jīng)排好序，再將第N+1個(gè)元素插入到前N個(gè)元素中。從N=0開(kāi)始重復(fù)這個(gè)過(guò)程，直到N=L。直接插入排序基本思想：如果要向一個(gè)已經(jīng)排序的順序表中插入元素直接插入排序012345tempi=1i=2012345temp2108254925*162125084925*16252125084925*162125084925*16492125084925*16i=32125084925*1625*2125084925*16直接插入排序012直接插入排序i=4i=52125084925*1616162125084925*162125084925*162125084925*1608直接插入排序i=4i=52125084925*161直接插入排序直接插入排序的算法typedefintSortData;voidInsertSort(SortDataV[],intn){//按非遞減順序?qū)Ρ磉M(jìn)行排序SortDatatemp;inti,j;for(i=1;i<n;i++){temp=V[i];for(j=i;j>0;j--)//從后向前順序比較if(temp<V[j-1])V[j]=V[j-1];elsebreak;V[j]=temp;}}

直接插入排序直接插入排序的算法直接插入排序時(shí)間復(fù)雜度為O(n^2)直接插入排序時(shí)間復(fù)雜度為O(n^2)折半插入排序可見(jiàn)，插入排序由“查找”和“移動(dòng)”兩個(gè)基本過(guò)程組成，而查找這一步驟實(shí)際上是在一個(gè)有序表中進(jìn)行的，因此可以用折半查找代替順序查找來(lái)提高效率。但是由于移動(dòng)這一過(guò)程無(wú)法被簡(jiǎn)化，因此折半插入排序仍然保值O(n^2)的時(shí)間復(fù)雜度。折半插入排序可見(jiàn)，插入排序由“查找”和“移動(dòng)”兩個(gè)基本過(guò)程組鏈表上的插入排序鏈表上的插入排序仍然無(wú)法回避比較的過(guò)程，但是無(wú)需移動(dòng)元素，從總體上看比順序表上插入排序的性能好一些。鏈表上的插入排序鏈表上的插入排序仍然無(wú)法回避比較的過(guò)程，但是6.3起泡排序6.3起泡排序16起泡排序基本思想：基于兩兩比較的思想，對(duì)于N個(gè)元素，如果從第一個(gè)開(kāi)始兩兩比較，將較?。ㄝ^大）的一個(gè)交換到后面，則經(jīng)過(guò)N-1次比較之后，最?。ㄗ畲螅┑脑鼐捅灰苿?dòng)到最后一個(gè)位置?；谶@一思想，如果要對(duì)一個(gè)表進(jìn)行排序，則可以先對(duì)全部元素進(jìn)行兩兩比較，將最?。ㄗ畲螅┑脑匾苿?dòng)到最后，再對(duì)前N-1元素重復(fù)過(guò)程，再對(duì)前N-2個(gè)……直到所有的元素都排好序。起泡排序基本思想：基于兩兩比較的思想，對(duì)于N個(gè)元素，如果從第起泡排序210825492516214925251608214925251608214925251608214925251608初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序214925251608第五趟排序起泡排序21082549251621492525160821起泡排序起泡排序的基本算法typedefintSortData;voidBubbleSort(SortDataa[],intn){ for(inti=0;i<n;i++){ for(intj=0;j<n-i-1;j++){ if(a[j]>a[j+1]) { inttemp=0; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } }

}}起泡排序起泡排序的基本算法起泡排序最多做n-1趟起泡就能把所有對(duì)象排好序。在對(duì)象的初始排列已經(jīng)按排序碼從小到大排好序時(shí),此算法只執(zhí)行一趟起泡,做n-1次排序碼比較,不移動(dòng)對(duì)象。這是最好的情形。時(shí)間復(fù)雜度是O(n^2)。起泡排序起泡排序起泡排序的改進(jìn)：在上面的程序中，如果序列經(jīng)過(guò)很少幾次循環(huán)就已經(jīng)完成了排序，程序仍然會(huì)執(zhí)行N-1次循環(huán)，造成多次循環(huán)做無(wú)用功。例如對(duì)于下面的序列，實(shí)際上經(jīng)過(guò)一次循環(huán)就已經(jīng)有序了。210825492516起泡排序210825492516起泡排序?qū)τ谶@種情況，我們可以設(shè)置一個(gè)標(biāo)志，如果一次循環(huán)發(fā)生數(shù)據(jù)交換，則令標(biāo)志為1；如果一次循環(huán)不發(fā)生數(shù)據(jù)交換，則令標(biāo)志為0，當(dāng)發(fā)現(xiàn)標(biāo)志為0時(shí)，就意味著已經(jīng)排序完成了。起泡排序起泡排序typedefintSortData;voidBubbleSort(SortDataV[],intn){inti=1;intexchange=1;while(i<n&&exchange){exchange=0; //標(biāo)志置為0,假定未交換for(intj=n-1;j>=i;j--)if(V[j-1]>V[j]){ //逆序 Swap(V[j-1],V[j]);//交換 exchange=1;//標(biāo)志置為1,有交換}i++;}}起泡排序typedefintSortData;起泡排序擴(kuò)展閱讀：雙冒泡排序。起泡排序鏈表上的起泡排序思考：在鏈表上進(jìn)行起泡排序，相比順序表有哪些不同？1：從前向后的過(guò)程，需要借助兩個(gè)指針來(lái)完成。2：需要用另外一個(gè)指針來(lái)指示已經(jīng)被移動(dòng)到最后的若干個(gè)元素。3：交換的過(guò)程有不同做法。實(shí)現(xiàn)起來(lái)比較繁瑣，建議課下練習(xí)。鏈表上的起泡排序思考：在鏈表上進(jìn)行起泡排序，相比順序表有哪些6.4簡(jiǎn)單選擇排序6.4簡(jiǎn)單選擇排序26簡(jiǎn)單選擇排序在一組數(shù)據(jù)中選擇具有最小排序關(guān)鍵字的一個(gè)。若它不是這組數(shù)據(jù)中的第一個(gè),則將它與這組數(shù)據(jù)中的第一個(gè)對(duì)調(diào);在剩下的N-1個(gè)數(shù)據(jù)中重復(fù)執(zhí)行第①、②步,直到完成。簡(jiǎn)單選擇排序在一組數(shù)據(jù)中選擇具有最小排序關(guān)鍵字的一個(gè)。簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序的排序過(guò)程21254925*16082125*i=0492516251608490825*4921i=1i=2081625*2521初始交換21,08交換25,16交換49,21簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序的排序過(guò)程21254925*1608簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序的基本算法typedefintSortData;voidSelectSort(SortDataV[],intn){for(inti=0;i<n-1;i++){intk=i;//選擇具有最小排序碼的對(duì)象for(intj=i+1;j<n;j++)if(V[j]<V[k])k=j;//當(dāng)前具最小排序碼的對(duì)象if(k!=i)//對(duì)換到第i個(gè)位置 Swap(V[i],V[k]);} }簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序的基本算法簡(jiǎn)單選擇排序時(shí)間復(fù)雜度仍為O(n^2)簡(jiǎn)單選擇排序時(shí)間復(fù)雜度仍為O(n^2)鏈表上的簡(jiǎn)單選擇排序鏈表上的簡(jiǎn)單選擇排序，最主要的區(qū)別仍然是元素的交換過(guò)程，可以采用與起泡相同的策略：只交換值交換節(jié)點(diǎn)鏈表上的簡(jiǎn)單選擇排序鏈表上的簡(jiǎn)單選擇排序，最主要的區(qū)別仍然是簡(jiǎn)單選擇排序的遞歸實(shí)現(xiàn)終止條件：表中只剩一個(gè)元素子問(wèn)題：對(duì)后N-1個(gè)元素組成的表進(jìn)行簡(jiǎn)單選擇排序。子問(wèn)題的操作：讓第一個(gè)元素與最小元素進(jìn)行交換，然后對(duì)剩余的N-1個(gè)元素進(jìn)行簡(jiǎn)單選擇排序。簡(jiǎn)單選擇排序的遞歸實(shí)現(xiàn)終止條件：表中只剩一個(gè)元素簡(jiǎn)單選擇排序的遞歸實(shí)現(xiàn)voidSelectSort(inta[],intstart,intn){ if(n-start>1){ intk=start; for(inti=start;i<n;i++)//查找 { if(a[k]>a[i]) k=i; } inttemp=a[start];a[start]=a[k];a[k]=temp; SelectSort(a,start+1,n); }}簡(jiǎn)單選擇排序的遞歸實(shí)現(xiàn)voidSelectSort(int三種排序算法的比較上面介紹的三種排序算法都是基本排序算法，思路也比較簡(jiǎn)單和直接。時(shí)間復(fù)雜度為O(n^2)基本過(guò)程都是將表劃分為兩部分，一部分已經(jīng)排好序，一部分沒(méi)有排好序，按照某種規(guī)則將未排序部分的元素加入到已排序部分。在實(shí)現(xiàn)時(shí)，都需要兩層循環(huán)。三種排序算法的比較上面介紹的三種排序算法都是基本排序算法，思三種排序算法的比較主要的區(qū)別就在于“如何從未排序的部分選擇元素，加入到已排序部分？”插入排序：隨意選擇，有序插入。起泡排序：相鄰元素兩兩比較，將最?。ㄗ畲螅┑脑馗郊拥揭雅判虿糠肿钋懊妫ㄗ匀槐ＷC有序）。選擇排序：查找最?。ㄗ畲螅┰?，將這個(gè)元素附加到已排序部分的最后（自然保證有序）。三種排序算法的比較主要的區(qū)別就在于“如何從未排序的部分選擇元6.5快速排序6.5快速排序36快速排序基本思想是任取待排序?qū)ο笮蛄兄械哪硞€(gè)對(duì)象(例如取第一個(gè)對(duì)象)作為基準(zhǔn),按照該對(duì)象的排序碼大小,將整個(gè)對(duì)象序列劃分為左右兩個(gè)子序列：

左側(cè)子序列中所有對(duì)象的排序碼都小于或等于基準(zhǔn)對(duì)象的排序碼右側(cè)子序列中所有對(duì)象的排序碼都大于基準(zhǔn)對(duì)象的排序碼快速排序基本思想是任取待排序?qū)ο笮蛄兄械哪硞€(gè)對(duì)象(例如取第快速排序經(jīng)過(guò)這樣的處理，基準(zhǔn)對(duì)象就被安置在了正確的位置。然后分別對(duì)左右兩個(gè)子序列重復(fù)施行上述方法，直到所有的對(duì)象都排在相應(yīng)位置上為止?；鶞?zhǔn)對(duì)象也稱為樞軸（或支點(diǎn)）記錄?？焖倥判蚪?jīng)過(guò)這樣的處理，基準(zhǔn)對(duì)象就被安置在了正確的位置。快速排序2108254925*16初始關(guān)鍵字08254925*162108254925*1608254925*1608254925*1608254925*1621prikey一次交換二次交換三次交換四次交換完成一趟排序ijijjiijjiji快速排序2108254925*16初始關(guān)鍵字08254925快速排序08254925*1621完成一趟排序分別進(jìn)行快速排序08254925*1621有序序列08254925*1621快速排序08254925*1621完成一趟排序分別進(jìn)行快速排快速排序快速排序的基本代碼voidQuickSort(SqList&L,intlow,inthigh){ //在序列l(wèi)owhigh中遞歸地進(jìn)行快速排序if(low<high){ intpivotloc=Partition(L,low,high);//劃分 QuickSort(L,low,pivotloc-1);//對(duì)左序列同樣處理 QuickSort(L,pivotloc+1,high);//對(duì)右序列同樣處理}}快速排序快速排序的基本代碼快速排序intPartition(SqList&L,intlow,inthigh){ pivotkey=L.r[low].key;//基準(zhǔn)對(duì)象關(guān)鍵字 while(low<high){ while(low<high&&L.r[high].key>=pivotkey) --high; L.r[low]>L.r[high];//小于基準(zhǔn)的移到左側(cè) while(low<high&&L.r[low].key<=pivotkey) ++low; L.r[high]>L.r[low];//大于基準(zhǔn)的移到右側(cè) } returnlow;}快速排序intPartition(SqList&L,快速排序快速排序的時(shí)間復(fù)雜度為O(nlogn)，是最快的內(nèi)排序算法之一但是，由于快速排序的過(guò)程比較復(fù)雜，在對(duì)很短的序列進(jìn)行排序時(shí)，它的速度不如插入/比較/選擇排序?？焖倥判蚩焖倥判虻臅r(shí)間復(fù)雜度為O(nlogn)，是最快的內(nèi)排快速排序快速排序的改進(jìn)判斷序列的長(zhǎng)度，當(dāng)小于特定長(zhǎng)度時(shí)，就改用其他排序方法。使用非遞歸的方法?？焖倥判蚩焖倥判虻母倪M(jìn)快速排序快速排序是“20世紀(jì)十大著名算法”之一。單純形法蒙特卡洛模擬快速傅里葉變換快速排序快速排序是“20世紀(jì)十大著名算法”之一。6.6堆排序6.6堆排序46堆首先介紹一種新的數(shù)據(jù)結(jié)構(gòu)：堆(Heap)。堆是一種特殊的二叉樹，首先，它是一個(gè)完全二叉樹，并且對(duì)于任意一個(gè)非葉子節(jié)點(diǎn)，其葉子的值都大于（小于）該節(jié)點(diǎn)的值。相應(yīng)的，稱其為一個(gè)大頂堆（小頂堆）。注意：與二叉排序樹的概念相區(qū)分。堆必須是一個(gè)完全二叉樹節(jié)點(diǎn)值的大小只關(guān)注上下層而不分左右堆首先介紹一種新的數(shù)據(jù)結(jié)構(gòu)：堆(Heap)。堆090987877878454565653131532323531717小頂堆大頂堆堆09098787787845456565313153232堆的建立思考：如何將一個(gè)任意的完全二叉樹變成一個(gè)堆。算法基本思路：從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始（從上到下，從左到右的順序），對(duì)于每一個(gè)非葉子節(jié)點(diǎn)重復(fù)執(zhí)行以下操作（以調(diào)整為大頂堆為例）：將節(jié)點(diǎn)的值(k)與它的兩個(gè)葉子節(jié)點(diǎn)的值(k1,k2)進(jìn)行比較,并且：如果滿足大頂堆的性質(zhì)（k>k1且k>k2），則不進(jìn)行操作，退出循環(huán)。如果不滿足，則將其與葉子節(jié)點(diǎn)中較大的一個(gè)進(jìn)行交換，并繼續(xù)執(zhí)行循環(huán)。堆的建立思考：如何將一個(gè)任意的完全二叉樹變成一個(gè)堆。堆的建立以一個(gè)小頂堆的建立過(guò)程為例5353171778780923456587最后一個(gè)0923456587倒數(shù)第二個(gè)堆的建立以一個(gè)小頂堆的建立過(guò)程為例5353171778780堆的建立以一個(gè)小頂堆的建立過(guò)程為例53531717787809234565870923456587注意這一次調(diào)整有點(diǎn)麻煩堆的建立以一個(gè)小頂堆的建立過(guò)程為例5353171778780堆的建立以一個(gè)小頂堆的建立過(guò)程為例53171778780923456587092345658753堆的建立以一個(gè)小頂堆的建立過(guò)程為例5317177878092堆的建立以一個(gè)小頂堆的建立過(guò)程為例53171778780923456587092345658753堆的建立以一個(gè)小頂堆的建立過(guò)程為例5317177878092堆的建立至此，小頂堆的建立就完成了。堆的建立至此，小頂堆的建立就完成了。堆排序那么如何使用“堆”這種數(shù)據(jù)結(jié)構(gòu)來(lái)排序呢？只需要如下的過(guò)程：將堆中最后一個(gè)節(jié)點(diǎn)與根節(jié)點(diǎn)交換，并且將調(diào)整之后的最后一個(gè)節(jié)點(diǎn)輸出出來(lái)，就得到了目前堆中最?。ㄗ畲螅┑脑?。將剩余的N-1個(gè)元素重新調(diào)整成堆（這一步只需要針對(duì)根節(jié)點(diǎn)進(jìn)行調(diào)整就可以）。重復(fù)以上過(guò)程直到全部元素都被輸出了。堆排序那么如何使用“堆”這種數(shù)據(jù)結(jié)構(gòu)來(lái)排序呢？堆排序以利用大頂堆進(jìn)行排序的過(guò)程為例：492525*211608012345082525*162149025431交換8與49，并輸出49堆排序以利用大頂堆進(jìn)行排序的過(guò)程為例：492525*2116堆排序以利用大頂堆進(jìn)行排序的過(guò)程為例：2525*082116490123451625*08252149025431重新調(diào)整為大頂堆，然后交