数据结构--排序

《数据结构--排序》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、排序1.插入排序：按照关键字大小将一个记录插入到一个有序的文件中的适当的位置，并且插入后使文件任然是有序的。2.关键码：记录屮的某一个可以用来标识一个数据元索（记录）的数据项被称为关键字项，该数据项的值称为关键码。3.数据表：是待排序数据对象的有限集合。4.排序：是把一组记录，按照记录中某个关键字进行有序排列的过程5.排序的稳定性：如果待排序的文件中存在多个关键字相同的记录，而排序后这些记录的相对次序仍然保持不变则称这种排序方法是稳定的，否则即称这种排序方法是不稳定的。sit希尔排序示意图:012345679Ml初始关键字70304010

2、802090100756045TT601T10048140207510302060454070807590HH)（町增就为3时的分组惜况第•趟井序结果70100206030（b）增虽为2时的分纽怙况第二趟推序结果10302040456070807590100第三话拮序结果1020304045607075809010(1快速排序示意图:初始关键字：28（28作为基准）i192748561210252050A■J第一次交换后：201927485612102550AA■1■J第二次交换后：201927561210254850■■J第三次交换后：

3、201927255612104850■1■J第四次交换后：201927251210564850•1■J第五次交换后：201927251012564850AA•■J完成一趟排序后:201927251012285648；50快速排序主要思路是依靠冒泡排序改进得来。树形选择排序的示意图:例{49,38,65,97,76,13,27,49}输出13例{49,38,65,97,76,13,27,49}输出13.27例{49,38,65,97,76,13,27,49}输出13,27,38完全二叉树构建最大堆的示意图:链式基数排序过程如下图:0(a)：

4、初始记录的静态琏表。T278卜门0「卜*063卜*930卜门89十*184耳505卜*269卞*008亦(a)e[0]e[l]e[2]e[3]e[4]e[5]e[6]e[7]e[8]930赢083f[6]如］008干589278109ffsi3(b)图(b):第一趟按个位数分配，修改结点指针域，将谁表中的记录分配到相应链队列图(c):第一趟收集：将各队列链接起来，形成单链表。->930-4-008e[0]$9]109e[l]e[2]e[3]e[4]e[7]e[8]008505fll]930f[2]f[彳f[4]e[习e[6]f[5]f[9

5、](d)图(d):第二趟按十位数分配，修改结点指针域，将琏表中的记录分配到相应链队列中。图(e)：第二趟收集：将各队列谁接起来，形成单琏表。T505斗008斗063■4^""斗278斗083589(e)e[6]fI7]_>008斗°63斗109斗184斗二6厂斗278斗505斗930f[8]