通信原理大綜合課件軟件排序

1排序2

排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作。功能：是將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。學(xué)習(xí)和研究各種排序方法是計(jì)算機(jī)工作者的重要課題之一。2.8排序2.8.1概述3其確切定義如下：

輸入：n個(gè)記錄R1，R2，…，Rn，其相應(yīng)的關(guān)鍵字分別為K1，K2，…，Kn。輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。2.8排序2.8.1概述42.8.2插入排序直接插入、折半插入1、直接插入排序基本思想:是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的，記錄數(shù)增1的有序表。待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]

5voidlnsertSort(SeqListR[],intn){//按遞增序進(jìn)行插入排序inti，j；for(i=2;i<=n；i++)//依次插入R[2]，…，R[n]if(R[i]<R[i-1]){ R[0]=R[i];j=i-1;//R[0]是哨兵，且是R[i]的副本

do

{//從右向左在有序區(qū)R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；//將關(guān)鍵字大于R[i]的記錄后移

j--；

}while(R[0]<R[j])；

//當(dāng)R[0]≥R[j]時(shí)終止

R[j+1]=R[0]；//R[i]插入到正確的位置上

}

}//InsertSort6例：有6個(gè)記錄，前5個(gè)已排序的基礎(chǔ)上，對(duì)第6個(gè)記錄排序。[1527365369]42

low

mid

high[1527365369]42

low

high

mid[1527365369]42

high

low[152736425369]2、折半插入排序折半插入排序在尋找插入位置時(shí)，利用折半查找的原理尋找插入位置,不是逐個(gè)比較。7voidBlnsertSort(SeqListL[],intn){//按遞增序進(jìn)行折半插入排序inti，j,low,high,mid；for(i=2;i<=n；++i)//{L[0]=L[i];Low=1;high=i-1;while(low<=high){

mid=(low+high)/2;

if(L[0]<L[mid])high=mid-1; elselow=mid+1;

}

for(j=i-1;j>=high+1;--j)L[j+1]=L[j]; L[high+1]=L[0];

}}82.8.3選擇排序

1、簡(jiǎn)單選擇排序思想：首先從1~n個(gè)元素中選出關(guān)鍵字最小的記錄交換到第一個(gè)位置上。然后從第2個(gè)到第n個(gè)元素中選出次小的記錄交換到第2個(gè)位置上，依次類(lèi)推。初態(tài)83916839168391683916ijkijkijkijk1

3986互換ijk1

3986ikj1

3986ikj第一趟第二趟1

3986ikj第三趟9voidSelectSort(intP[],intn){inti,j,k,t;for(i=0;i<n-1;++i）

{k=i；

for(j=i+1;j<=n-1;++j)if(P[j]<P[k])k=j;

//P[k]中存放的是第I小的元素

if(k!=i){t=P[i];P[i]=P[k];P[k]=t；}//交換

}}10堆定義

n個(gè)關(guān)鍵字序列Kl，K2，…，Kn稱(chēng)為堆，當(dāng)且僅當(dāng)該序列滿(mǎn)足如下性質(zhì)(簡(jiǎn)稱(chēng)為堆性質(zhì))：

(1)ki≤K2i且ki≤K2i+1或(2)Ki≥K2i且ki≥K2i+1(1≤i≤n/2)

若將此序列所存儲(chǔ)的向量K[1..n]看做是一棵完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿(mǎn)足如下性質(zhì)的完全二叉樹(shù)：樹(shù)中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字。2

堆排序堆排序(HeapSorting)是利用堆的特性進(jìn)行排序的過(guò)程。堆排序包括構(gòu)成初始堆和利用堆排序這兩個(gè)階段。11

2

堆排序A、堆的示例

897624331510(a):堆頂元素取最大值112536497856(b):堆頂元素取最小值12B、實(shí)現(xiàn)堆排序需解決兩個(gè)問(wèn)題：

（1）如何由一個(gè)無(wú)序序列建成一個(gè)堆？（2）輸出堆頂元素后，如何將剩余元素調(diào)整成一個(gè)新的堆？13堆排序的方法方法:將一個(gè)無(wú)序序列以完全二叉樹(shù)表示,從完全二叉樹(shù)的非葉子結(jié)點(diǎn)(下標(biāo)為n的父結(jié)點(diǎn))開(kāi)始,向前逐個(gè)進(jìn)行,直到根結(jié)點(diǎn)為止,對(duì)每個(gè)結(jié)點(diǎn)調(diào)整建堆.調(diào)整堆的方法:(以堆頂元素為最小)

總是將根結(jié)點(diǎn)的值與左右子樹(shù)根結(jié)點(diǎn)值進(jìn)行比較,若不滿(mǎn)足堆條件,則將左右子樹(shù)根結(jié)點(diǎn)中的小者與根結(jié)點(diǎn)值交換,一直做到所有子樹(shù)均為堆為止.14由無(wú)序序列建初始堆的過(guò)程2556497811654136(a)無(wú)序序列n=8,int(n/2)=4開(kāi)始2556493611654178(b)2556413611654978(c)2511413656654978(d)(e)1125413656654978152.8.4交換排序

1、冒泡排序4936416511第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始關(guān)鍵字783665364156364165413641561178363641491156492525251149495611111125252525思想：小的浮起，大的沉底。16#defineLEN5main(){inta[LEN];inti,j,temp;printf("Pleaseinput%dfigures:",LEN);for(i=0;i<LEN;i++)scanf("%d",&a[i]);

for(i=1;i<LEN;i++)/*共進(jìn)行LEN-1輪起泡*/{for(j=0;j<LEN-i;j++)/*每次起泡要進(jìn)行LEN-i次置換*/if(a[j]>a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}for(i=0;i<LEN;i++)printf("%d",a[i]);}

17快速排序是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。2352667182.8.4交換排序

2、快速排序18intpartition(RedTypeL[],intlow,inthigh){//L[0]=L[low];Key=L[low].key;while(low<high){

while(low<high&&L[high].key>=key)--high;L[low]=L[high];

while(low<high&&L[low].key<=ke