文档介绍：排序算法及算法分析
2008/12/18
1
问题的提出:
为什么要排序?有序表的优点?缺点?
构造关系。
按照什么原则排序?
比较?
如何进行排序?
2
基本概念
排序(Sorting):
简单地说,排序就是把一组记录按照某个(或某几个)字段的值以递增(由小到大)或递减(由大到小)的次序重新排列的过程。(如按年龄从小到大排序)
学号
姓名
年龄
性别
2004001
张佳
18
男
2004002
王鹏
19
男
2004003
刘宁
17
女
2004004
李娟
18
女
2004005
陈涛
19
男
2004006
李小燕
18
女
3
作为比较基础的一个(或多个)字段,称为排序码。排序码可以是数值、符号或符号串。
排序码不一定是关键码,关键码可以作为排序码。关键码是唯一的,但排序码不一定唯一。排序码不唯一时,排序的结果可能不唯一。
参与排序的对象,称为记录。一个记录可以包含多个字段。
如果记录集合中存在多个排序码相同的记录,经过排序后,排序码相同的记录的前后次序保持不变,则这种排序方法称为是稳定的,否则是不稳定的。
排序码与关键码(primary key)
4
排序方法可以分为五种∶插入排序、选择排序、交换排序、分配排序和归并排序。
在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。
本章侧重讨论内排序的方法,但有些方法(特别是归并排序的思想)也可以用于外排序。
排序的类型
5
排序算法的评价
评价排序算法好坏的标准
执行算法所需的时间
执行算法所需要的附加空间
算法本身的复杂程度也是考虑的一个因素
排序的时间开销是算法好坏的最重要的标志
排序的时间开销衡量标准:
算法执行中的比较次数(必须)。
算法执行中的移动次数(有可能避免)。
通常会关注最坏情况和平均情况的开销。
6
插入排序
基本思想:每步将一个待排序的记录,按其排序码大小插到前面已经排序的字序列的合适位置,直到全部插入排序完为止。
x
顺次选取一个元素
插入到合适位置
7
插入排序的细分类
如何插入到已排好序的序列中?
直接插入(从后向前找位置后插入)
O(n2)
二分法插入(按二分法找位置后插入)
O(nlog2n)
表插入排序(按链表查找位置后插入)
O(n2)
8
直接插入排序
基本思想:
假定前面m 个元素已经排序;
取第(m+1) 个元素,插入到前面的适当位置;
一直重复,到m=n 为止。
(初始情况下,m = 1)
9
第一趟: {23}, [起始只有一个记录]
{11, 23} 11
第二趟: {11,23},
{11,23,55} 55
第三趟: {11,23,55},
{11,23,55,97} 97
第四趟: {11,23,55,97},
{11,19,23,55,97} 19
第五趟: {11,19,23,55,97},
{11,19,23,55,80,97} 80
示例:{23,11,55,97,19,80}
10