软件技术基础第三章2基本排序

《软件技术基础第三章2基本排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、冒泡排序与快速排序(交换排序法)简单插入排序与希尔排序(插入排序法)简单选择排序与堆排序(选择排序法)其他排序方法简介排序是数据处理的重要内容,是指将一个无序序列整理成按值非递减顺序排列的有序序列(本章仅介绍内部排序:即能够在内存中完成的排序)基本排序实质上,我们可以对排序定义再抽象即将无序序列整理成具有逻辑大小前驱后继排列的序列交换排序交换排序的思想是通过交换元素以达到消除逆序的目的冒泡排序(1)从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中

2、，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后。(2)除去最后已经冒出的元素,对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时冒出的元素构成的线性表已经变为有序。逆序：在数组A[n]中,存在iA[j]则称A[i]和A[j]构成一个逆序5173169428615316742869第一遍13156427689第二遍11354266789第三遍11342566789第四.五.六遍11324566789第七遍11234566789第八遍11234566789第九.十.十一遍冒泡排序需要经过(n-1)+(n-2)

3、+(n-3)+…+1=n(n-1)/2次比较算法复杂度量级为O(n2)双向冒泡排序(1)从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后。(2)从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中

4、的最小者换到了表的最前面(3)对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。bubsort(p，n)intn；ETp[]；{intm，k，j，i；ETd；k＝0；m＝n－1；while(k＜m)/*子表未空*/{j＝m－1；m＝0；for(i＝k；i＜＝j；i＋＋)/*从前往后扫描*/if(p[i]＞p[i＋1])/*发现逆序进行交换*/{d＝p[i]；p[i]＝p[i+1]；p[i+1]＝d；m＝i；}j＝k＋1；k＝0；for(i＝m；i＞＝j；i－－)/*从后往前扫描*/if(p[i－1]＞p[i])/*发现逆序

5、进行交换*/{d＝p[i]；p[i]＝p[i-1]；p[i-1]＝d；k＝i；}}return；}输入：无序序列P(1：n)。输出：有序序列P(1：n)。虽然从算法上优化了冒泡法排序,但是其最坏算法复杂度量级依然是O(n2)快速排序:解决冒泡排序中一次仅通过交换两个相邻元素完成一个逆序的消除的效率不高的问题快速排序的思想为:从线性表中取一个元素,设为T,小于T的元素移到T前,大于T的元素移到T后从而将线性表以T为分界分成两个子表.关键是对线性表的分割.首先，在表的第一个、中间一个与最后一个元素中选取其中一项作为枢纽，设为P(k)，并将P(k)赋给T，再将

6、表中的第一个元素移到P(k)的位置上。然后设置两个指针i和j分别指向表的起始与最后的位置。反复作以下两步：(1)将j逐渐减小，并逐次比较P(j)与T，直到发现一个P(j)＜T为止，将P(j)移到P(i)的位置上。(2)将i逐渐增大，并逐次比较P(i)与T，直到发现一个P(i)＞T为止，将P(i)移到P(j)的位置上。上述两个操作交替进行，直到指针i与j指向同一个位置（即i＝j）为止，此时将T移到P(i)的位置上。算法描述例:将序列49、38、65、97、76、13、27、49用快速排序的方法进行排序。012345678493838656597977676131

7、327274949ji49界点9e.g:将序列49、38、65、97、76、13、27、49用快速排序的方法进行排序。012345678493838656597977676131327274949ji49界点10e.g:将序列49、38、65、97、76、13、27、49用快速排序的方法进行排序。012345678493838656597977676131327274949ji49界点11e.g:将序列49、38、65、97、76、13、27、49用快速排序的方法进行排序。012345678493838656597977676131327274949ji49界

8、点12e.g:将序列49、38、65、