天津大学：《数据结构 Data Structures》课程教学资源（PPT课件讲稿）第十章 排序

第十章内部排序 令概迷 令插入排序 快速排序 令选择排序 令归并排序 基数排序 令各种内排方法比较

❖概述 ❖插入排序 ❖快速排序 ❖选择排序 ❖归并排序 ❖基数排序 ❖各种内排方法比较 第十章内部排序

概迷 排序:将一个数据元素的任意序列,重新 排列成一个按关键字有序的序列。 数据表( datalist):它是待排序数据对象的 有限集合。 主关键字(key):数据对象有多个属性域 即多个数据成员组成,其中有一个属性域可用 来区分对象,作为排序依据,称为关键字。也 称为排序码

概 述 ◼ 排序：将一个数据元素的任意序列，重新 排列成一个按关键字有序的序列。 ◼ 数据表(datalist): 它是待排序数据对象的 有限集合。 ◼ 主关键字(key): 数据对象有多个属性域, 即多个数据成员组成, 其中有一个属性域可用 来区分对象, 作为排序依据，称为关键字。也 称为排序码

排序方法的稳定性:如果在对象序列中有两 个对象r和rj它们的排序码k[i==klil, 且在排序之前,对象r排在r前面。如果在 排序之后,对象r仍在对象rj的前面,则称 这个排序方法是稳定的,否则称这个排序方法 是不稳定的 内排序与外排序:内排序是指在排序期间 数据对象全部存放在内存的排序;外排序是 指在排序期间全部对象个数太多,不能同时 存放在内存,必须根据排序过程的要求,不 断在内、外存之间移动的排序

◼ 排序方法的稳定性: 如果在对象序列中有两 个对象r[i]和r[j], 它们的排序码 k[i] == k[j], 且在排序之前, 对象r[i]排在r[j]前面。如果在 排序之后, 对象r[i]仍在对象r[j]的前面, 则称 这个排序方法是稳定的, 否则称这个排序方法 是不稳定的。 ◼ 内排序与外排序: 内排序是指在排序期间 数据对象全部存放在内存的排序；外排序是 指在排序期间全部对象个数太多，不能同时 存放在内存，必须根据排序过程的要求，不 断在内、外存之间移动的排序

排序的时间开销:排序的时间开销是 衡量算法好坏的最重要的标志。排序的 时间开销可用算法执行中的数据比较次 数与数据移动次数来衡量

◼ 排序的时间开销: 排序的时间开销是 衡量算法好坏的最重要的标志。排序的 时间开销可用算法执行中的数据比较次 数与数据移动次数来衡量

内排序分类 依不同原则 插入排序、交换排序、选择排序、归 并排序、和计数排序等 依所须工作量 简单排序-时间复杂度0m2) 先进排序方法时间复杂度 o(n logn) 基数排序-时间复杂度odn)

内排序分类 • 依不同原则 插入排序、交换排序、选择排序、归 并排序、和计数排序等。 • 依所须工作量 简单排序---时间复杂度o(n2) 先进排序方法---时间复杂度o(n logn) 基数排序---时间复杂度o(d.n)

插入排序( nsert sorting) 基本思想每步将一个待排序的对象,按其排 序码大小,插入到前面已经排好序的一组对象 的适当位置上,直到对象全部插入为止。 直接插入排序( Insert Sort 基本思想当插入第i(i≥1)个对象时,前面的 V0,V1l,…,v[i-1|经排好序。这时用 V[i的排序码与vi1,Vi-2l,…的排序码顺 序进行比较,找到插入位置即将Ⅴ插入原 来位置上的对象向后顺移

插入排序 (Insert Sorting) ◼ 基本思想 当插入第i (i  1) 个对象时, 前面的 V[0], V[1], …, V[i-1]已经排好序。这时, 用 V[i]的排序码与V[i-1], V[i-2], …的排序码顺 序进行比较, 找到插入位置即将V[i]插入, 原 来位置上的对象向后顺移。 基本思想 每步将一个待排序的对象, 按其排 序码大小, 插入到前面已经排好序的一组对象 的适当位置上, 直到对象全部插入为止。 直接插入排序 (Insert Sort)

直接插入排序过程 234 5 temp 9的@9 2 5 temp 21 08 25)(49 的5 08 i=2②②O6 08 分6的 08 i=32因06@6 08

直接插入排序过程 i = 1 0 1 2 3 4 5 temp i = 2 0 1 2 3 4 5 temp 21 25 49 25* 16 08 21 25 49 25* 16 08 25 21 25 49 25* 16 08 21 25 49 25* 16 08 49 21 25 49 25* 16 08 i = 3 21 25 49 25* 16 08 25* 21 25 25* 49 16 08

25)(25 i=4 ②229 16 25)25(49 i=5 08 四(2)(9

i = 4 i = 5 21 25 25* 49 16 08 16 16 21 25 25* 49 08 16 21 25 25* 49 08 08 16 21 25 25* 49 08

直接插入排序的算法 typedef int SortData; void Insertsort( SortData vIl, intn)t /按非递减顺序对表进行排序 SortData temp; int i, j; for(i=l; i0;j-)从后向前顺序比较 if temp<Vj-l)vl=v[j-1; else breaks V=temp

直接插入排序的算法 typedef int SortData; void InsertSort ( SortData V[ ], int n ) { //按非递减顺序对表进行排序 SortData temp; int i, j; for ( i = 1; i 0; j-- ) //从后向前顺序比较 if ( temp < V[j-1] ) V[j] = V[j-1]; else break; V[j] = temp; } }

算法分析 设待排序对象个数为n,则该算法的主程序执行 趟。 排序码比较次数和对象移动次数与对象排序码的 初始排列有关。 最好情况下,排序前对象已按排序码从小到大有 序,每趟只需与前面有序对象序列的最后一个对 象比较次,移动2次对象,总的排序码比较次数 为n-1,对象移动次数为2(n-1)

算法分析 ◼ 设待排序对象个数为 n, 则该算法的主程序执行 n-1趟。 ◼ 排序码比较次数和对象移动次数与对象排序码的 初始排列有关。 ◼ 最好情况下, 排序前对象已按排序码从小到大有 序, 每趟只需与前面有序对象序列的最后一个对 象比较1次, 移动2次对象, 总的排序 码比较次数 为 n-1, 对象移动次数为 2(n-1)