通信原理大综合课件软件排序

1排序2

排序是计算机程序设计中的一种重要操作。功能：是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。学习和研究各种排序方法是计算机工作者的重要课题之一。2.8排序2.8.1概述3其确切定义如下：

输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。2.8排序2.8.1概述42.8.2插入排序直接插入、折半插入1、直接插入排序基本思想:是将一个记录插入到已排好序的有序表中，从而得到一个新的，记录数增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

{//从右向左在有序区R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；//将关键字大于R[i]的记录后移

j--；

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

//当R[0]≥R[j]时终止

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

}

}//InsertSort6例：有6个记录，前5个已排序的基础上，对第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个元素中选出关键字最小的记录交换到第一个位置上。然后从第2个到第n个元素中选出次小的记录交换到第2个位置上，依次类推。初态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个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：

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

若将此序列所存储的向量K[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。2

堆排序堆排序(HeapSorting)是利用堆的特性进行排序的过程。堆排序包括构成初始堆和利用堆排序这两个阶段。11

2

堆排序A、堆的示例

897624331510(a):堆顶元素取最大值112536497856(b):堆顶元素取最小值12B、实现堆排序需解决两个问题：

（1）如何由一个无序序列建成一个堆？（2）输出堆顶元素后，如何将剩余元素调整成一个新的堆？13堆排序的方法方法:将一个无序序列以完全二叉树表示,从完全二叉树的非叶子结点(下标为n的父结点)开始,向前逐个进行,直到根结点为止,对每个结点调整建堆.调整堆的方法:(以堆顶元素为最小)

总是将根结点的值与左右子树根结点值进行比较,若不满足堆条件,则将左右子树根结点中的小者与根结点值交换,一直做到所有子树均为堆为止.14由无序序列建初始堆的过程2556497811654136(a)无序序列n=8,int(n/2)=4开始2556493611654178(b)2556413611654978(c)2511413656654978(d)(e)1125413656654978152.8.4交换排序

1、冒泡排序4936416511第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始关键字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快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。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