NOI排序算法课程胶片

1、排序 1. 冒泡排序 2. 快速排序 3. 直接插入排序 4. 希尔排序 5. 选择排序 6. 小结 冒泡排序算法描述 设待排序记录序列中的记录个数为n 一般地，第i趟起泡排序从1到n-i+1 依次比较相邻两个记录的关键字，如果发生逆序，则交 换之 其结果是这n-i+1个记录中，关键字最大的记录被交换 到第n-i+1的位置上，最多作n-1趟。 算法示例1 0 1 2 3 4 5 算法示例2 0 1 2 3 4 5 总体演示 初始 关键 字 第一 趟排 序 第四 趟排 序 第二 趟排 序 第三 趟排 序 第五 趟排 序 算法实现 输入n 个数给a1 到 an for j=1 to n-1 for

2、 i=1 to n-j aiai+1 真假 aiai+1 输出a1 到 an #include main() int a11,i,j,t; printf(Input 10 numbers:n); for(i=1;i11;i+) scanf(%d, printf(n); for(j=1;j=9;j+) for(i=1;iai+1) t=ai; ai=ai+1; ai+1=t; printf(The sorted numbers:n); for(i=1;i11;i+) printf(%d ,ai); 1. 冒泡排序 2. 快速排序 3. 直接插入排序 4. 希尔排序 5. 选择排序 6. 小结 快

3、速排序 快速排序是通过比较关键码、交换记录， 以某个记录为界(该记录称为支点)，将待排序列分成 两部分 一部分所有记录的关键码大于等于支点记录的关键码 另一部分所有记录的关键码小于支点记录的关键码 算法描述 任取待排序记录序列中的某个记录(例如取第一个记录)作为基准(枢),按照该记 录的关键字大小,将整个记录序列划分为左右两个子序列 左侧子序列中所有记录的关键字都小于或等于基准记录的关键字 右侧子序列中所有记录的关键字都大于基准记录的关键字 基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。 然后分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置 上为止。 基准记录

4、也称为枢轴（或支点）记录。 取序列第一个记录为枢轴记录，其关键字为Pivotkey 指针low指向序列第一个记录位置 指针high指向序列最后一个记录位置 算法示例1 始关键字pivotkey 一次交换 二次交换 三次交换 high-1 完成一趟排序 lowhigh low low low low low high high high high high 算法示例2 12 完成一趟排序 分别进行快速排序 有序序列 算法分析 快速排序是一个递归过程; 利用序列第一个记录作为基准，将整个序列划分为左右两 个子序列。只要是关键字小于基准记录关键字的记录都移 到序列左侧； 快速排序的趟数取决于递归树的

5、高度。 如果每次划分对一个记录定位后, 该记录的左侧子序列与 右侧子序列的长度相同, 则下一步将是对两个长度减半的 子序列进行排序, 这是最理想的情况 13 1. 冒泡排序 2. 快速排序 3. 直接插入排序 4. 希尔排序 5. 选择排序 6. 小结 直接插入排序 算法描述： 记录存放在数组R0.n-1中，排序过程的某一中间时刻，R被划分 成两个子区间R0i-1和Ri.n-1，其中：前一个子区间是已排好 序的有序区；后一个子区间则是当前未排序的部分。 基本操作 将当前无序区的第1个记录Ri插入到有序区R0.i-1中适当的位置 ，使R0i变为新的有序区 直接插入排序 操作细节： 当插入第i(i

6、1)个对象时, 前面的r0, r1, , ri-1已经排 好序。 用ri的关键字与ri-1, ri-2, 的关键字顺序进行比较(和顺 序查找类似)，如果小于，则将rx向后移动(插入位置后的记录向 后顺移) 找到插入位置即将ri插入 直接插入排序 实用例子： 已知待序的一组记录的初始排列为：21, 25, 49, 25*, 16, 08 0 1 2 3 4 5 算法示例 0 1 2 3 4 5 temp 25 0 1 2 3 4 5 temp 49 25* 0 1 2 3 4 5 算法示例 0 1 2 3 4 5 temp 16 0 1 2 3 4 5 temp 08 0 1 2 3 4 5 完

7、成 算法实现 void InsertSort (int r , int n ) / 假设关键字为整型，放在向量r中 int i, j, temp; for (i = 1;i0;j- -) /从后向前顺序比较，并依次后移 if ( temp rj-1 ) rj = rj-1; else break; rj = temp; 算法分析 关键字比较次数和记录移动次数与记录关键字的初始排 列有关。 最好情况下, 排序前记录已按关键字从小到大有序, 每趟 只需与前面有序记录序列的最后一个记录比较1次, 移动 2次记录, 总的关键字比较次数为 n-1, 记录移动次数为 2(n-1)在平均情况下的关键字比较次

8、数和记录移动次数 约为 n2/4。 直接插入排序是一种稳定的排序方法 直接插入排序最大的优点是简单，在记录数较少时，是 比较好的办法 1. 冒泡排序 2. 快速排序 3. 直接插入排序 4. 希尔排序 5. 选择排序 6. 小结 希尔排序 希尔排序又称缩小增量排序 是1959年由D.L.Shell提出来的 算法描述 首先取一个整数 gap n(待排序记录数) 作为间隔, 将全部记录分为 gap 个子序列, 所有距离为 gap 的记录放在同一个子序列中 在每一个子序列中分别施行直接插入排序。 然后缩小间隔 gap, 例如取 gap = gap/2 重复上述的子序列划分和排序工作，直到最后取gap

9、 = 1, 将所有记录放在同 一个序列中排序为止。 算法示例 已知待排序的一组记录的初始排列为：21, 25, 49, 25*, 16, 08 0 1 2 3 4 5 算法示例 t 3 0 1 2 3 4 5 0 1 2 3 4 5 t 2 t 1 算法分析 开始时 gap 的值较大, 子序列中的记录较少, 排序速度 较快 随着排序进展, gap 值逐渐变小, 子序列中记录个数逐 渐变多,由于前面大多数记录已基本有序, 所以排序速 度仍然很快 Gap的取法有多种。 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。 1. 冒泡排序 2. 快速排序 3. 直接插

10、入排序 4. 希尔排序 5. 选择排序 6. 小结 排序过程 首先通过n-1次比较，从n个数中找出最小的， 将它 与第一个数 交换第一趟选择排序，结果最小的数被安置在第 一个元素位置上 再通过n-2次比较，从剩余的n-1个数中找出关键字 次小的记录， 将它与第二个数交换第二趟选择排序 重复上述过程，共经过n-1趟排序后，排序结束 排序示例 初始：初始： 49 38 65 97 76 13 27 k j i=1 1349 一趟：一趟： 13 38 65 97 76 49 27 i=22738 二趟：二趟： 13 27 65 97 76 49 38 三趟：三趟： 13 27 38 97 76 49

11、 65 四趟：四趟： 13 27 38 49 76 97 65 五趟：五趟： 13 27 38 49 65 97 76 六趟：六趟： 13 27 38 49 65 76 97 k k k k jj jj j jjj j j 算法示例 0 1 2 3 4 5 算法示例 0 1 2 3 4 5 最小者 最小者 各趟排序后的结果 算法示例 0 1 2 3 4 5 i =2时选择排序的过程 i k j i k j i k j 算法示例 0 1 2 3 4 5 i k j 算法实现 输入n 个数给a1 到 an for i=1 to n-1 for j=i+1 to n ajak 真假 k=j 输出a1

12、 到 an k=i aiak i != k 真假 #include main() int a11,i,j,k,x; printf(Input 10 numbers:n); for(i=1;i11;i+) scanf(%d, printf(n); for(i=1;i10;i+) k=i; for(j=i+1;j=10;j+) if(ajak) k=j; if(i!=k) x=ai; ai=ak; ak=x; printf(The sorted numbers:n); for(i=1;i11;i+) printf(%d ,ai); 1. 冒泡排序 2. 快速排序 3. 直接插入排序 4. 希尔排序

13、 5. 选择排序 6. 小结 36 基本概念 排序排序（Sorting）： 简单地说，排序就是把一组记录一组记录按照某个（或某几个）字段的值以 递增（由小到大）或递减（由大到小）的次序重新排列的过程。（如按 年龄从小到大排序） 学号姓名年龄性别 2004001张佳18男 2004002王鹏19男 2004003刘宁17女 2004004李娟18女 2004005陈涛19男 2004006李小燕18女 37 作为比较基础的一个(或多个)字段，称为排序码排序码。排序码可以是数 值、符号或符号串。 排序码排序码不一定是关键码，是关键码，关键码可以作为排序码。关键码是唯一的， 但排序码不一定唯一。排序

14、码不唯一时，排序的结果可能不唯一。 参与排序的对象，称为记录。一个记录可以包含多个字段。 如果记录集合中存在多个排序码排序码相同的记录，经过排序后，排序码排序码 相同的记录的前后次序保持不变，则这种排序方法称为是稳定稳定的， 否则是不稳定不稳定的。 排序码 与 关键码（primary key） 38 排序方法可以分为五种 插入插入排序、选择选择排序、交换交换 排序、分配分配排序和归并归并排序。 在排序过程中，全部记录存放在内存，则称为内排序内排序， 如果排序过程中需要使用外存，则称为外排序。外排序。 排序的类型 评价排序算法好坏的标准 执行算法所需的时间 执行算法所需要的附加空间 算法本身的复杂程度也是考虑的一个因素 排序的时间开销时间开销是算法好坏的最重要的标志 排序的时间开销衡量标准: 算法执行中的比较次数（必须）。 算法执行中的移动次数（有可能避免）。 通常会关注最坏情况和平均情况的开销。 排序算法的评价 39 阶段小节 几