>本节内容说明 ●内容:选择排序、多关键字排序 要求:掌握简单选择排序的基本思想及算法实 现,并了解该排序算法的性能;通过多 关键字排序问题进一步提高利用排序算 法解决实际问题的能力。 重点:简单选择排序的基本思想及算法实回一 计算机解决多关键字排序中应注意 问题。 ●难点:多关键字排序的具体实现
➢ 本节内容说明 ⚫ 内容：选择排序、多关键字排序 ⚫ 要求：掌握简单选择排序的基本思想及算法实 现，并了解该排序算法的性能；通过多 关键字排序问题进一步提高利用排序算 法解决实际问题的能力。 ⚫ 重点：简单选择排序的基本思想及算法实现； 计算机解决多关键字排序中应注意的 问题。 ⚫ 难点：多关键字排序的具体实现
4.7简单选择排序 基本思想: 第一趟排序在所有待排序的n个记录中选出 关键字最小的记录,将它与数据表中的第一个 记录交换位置,使关键字最小的记录处于数据 表的最前端;第二趟在剩下的n1个记录中再选 出关键字最小的记录,将其与数据表中的第二 个记录交换位置;重复这样的操作,排序共进 行n-1趟,最终可实现数据表的升序排列
4.7 简单选择排序 第一趟排序在所有待排序的n个记录中选出 关键字最小的记录，将它与数据表中的第一个 记录交换位置，使关键字最小的记录处于数据 表的最前端；第二趟在剩下的n-1个记录中再选 出关键字最小的记录，将其与数据表中的第二 个记录交换位置；重复这样的操作，排序共进 行n-1趟，最终可实现数据表的升序排列。 一. 基本思想：
第i趟循环,在 clist-lst叫范围内选择关 键字最小的元素,将其与is进行交换 初始状态38204638749112 第1趟12204638749138 第2趟12 46749138 第3趟12220本身就是749138 第4趟12 最小的 兼涤操兼米 第5趟12203838 第6趟12203838467491
⚫ 选择排序过程示例---以升序为例 初始状态 38 20 46 38 74 91 12 第1趟 12 20 46 38 74 91 38 第2趟 12 20 46 38 74 91 38 第3趟 12 20 38 46 74 91 38 第4趟 12 20 38 38 74 91 46 第5趟 12 20 38 38 46 91 74 第6趟 12 20 38 38 46 74 91 20本身就是 最小的 • 第i趟循环，在list[i]~list[n]范围内选择关 键字最小的元素，将其与list[i]进行交换
二.算法描述 第i趟执行的操作 k=i;/k用于记下最小元素的下标* for〔j=|+1j<=nj++) 在待排序范围内寻找关键字最小的记录* if(listO]. key<list[k]. key)=j; if(kl=i) [temp=list[i] list(=list[kI; 兼涤操兼米 list[k=temp:
二．算法描述 k=i; /*k用于记下最小元素的下标*/ for (j=i+1;j<=n;j++) /*在待排序范围内寻找关键字最小的记录*/ if(list[j].key<list[k].key) k=j; if(k!=i) {temp=list[i]; list[i]=list[k]; list[k]=temp; } 第i趟执行的操作
下面的简单选择排序实现将一个长度为n的线性表r 上的所有元素按关键字升序排列。 void selectsort(ElemType listI, int n) tint i,j, k; Elem Type tem p for(i=1;i<=n-1;}++)/外循环控制排序的总趟数* 【k=;/k用于记下最小元素的下标啊 for (=i+1; j<=n;j++ 在待排序范围内寻找关键字最小的记录* if(listo]. key<list[k]. key) k=j if(k=i i temp=list[ list[=list[k] listk]temp 3/selectsort*/
下面的简单选择排序实现将一个长度为n的线性表r 上的所有元素按关键字升序排列。 { k=i; /*k用于记下最小元素的下标*/ for (j=i+1;j<=n;j++) /*在待排序范围内寻找关键字最小的记录*/ if(list[j].key<list[k].key) k=j; if(k!=i) { temp=list[i]; list[i]=list[k]; list[k]=temp; } } for(i=1;i<=n-1;i++) /*外循环控制排序的总趟数*/ void selectsort(ElemType list[],int n) {int i,j,k; ElemType temp; } /*selectsort*/
三.算法分析 稳定性:不稳定的 ●时间复杂度:O(m2) ●与初始状态无关
三. 算法分析 ⚫ 稳定性: 不稳定的 • 时间复杂度: Ｏ(n2 ) • 与初始状态无关
知识回顾的线性表按关键字值升序排列 思考? void sort (ElemType listI, int n) Rint i,j; ElemType t; 此排序算法应属于 for(i=l; i<n; i++) 哪种排序方法? forli=i+1:j<=n:j++) if(listj. key<list i key) 与刚刚介绍的选择 tt=list[i]; 排序算法相比,两 list=list[j; 个算法有何不同之 list[j=ts 处?哪个算法的效 率更高?
• 知识回顾 void sort(ElemType list[],int n) {int i,j; ElemType t; for(i=1;i<n;i++) for(j=i+1;j<=n;j++) if(list[j].key<list[i].key) {t=list[i]; list[i]=list[j]; list[j]=t; } } 下面的排序算法实现将表长为n 的线性表按关键字值升序排列。 思考? 此排序算法应属于 哪种排序方法？ 与刚刚介绍的选择 排序算法相比，两 个算法有何不同之 处？哪个算法的效 率更高？