数据结构（c语言描述） 教学课件 作者 库波 第9章 排序.ppt

数据结构(C#)主编: (在排序中把数据元素称为记录)集合或序列重新排列成按记录的某个数据项值递增(或递减)的序列。下表是一个学生成绩表,其中某个学生记录包括学号、姓名及计算机文化基础、C语言、数据结构等课程的成绩和总成绩等数据项。在排序时,如果用总成绩来排序,则会得到一个有序序列;如果以数据结构成绩进行排序,则会得到另一个有序序列。学生成绩表学号姓名计算机文化基础C语言数据结构总成绩04103101张三85928626304103102李四90919327404103103王五666364**********何六757473222………………作为排序依据的数据项称为“排序项”,也称为记录的关键码。关键码分为主关键码和次关键码。若关键码是主关键码,则对于任意待排序的序列,经排序后得到的结果是唯一的;若关键码是次关键码,排序的结果不一定唯一。它们之间的位置关系与排序前不一定保持一致。相同关键码值的记录之间的位置关系与排序前一致,则称此排序方法是稳定的;如果不一致,则称此排序方法是不稳定的注意:关键码与数据库中表中的域的关系,主关键码与主键的关系。一个记录的关键码序列为(31,2,15,7,91,7*)。若结果序列为(2,7,7*,15,31,91),则该排序方法是稳定的;若得到的结果序列为(1,7*,7,15,31,91),则这种排序方法是不稳定的。内部排序:记录全部存放在计算机的内存中,在内存中调整记录之间的相对位置,没有内、外存的数据交换。外部排序:记录的主要部分存放在外存中,借助于内存逐步调整记录之间的相对位置。不断地在内、外存之间交换数据。排序问题的记录采用线性结构。排序算法基本上是基于顺序表设计。:顺序地将待排序的记录按其关键码的大小插入到已排序的记录子序列的适当位置。子序列的记录个数从1开始逐渐增大,当子序列的记录个数与顺序表中的记录个数相同时排序完毕。注意:排序的范围由小到大。设顺序表sqList中有n个记录,初始时子序列中只有sqList[0]。第一次排序,比较sqList[0]和sqList[1]的大小,若sqList[0]≤sqList[1],说明序列已有序,否则将sqList[1]插入到sqList[0]的前面,这样子序列的大小增大为2。第二次排序时,比较sqList[2]和sqList[1]以确定是否需要把sqList[2]插入到sqList[1]之前。如果sqList[2]插入到sqList[1]之前,再比较sqList[2]和sqList[0]以确定是否需要把sqList[2]插入到sqList[0]之前。