数据结构与算法 (10).ppt

《数据结构与算法 (10).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章.内部排序（Chapter10.InternalSorting)排序又称分类，是计算机中最重要的操作，它是将一个数据元素（或记录）的任意序列排列成一个按关键字有序的序列。若待排序列中存在两个或以上关键字相等的记录，设Ki=Kj(1≤i

2、，则称排序是不稳定稳定的。内部排序（internalsorting）待排序列记录全部存放在计算机随机存储器中进行排序的过程称为内部排序。外部排序（externalsorting）待排序列记录数量太大，不能全部存放在计算机随机存储器中，排序过程中需对计算机外存进行访问，这种排序过程称为外部排序。1、比较操作：比较两个关键字值的大小的操作。排序过程中的两种基本操作：2、移动操作：将记录从一个位置移动到另一个位置的操作。待排序列的三种存储结构：1、顺序存储：存储在地址连续的一组存储单元中（以此为例）。2、链式存储：存储在地址不连续的一组存储单元（链表）中。3、地址存储：记录顺序

3、存储，另设关键字和记录地址排序。typedefstruct{keytypekey;......}elemtype;typedefstruct{elemtype*elem;intlength;}sqlist;§10.1插入排序一、直接插入排序：直接插入排序（straightinsertionsort）是一种最简单的排序方法：将记录一个个插入到已排序好的有序表中，从而得到长度增加的新的有序表。voidstraightinsertsort(sqlist&R){for(i=2;i<=R.length;i++)if(R.elem[i].key

4、elem[0]=R.elem[i];R.elem[i]=R.elem[i-1];for(j=i-2;R.elem[0].key

5、况下，直接插入排序的时间复杂度下降为O(n)。移动次数：最好情况—0最坏情况—(n+4)(n-1)/2平均移动次数：(n+4)(n-1)/4折半插入排序的移动次数与直接插入排序相同，只是比较次数少了，因此其时间复杂度也为O(n2)。三、2-路插入排序：2-路插入排序目的是为了减少排序过程中移动记录的次数，代价是需要n个记录的辅助空间d：将r[1]赋值给d[1]，将d看成循环的，其它记录均与d[1]比较，比其小则在d[1]前插入，反之则在d[1]后插入。2-路插入排序的移动次数大约为n2/2，因此其时间复杂度仍为O(n2)。四、表插入排序：表插入排序需附设一个指针域，通过改

6、变指针的值来达到不移动记录而得到排序结果的目的。表插入排序是用改变指针来代替移动记录操作，因此其时间复杂度还为O(n2)。表插入排序的结果是形成了链表，因此查找时只能用顺序查找，为能使用折半查找，需对记录重新排序，但这不影响其时间复杂度。五、希尔排序：希尔排序（Shell’smethod），又称为“缩小增量排序”（diminishingincrementsort），是一种比较复杂的插入排序。希尔排序的思想是：用一定的增量间隔将待排序列分成多个组，每组都采用简单插入排序；排序完一遍后，缩小增量间隔，再对新的分组采用简单插入排序；反复此过程，直至增量间隔为1，即整个待排序列为

7、一组时，执行一遍简单插入排序后结束。12525634512214845221996187732待排序列：12532256345122148452219961877增量为7：125452322125699345618127712532256345122148452219961877增量为5：12532256345122148452219961877增量为3：1252146182187799452345321225612532256345122148452219961877增量为1：125322563451221484522199