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

1排序2

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

輸入：n個記錄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、直接插入排序基本思想:是將一個記錄插入到已排好序的有序表中，從而得到一個新的，記錄數(shù)增1的有序表。待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]

5voidlnsertSort(SeqListR[],intn){//按遞增序進行插入排序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]時終止

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

}

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

low

mid

high[1527365369]42

low

high

mid[1527365369]42

high

low[152736425369]2、折半插入排序折半插入排序在尋找插入位置時，利用折半查找的原理尋找插入位置,不是逐個比較。7voidBlnsertSort(SeqListL[],intn){//按遞增序進行折半插入排序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、簡單選擇排序思想：首先從1~n個元素中選出關(guān)鍵字最小的記錄交換到第一個位置上。然后從第2個到第n個元素中選出次小的記錄交換到第2個位置上，依次類推。初態(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個關(guān)鍵字序列Kl，K2，…，Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡稱為堆性質(zhì))：

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

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

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

2

堆排序A、堆的示例

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

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

總是將根結(jié)點的值與左右子樹根結(jié)點值進行比較,若不滿足堆條件,則將左右子樹根結(jié)點中的小者與根結(jié)點值交換,一直做到所有子樹均為堆為止.14由無序序列建初始堆的過程2556497811654136(a)無序序列n=8,int(n/2)=4開始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++)/*共進行LEN-1輪起泡*/{for(j=0;j<LEN-i;j++)/*每次起泡要進行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快速排序是對冒泡排序的一種改進。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(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