清华大学：《C++语言程序设计》课程教学资源（PPT课件）第十章 群体数据的组织

C++语言程序设计 第十章群体数据的组织 清华大学计算机与信息管理中心 郑莉

第十章 群体数据的组织 清华大学计算机与信息管理中心 郑 莉 C++语言程序设计

本章主要内容 插入排序 ●选择排序 交换排序 顺序查找 折半查找 休息

前一页 休息 2 本章主要内容 ⚫ 插入排序 ⚫ 选择排序 ⚫ 交换排序 ⚫ 顺序查找 ⚫ 折半查找

排序( sorting) ●排序是计算机程序设计中的一种重要操作,它 的功能是将一个数据元素的任意序列,重新排 列成一个按关键字有序的序列。 数据元素:数据的基本单位。在计算机中通常作为 个整体进行考虑。一个数据元素可由若干数据项 组成。 关键字:数据元素中某个数据项的值,用它可以标 识(识别)一个数据元素 在排序过程中需要完成两种基本操作: 比较两个数的大小 调整元素在数组中的位置 订一页休息 3

前一页 休息 3 排序（sorting） ⚫ 排序是计算机程序设计中的一种重要操作，它 的功能是将一个数据元素的任意序列，重新排 列成一个按关键字有序的序列。 – 数据元素：数据的基本单位。在计算机中通常作为 一个整体进行考虑。一个数据元素可由若干数据项 组成。 – 关键字：数据元素中某个数据项的值，用它可以标 识（识别）一个数据元素。 ⚫ 在排序过程中需要完成两种基本操作： – 比较两个数的大小 – 调整元素在数组中的位置

内部排序与外部排序 ●内部排序:待排序的数据元素存放在计算 机内存中进行的排序过程。 ●外部排序:待排序的数据元素数量很大, 以致内存存中一次不能容纳全部数据,在 排序过程中尚需对外存进行访问的排序过 程。 大斗 休息

前一页 休息 4 内部排序与外部排序 ⚫ 内部排序：待排序的数据元素存放在计算 机内存中进行的排序过程。 ⚫ 外部排序：待排序的数据元素数量很大， 以致内存存中一次不能容纳全部数据，在 排序过程中尚需对外存进行访问的排序过 程

内部排序方法 插入排序 ●选择排序 交换排序 休息

前一页 休息 5 内部排序方法 ⚫ 插入排序 ⚫ 选择排序 ⚫ 交换排序

括入排序的基本思想 每一步将一个待排序元素按其关键字值的大小插入到已排 序序列的适当位置上,直到待排序元素插入完为止 初始状态: [5]41020123 插入操作:1[4][45]1020123 [10][4510]20123 3[20][451020]123 4[12][4 10 220 5[3][3 510k1220 休息

前一页 休息 6 插入排序的基本思想 ⚫ 每一步将一个待排序元素按其关键字值的大小插入到已排 序序列的适当位置上，直到待排序元素插入完为止。 初始状态： [5] 4 10 20 12 3 插入操作： 1 [4] [4 5] 10 20 12 3 2 [10] [4 5 10] 20 12 3 3 [20] [4 5 10 20] 12 3 4 [12] [4 5 10 12 20] 3 5 [3] [3 4 5 10 12 20]

直接插入排序 在插入排序过程中,由于寻找插入位置的 方法不同又可以分为不同的插入排序法, 这里我们只介绍最简单的直接插入排序法。 例10.1直接插入排序函数模板(10-1h) 休息

前一页 休息 7 直接插入排序 ⚫ 在插入排序过程中，由于寻找插入位置的 方法不同又可以分为不同的插入排序法， 这里我们只介绍最简单的直接插入排序法。 ⚫ 例10.1 直接插入排序函数模板（10-1.h）

template void Insertion Sort(T Al, int n) i int i, j; T temp for(=1;i0&&temp≤A[-1]) A=A[-1 A的]=temp;

template void InsertionSort(T A[], int n) { int i, j; T temp; for (i = 1; i 0 && temp < A[j-1]) { A[j] = A[j-1]; j--; } A[j] = temp; } }

选择排序的基本思翘 每次从待排序序列中选择一个关键字最小的元素, 当需要按关键字升序排列时),顺序排在已排序序列的 最后,直至全部排完 初始状态: 4 020123] [41020125] 333 4[1020125] 5[201210] 第ⅰ次选择后,将选出的那个记录与第i个记录做交换。 体息

前一页 休息 9 选择排序的基本思想 每次从待排序序列中选择一个关键字最小的元素， （当需要按关键字升序排列时），顺序排在已排序序列的 最后，直至全部排完。 初始状态： [5 4 10 20 12 3] 3 [4 10 20 12 5] 3 4 [10 20 12 5] 第 i 次选择后，将选出的那个记录与第 i 个记录做交换。 3 4 5 [20 12 10] ...

直接选择排序 在选择类排序方法中,从待排序序列中选 择元素的方法不同,又分为不同的选择排 序方法,其中最简单的是通过顺序比较找 出待排序序列中的最小元素,称为直接选 择排序。 例10.2直接选择排序函数模板(10-2h) 休息

前一页 休息 10 直接选择排序 ⚫ 在选择类排序方法中，从待排序序列中选 择元素的方法不同，又分为不同的选择排 序方法，其中最简单的是通过顺序比较找 出待排序序列中的最小元素，称为直接选 择排序。 ⚫ 例10.2 直接选择排序函数模板（10-2.h）