文档介绍：插入排序和快速排序
学****目标
了解排序的定义
了解内排序和外排序的基本概念
掌握插入排序和快速排序
掌握他们在最坏、最好、平均情况下的时间复杂度
能够判断排序算法是否稳定
重点和难点
重点如下:
插入排序
快速排序
难点如下:
快速排序
排序算法的时间复杂度
什么是排序
简单说,排序是将无序的记录序列调整为有序记录序列的一种操作
内部排序与外部排序
内部排序: 指的是待排序记录存放在计算机随机存储器中进行的排序过程。
外部排序: 指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程。
排序的分类
按排序过程依据的不同原则进行分类:
插入排序、
交换排序、
选择排序、
归并排序和
基数排序
排序的时间复杂性
排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性是算法执行中的数据比较次数及数据移动次数来衡量。
稳定排序与不稳定排序
假设 Ki = Kj ,且排序前序列中 Ri 领先于 Rj ;
若在排序后的序列中 Ri 仍领先于 Rj ,则称排序方法是稳定的。
若在排序后的序列中 Rj 可能领先于 Ri ,则称排序方法是不稳定的。
例,序列 3 15 8 8 6 9
若排序后得 3 6 8 8 9 15
稳定的
若排序后得 3 6 8 8 9 15
不稳定的
插入排序——直接插入排序
13 27 38 49 65 76 97
插入 49
例,序列 13 27 38 65 76 97
思想: 利用有序表的插入操作进行排序
有序表的插入: 将一个记录插入到已排好序的有序表中,从而得到一个新的有序表。
直接插入排序算法描述
直接插入排序算法主要应用比较和移动两种操作。
{ 13 27 38 49 65 76 97 }
初始,S = { 49 } ;
例,序列 49 38 65 97 76 13 27
直至最后一个元素;
初始,令第 1 个元素作为初始有序表;
依次插入第 2 , 3 , …, k 个元素构造新的有序表;