《计算机应用基础课件》1.6 排序.ppt

第 1 章数据结构
主要内容
基本数据结构与算法
线性表
栈和队列
树和二叉树
查找
排序
A
B
C
D
E
F
G
姓名学号成绩班级
李红 9761059 95
10
65
865
排序
排序又称分类,是计算机程序设计中一个重要运算,它的功能是将一组任意序列的数据元素,进行按关键字由大到小的顺序(降序)排列或按由小到大的顺序(升序)排列。
排序的对象:这些数据元素可以是数值型,也可以为字符型。若为数值型,则按数值大小排列;若为字符型,则按其ASCII码的顺序排列。
排序的依据:在实际应用中,参加排序的数据元素有时不是单个数据项,而是由多个数据项组成的记录。此时排序应按照关键字的大小进行。所谓关键字是指记录中的某个数据项,用它可以标识一个记录。若此关键字可以唯一地标识一个记录,则称此关键字为主关键字;反之,把用以识别若干记录的关键字称为次关键字。
学号
姓名
系别
住址
电话
981111
李洪
机械
六舍
5371111
982111
王刚
电子
四舍
5372111
983211
王将
计算机
五舍
5373211
983212
张强
机械
六舎
5372221
排序的稳定性:在待排序的记录中,若存在多个关键在相同
的记录,经过排序后,这些具有相同关键在
的记录之间的相对次序发生变化,则称这种
排序方法是稳定的;否则,是不稳定的。
排序的分类:内部排序与外部排序
内部排序:整个排序过程完全在内存中进行.
外部排序:由于待排序记录数据量太大,内存无法容纳
全部数据,排序需要借助外部存储设备才能
完成.
排序算法评价:
算法执行时间(最好、最差及平均情况)、需要附加空间大小
排序
插入排序的基本思想:
插入排序
插入排序三种方法
1. 直接排序: 认可第1个记录已排好序,然后将第2个到第n个记录依次插入到前面已排好序的记录组成的文件中。
: 折半插入排序在寻找插入位置时,不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多,改进效果越明显。
: 将整个无序序列分割成若干个子序列分别进行直接插入排序.
将待排序文件中的记录,逐个按其排序码值的大小插入到已排好序的若干个记录组成的文件中的适当位置,保持新文件有序。
:
思路:认可第1个记录已排好序,然后将第2个到第n个记录依次插入到前面已排好序的记录组成的文件中。
具体过程(第i个记录Ri插入到前面i-1个已排好序的记录中)
将Ri的排序码与前面已排好序的排序码从右向左依次比较,找到Ri应插入的位置;将该位置以后直到Ri-1各记录顺序后移,空出位置插入Ri。
插入排序
<例>直接插入排序:
次数i r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]
(49) 39 66 96 76 11 37 50
(39 49) 66 96 76 11 37 50
i=2
39
(39 49 66) 96 76 11 37 50
i=3
66
(39 49 66 96) 76 11 37 50
i=4
96
(39 49 66 76 96) 11 37 50
i=5
76
(11 39 49 66 76 96) 37 50
i=6
11
(11 37 39 49 66 76 96) 50
i=7
37
(11 37 39 49 50 66 76 96)
i=8
50
对于有n个数据元素的待排序列,插入操作要进行n-1次
.............
/*对N个整数进行升序排序*/
for(i=1;i<N;i++)
{
for(k=i-1; k>=0; k--) //寻找插入位置 if(a[i]>a[k])
break;
//插入到第k个位置的后面
temp=a[i];
for(j=i-1;j>k; j--) //向后移动
a[j+1]=a[j];
a[j+1]=temp;
}
.............
/*改进前面的算法*/
for(i=1;i<N;i++)
{ /*一边比较,一边移动*/
temp=a[i];
for(j=i-1; j>=0 && temp<a[j]; j--)
a[j+1]=a[j];
a[j+1]=temp;
}
temp>a[j]
若降序排序,则:
:
时效分析
最好情况:初始排序码已经有序。共比较n-1次,移动0次。
最坏情况:待排序序