【文档说明】计算机软件基础汇总课件.ppt，共(45)页，210.001 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-76543.html

以下为本文档部分文字说明：

计算机软件基础Thesoftwarebasicofcomputer主讲：李尊朝西安交通大学计算机教学实验中心第7单元排序教学目标•了解有关排序的–基本概念–排序的典型算法教学要求通过本单元的学习，了解、掌握有关排序的：•基本概念–排序、排序分类、算法稳定性•典型的排序算法–插入排序、

选择排序、交换排序–快速排序、归并排序一、基本概念•将记录按关键字递增(递减)的次序排列起来,形成新的有序序列,称为排序。设n个记录的序列为{R1,R2,…,Rn},其相应关键字序列为{K1,K2,…,Kn},需确定一种排序P

1,P2,…,Pn,使其相应的关键字满足递增(升序),或递减(降序)的关系:Kp1Kp2...Kpn或Kp1Kp2….Kpn排序分类•根据排序元素所在位置的不同,排序分:内排序和外排序。•内排序在排序过程中，所有元素调到内存中进行的排序，称为内排序。内排序效率用比较次数来衡

量。•外排序在数据量大的情况下，不能将全部元素存放在内存，还要使用外存。外排序用读/写外存的次数来衡量其效率。•若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；•若经排序后，记录的相对次序发生了改变，则

称该算法是不稳定的。排序算法的稳定性二、典型排序算法•插入排序•选择排序•交换排序•快速排序•归并排序⑴插入排序（算法3-5）•基本思想：将n个元素的数列分为已有序和无序两个部分。{{a1}，{a2，a3，a

4，…,an}}{{a1(1)，a2(1)}，{a3(1)，a4(1)…,an(1)}}…...{{a1(n-1)，a2(n-1)，…},{an(n-1)}}每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位

置中。有序无序插入排序算法步骤•Step1从有序数列{a1}和无序数列{a2,a3,…,an}开始进行排序;•Step2处理第i个元素时(i=2,3,…,n),数列{a1,a2,…,ai-1}是已有序的,而数列{ai,ai+1,…

,an}是无序的。用ai与ai-1、ai-2,…,a1进行比较,找出合适的位置将ai插入。•Step3重复Step2，共进行n-1的插入处理，数列全部有序。插入排序算法insert_sort(item,n)intitem[],n;{i

nti，j，t;for（i=1；i<n;i++){t=item[i];j=i-1;while(j>=0&&t<item[j]){item[j+1]=item[j];j--;}item[j+1]=t;}}算法讨论•插入算法比较次数和交换

次数约为n2/2，因此，其时间复杂度为O（n2）。•该算法是稳定的。⑵选择排序（算法3-6）•基本思想：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已有序的记录序列的最后（或最前）面，直到全部数列有序。{{a1}，{a2，a3，a4，…,an}}{{a1(1)，

a2(1)}，{a3(1)，a4(1)…,an(1)}}…...{{a1(n-1)，a2(n-1)，…},{an(n-1)}}有序无序选择排序举例设有数列{18，12，10，12，30，16}初始状态：{}，{18，12，10，12，30，16}

比较次数i=1{10}，{12，18，12，30，16}5i=2{10，12}，{18，12，30，16}4i=3{10，12，12}，{18，30，16}3i=4{10，12，12，16}，{30，18

}2i=5{10，12，12，16，18}，{30}1选择排序算法步骤•Step1从原始数列{a1,a2,a3,…,an}开始进行排序，比较n-1次，从中选出最小关键字，放在有序数列中，形成{a1}、{a2,a3,…,

an}有序数列和无序数列两部分，完成第1趟排序。•Step2处理第i趟排序时(i=2,3,…,n),从剩下的n-i+1个元素中找出最小关键字，放在有序数列的后面。•Step3重复Step2，共进行n-1趟的选择处理，数列全部有序。选择排序算法select_sort(intitem[],intc

ount){inti,j,k，t;for(i=0;i<count-1;++i){k=i;t=item[i];for(j=i+1;j<count;++j){if(item[j]<t){k=j;t=item[j];}}item[k]=item[i];item[i]=

t;}}算法讨论•每次选出当前最小关键字，但没有为以后的选择留下任何信息，比较次数仍为O（n2）。•选择排序算法是不稳定的。3、交换排序（冒泡排序）•指导思想：两两比较待排序记录的关键字，并交换不满足顺序要求的那些偶对元素，直到全部数列满足有序为止。•冒泡排序（Bubblesort）是基于交

换排序的一种算法。它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为止。

…a1a2a3…an-1an最大值冒泡排序算法举例设有数列{65,97,76,13,27,49,58}比较次数第1趟{65，76，13，27，49，58}，{97}6第2趟{65，13，27，49，58}，{76，97}5第3趟{13，27，49，58}，{65，76，97}4

第4趟{13，27，49}，{58，65，76，97}3第5趟{13，27}，{49，58，65，76，97}2第6趟{13}，{27，49，58，65，76，97}1冒泡排序（算法3-7）•step1从待排序队列的前端开始(a1)两两比较记录的关键字值,若ai>ai

+1(i=1,2,…,n-1),则交换ai和ai+1的位置,直到队列尾部。一趟冒泡处理，将序列中的最大值交换到an的位置。•step2如法炮制，第k趟冒泡，从待排序队列的前端开始(a1)两两比较ai和ai+1（i=1，2，…n-k)，并进行交换处理,选出序列中第k大的关键字值,放在有序队列的最前端

。•Step3最多执行n-1趟的冒泡处理,序列变为有序。冒泡排序算法3-7bubble(int*item,intcount){inti,j，t;//count个元素for(i=1;i<count;++i)for(j=1;j<=count-i;j++

)if(item[j-1]>item[j]){t=item[j-1];item[j-1]=item[j];item[j]=t;}}改进的冒泡排序3-8•从上述举例中可以看出，从第4趟冒泡起，序列已有序，结果是空跑了3趟。若两次冒泡处理过程中，没有进行交换，说明序列已有序，则停止交换。•用改进

的冒泡算法进行处理，比较次数有所减少。对于数列{65,97,76,13,27,49,58}比较次数第1趟{65，76，13，27，49，58}，{97}6第2趟{65，13，27，49，58}，{76，97}5第3趟{13，27，49，58}，{65，76，97}4第4趟{13，27，4

9}，{58，65，76，97}3改进的冒泡排序算法3-8bubble_a(int*item,intcount){inti,j,t,c;for(i=1;i<count;++i){c=1;for(j=1;j<=count-i;j++){if(item[j-1]>item[j]){t=item[

j-1];item[j-1]=item[j];item[j]=t;c=0;}}if(c==1)break;}}算法讨论•若待排序列有序(递增或递减),则只需进行一趟冒泡处理即可;若反序，则需进行n-1趟的冒泡处理。在最坏的

情况下,冒泡算法的时间复杂度是O(n2)。•当待排序列基本有序时，采用冒泡排序法效果较好。•冒泡排序算法是稳定的。4、快速排序•快速排序法是一位计算机科学家C.A.R.Hoare推出并命名的。曾被认为是最好的一种排序方法。快速排序法是对冒泡排序法的一种改进，也是基于交换排序的一

种算法。因此，被称为“分区交换排序”。快速排序基本思想•在待排序序列中选取一个元素K，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，否则在右边。形成{左子序列}K{右子序列}再分别对左、右两部分实施上述

分解过程，直到各子序列长度为1，即有序为止。快速排序（算法3-9）•Step1分别从两端开始，指针i指向第一个元素A[left]，指针j指向最后一个元素A[right]，分界点取K；•Step2循环（ij）–从

右边开始进行比较：若KA[j]，则将A[j]交换到左边；若K〈A[j]，则j=j-1，再进行比较；–从左边开始进行比较：若K〉A[i]，则i=i+1，再进行比较；若KA[i]，则将A[i]交换到右边。–当i=j时，一次分解操作完成。•Step3

在对分解出的左、右两个子序列按上述步骤继续进行分解，直到子序列长度为1（不可再分）为止，也即序列全部有序。快速排序算法3-9quick_sort(item,count)int*item,count;{qs(item,0,count-1);}qs（）子函数qs(int*item,intleft

,intright){inti,j,x,y,k;i=left;j=right;x=item[(left+right)/2];do{while(item[i]<x&&i<right)i++；while(x<item[j]&&j>left)j--;if(i

<=j){y=item[i];item[i]=item[j];item[j]=y;i++;j--;}}while(i<=j);if(left<j)qs(item,left,j);if(i<right)qs(i

tem,i,right);}快速排序算法举例•{4862347755143598}i=1,j=848•{35623477551498}i=1,j=7•{35347755146298}i=2,j=7•{35143477

556298}i=2,j=6•{35143455776298}i=4,j=6•{35143455776298}i=4,j=5•{3514344855776298}i=4,j=4•第一趟结束{351434}48{55776298}

•{351434}48{55776298}•{34,14}354855{776298}•{14}34354855{62}77{98}算法讨论•分界点选取方法不同，排序效果差异很大；•比较次数为nlogn，即为：O（nlogn）

，交换次数为n/6*logn。•快速排序算法是不稳定的。5、归并排序•归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表；即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序

列。•将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。归并排序（算法3-12）•Step1把待排序的n个记录看作是长度为1的有序序列。将相邻子

序列两两归并为长度为2的有序序列；•Step2把得到的n/2个长度为2的有序子序列再归并为长度为2*2的有序序列；•Step3按Step2的方式，重复对相邻有序子序列进行归并操作，直到成为一个有序序列为止。归并排序算法简述•设有待排序数列{49，38，65，97，76，

12，27}，•第一趟处理，先将每个元素看成是有序的子序列，即[49][38][65][97][76][12][27]•第二趟处理，将长度为1的子序列合并为长度为2的子序列，即[38，49][65，97][12，76][27]

•第三趟处理，将长度为2的子序列合并为长度为4的子序列，即[38，49，65，97][12，27，76]•第四趟处理，将长度为4的子序列合并为长度为8的序列，即[12，27，38，49，65，76，97]归并排序算法3-12说明•设有两个有序序列L1和L2，它

们顺序存放在数组X[l1]，X[l1+1]，…,X[u1]和X[l2],X[l2+1],…,X[u2]中,其中:l2=u1+1;•设置三个变量i、j、m，其中i、j分别表示序列L1和L2中当前要比较的记录的位置

；初值i=l1，j=l2。m表示Swap数组中当前位置，初值m=l1。•归并时，反复比较X[i]和X{j]：–若X[i]X[j]则X[i]送Swap[m]，i++；m++；–若X[i]>X[j]则X[j]送Swap[m]，j++；m++；•当序列L1或L2的全部记录已归并到数组

X中,即i=u1+1,或j=u2+1时,比较结束,然后将另一个序列中剩余的所有记录依此放回到数组Swap中,完成L1和L2的合并。归并排序算法3-12merge_sort(int*x,intn){inti,k,

l;intswap[N];k=1;while(k<n){merge(x,swap,k,n);/*将x中长度为k的两个序列合并，放入swap中*/for(i=0;i<n;i++)/*将数列从SWAP放回X中*/x[i]=swap[i];k=2*k;/*序列长度

加倍*/}}归并排序算法3-12(续一）merge(int*x,int*swap,intk,intn)/*将x中长度为k的两个序列合并，放入swap中，共有n个元素*/{inti,j,l1,l2,u1,u2,m;l1=0;m=0;while(l1+k<n){l2=l1

+k;u1=l2-1;u2=(l2+k-1<n)?l2+k-1:n-1;for(i=l1,j=l2;i<=u1&&j<=u2;m++){if(x[i]<=x[j]){swap[m]=x[i];i++;}else{swap[m]=x[j];j++;}}while(i<=u1)/*将序列1中剩余元素顺

序放回SWAP中*/{swap[m]=x[i];m++;i++;}while(j<=u2)/*将序列1中剩余元素顺序放回SWAP中*/{swap[m]=x[j];m++;j++;}l1=u2+1;/*改变子序列*/}/*将原始序列中剩余的、不足一组的

记录顺序放到SWAP中*/for(i=l1;i<n;i++,m++)swap[m]=x[i];}算法讨论•空间复杂度为O（n），时间复杂度为O（nlogn）•2-路归并排序算法是稳定的。希尔（Shell）排序•数据基本有序，插入排序速度快。•希尔排序是一种快速排序法，出

自D.L.Shell。•指导思想：仍采用插入法，排序过程通过调换并移动数据项来实现。每次比较指定间距的两个数据项，若左边的值小于右边的值，则交换它们的位置。间距d按给定公式减少：di+1=（di+1）/2，直到d等于1为止。d取{9，

5，3，2，1}。•不稳定•时间复杂度与大di序列有关。算法步骤•Step1将n个元素个数列分为n个部分，元素比较间距为d。•step2在第i步，两元素比较的间距取di+1=（di+1）/2{9，5，3，2，1}若ai+1>ai,则交换它们的位置。•Step3重复上述步骤，直到dK=

1。希尔排序举例设有数列“fdacbe”,第1趟d=5fdacbe得到edacbf第2趟d=3edacbf得到cbaedf第3趟d=2cbaedf得到abcedf第4趟d=1abcedf得到adcdefSHELL排序子函数shell(char*

item,intcount){inti,j,k,w;charx;inta[]={9,5,3,2,1};for(w=0;w<5;w++){k=a[w];for(i=k;i<count;i++){x=item[i];j=i-k;while(x<

item[j]&&j>=0)\\插入排序{item[j+k]=item[j];j=j-k;}item[j+k]=x;}}}SHELL排序主函数#include"stdio.h"main(){chars[80]

;intl;printf("Enterastring:");gets(s);l=strlen(s);shell(s,l);printf("Thesortedstringis:%s\n",s);}作业、思考题1、第3章作业思考：第1、8、9、12题作业

：给定数列{503、87、512、61、908、170、897、275、653、426}，计算采用下列算法的比较次数：插入、选择、冒泡、快速、归并排序。结束语•欢迎参加到中心网站《软件基础》课程的学习讨论中来。•中心网址：http：//ctec.xjtu.edu.cn•课件下载地址:ftp

://ctec.xjtu.edu.cn谢谢，再见！