软件技术基础3_2.ppt

第三章查找与排序(下);本节内容;排序的基本概念;简单起见，这里用顺序存储结构描述待排序的记录。 顺序存储结构（C语言描述）： #define N n typedef struct record { int key ； /* 关键字项 */ int otherterm； /* 其它项 */ } ； typedef struct record RECORD； RECORD ]；/*RECORD型的N+1元数组*/;典型排序算法;一、冒泡排序;21;25*;2.冒泡排序算法;冒泡排序算法举例;3.冒泡排序实现;4.改进的冒泡排序;bubble_a(int *item,int count) { int a,b,t,c; for(a=1;acount;++a) /* n-1趟的循环 */ { c=1; /* 设置交换标志 */ for(b=1;b=count-a;b++)/* n-1趟处理 */ { if(item[b-1]item[b])/* 若逆序，则 */ { t=item[b-1]; /* 交换位置 */ item[b-1]=item[b]; item[b]=t; c=0; } /* 若有交换，则 */ } /* 改变交换标志 */ if(c) break; /* 若没有交换，则 */ } /* 退出处理 */ };5. 算法评价;书上的算法;示例;二、快速排序;1.快速排序基本思想;21;2. 快速排序算法;qs(int *item,int left,int right) { int i,j,x,y,k; i=left; j=right; x=item[(left+right)/2]; /* 计算中点位置 */ do{ /* i≤j 的循环处理 */ while(item[i]x iright ) i++ ； /* 确定i点交换位置 */ while(xitem[j] jleft) j--; /* 确定j点交换位置 */ if(i=j) /* 如果i、j位置合法，则交换 */ { y=item[i]; /* A[i]和A[j]的位置 */ item[i]=item[j]; item[j]=y; i++; j--; } } while(i=j); if(leftj) qs(item,left,j); /* 对分割出的左部处理*/ if(iright) qs(item,i,right); /*对分割出的右部处理*/ };快速排序算法举例;快速排序算法举例（续一）;快速排序算法举例（续二）;快速排序算法举例（续三）;线性表P（m：n）的分割算法;书上的快速排序算法;4. 算法评价;三、简单插入排序;2.插入排序算法步骤;插入排序举例;插入排序算法实现;4. 算法评价;四.希尔（Shell）排序;2. 算法步骤;3. SHELL排序算法(c++语言);4. 算法评价;五、简单选择排序;2.选择排序算法步骤;选择排序举例;3.选择排序算法;4. 算法评价;六、堆排序;1. 堆的定义;10;70; * 2. 建堆 ;(a)只有一个结点的树是堆 (b)而在完全二叉树中，所有序号i = low(n/2)的结点都是叶子，因此以这些结点为根的子树都已是堆。;(c) 只需依次将序号为low(n/2) low(n/2)-1， ...，1的结点作为根的子树都调整为堆即可。;