第3章排序 计算机教研宦 第1页 2021/2/19
Data Structure 数据结构—— 第3章排序 胡建华 2021/2/19 计算机教研室 第 1 页 第 3 章 排序
◎31排序的基本概念 排序是计算机内经常进行的一种操作,其目的 是将一组“无序”的记录序列调整为“有序” 的记录序列。 例如:将下列关键字序列 52,49,80,36,14,58,61,23,97,75 调整为 14,23,36,49,52,58,61,75,80,97 计算机教研宦 第2页 2021/2/19
Data Structure 数 据 结 构—— 第 3 章 排 序 胡建华 2021/2/19 计算机教研室 第2页 3.1 排序的基本概念 • 排序是计算机内经常进行的一种操作，其目的 是将一组“无序”的记录序列调整为“有序” 的记录序列。 例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97
◎31排序的基本概念 般情况下,假设含n个记录的序列为 R31,R2 其相应的关键字序列为 e K1,K2 K n 这些关键字相互之间可以进行比较,即在它们之间 存在着这样一个关系: Kn1≤K≤≤K p pn 按此固有关系将上式记录序列重新排列为 1,1p2 p 的操作称作排序。 计算机教研宦 第3页 2021/2/19
Data Structure 数 据 结 构—— 第 3 章 排 序 胡建华 2021/2/19 计算机教研室 第3页 3.1 排序的基本概念 一般情况下，假设含n个记录的序列为 { R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn } 这些关键字相互之间可以进行比较，即在它们之间 存在着这样一个关系 ： Kp1≤Kp2≤…≤Kpn 按此固有关系将上式记录序列重新排列为 { Rp1, Rp2, …，Rpn } 的操作称作排序
@C语言描述 #define MAXSIZE 1000 //待排顺序表最大长度 typedef int Key Type //关键字类型为整数类型 /*水冰*米米**冰*米*米水冰*米水**冰水*水*米冰水*/ typedef struct f KeyType key: //关键字项 InfoType otherinfo //其它数据项 的} RetYpe; //记录类型 /**水冰*米水*冰*米米水*冰*冰水*水****水*/ t ypedef struct RcdType r[MAXSIZE+1];//r[0]闲置 int length //顺序表长度 6 SqList //顺序表类型 计算机教研宦 第4页 2021/2/19
Data Structure 数 据 结 构—— 第 3 章 排 序 胡建华 2021/2/19 计算机教研室 第4页 C语言描述 #define MAXSIZE 1000 // 待排顺序表最大长度 typedef int KeyType; // 关键字类型为整数类型 /***********************************************/ typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项 } RcdType; // 记录类型 /***********************************************/ typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置 int length; // 顺序表长度 } SqList; // 顺序表类型
◎31排序的基本概念 内部排序 若整个排序过程不需要访问外存便能完成,则称 此类排序问题为内部排序; 外部排序 反之,若参加排序的记录数量很大,整个序列的 排序过程不可能在内存中完成,则称此类排序问题为 外部排序。 计算机教研宦 第5页 2021/2/19
Data Structure 数 据 结 构—— 第 3 章 排 序 胡建华 2021/2/19 计算机教研室 第5页 3.1 排序的基本概念 • 内部排序 若整个排序过程不需要访问外存便能完成，则称 此类排序问题为内部排序； • 外部排序 反之，若参加排序的记录数量很大，整个序列的 排序过程不可能在内存中完成，则称此类排序问题为 外部排序
◎31排序的基本概念 内部排序的过程是一个逐步扩大记录的有序序列长度 的过程。 有序序列区无序序列区 经过一趟排序 有序序列区无序序列区 计算机教研宦 第6页 2021/2/19
Data Structure 数 据 结 构—— 第 3 章 排 序 胡建华 2021/2/19 计算机教研室 第6页 3.1 排序的基本概念 • 内部排序的过程是一个逐步扩大记录的有序序列长度 的过程。 经过一趟排序 有序序列区 无 序 序 列 区 有序序列区 无 序 序 列 区
◎选择排序( select sort) 8有序序列R[1i1无序序列R[in R RII 有序序列R 无序序列R+1.n 计算机教研宦 第7页 2021/2/19
Data Structure 数 据 结 构—— 第 3 章 排 序 胡建华 2021/2/19 计算机教研室 第7页 选择排序（select sort) 有序序列R[1..i] 无序序列 R[i+1..n] 有序序列R[1..i-1] 无序序列 R[i..n] R[i] R[j]
@算法31 o void SelectPass( SqList &L, int i)t ∥已知L.r[1.-1中记录按关键字非递减有序,本算法实现第i趟 ∥选择排序,即在Lr[i.n]的记录中选出关键字最小的记录L.r ∥和L.r交换 RcdType W; j=i;∥j指示关键字最小记录的位置,初值设为 for(k=i+1; k<=L length; k++) if (L r[k]. key <L r[]. key)j=k; ∥暂不进行记录交换,只记录位置 if (i l=j)IW=L rD]: LrD=L r[: Lr[=W; y ∥最后互换记录R和R[ }∥ SelectPass 研室 第8页 2021/2/19
Data Structure 数 据 结 构—— 第 3 章 排 序 胡建华 2021/2/19 计算机教研室 第8页 算法 3.1 void SelectPass( SqList &L, int i ) { // 已知L.r[1..i-1]中记录按关键字非递减有序，本算法实现第 i 趟 //选择排序，即在L.r[i..n]的记录中选出关键字最小的记录L.r[j] //和L.r[i]交换 RcdType W； j = i； // j 指示关键字最小记录的位置，初值设为I for ( k=i+1; k<=L.length; k++ ) if ( L.r[k].key < L.r[j].key ) j = k ； // 暂不进行记录交换，只记录位置 if ( i != j ) { W=L.r[j]；L.r[j] =L.r[i]；L.r[i] = W；} // 最后互换记录R[j] 和R[i] } // SelectPass
@算法32 o void SelectSort(SqList &L) ∥对顺序表L作简单选择排序。 RcdType W; for(i=1;i<= L length;++i){∥选择第i的记录,并交换到位 for( k=i+1; k<=L length; k++) ∥在L.r[i. L length]中选择key最小的记录 if(Lr[k]. key <Lrf]. key)j=k; if (iFj [WEL rD]: Lr[]=L r[]: Lr[=W; 3 ∥与第个记录交换} }∥ Selectsort 研室 第9页 2021/2/19
Data Structure 数 据 结 构—— 第 3 章 排 序 胡建华 2021/2/19 计算机教研室 第9页 算法 3.2 void SelectSort (SqList &L) { // 对顺序表L作简单选择排序。 RcdType W； for (i=1; i<=L.length;++i ){ // 选择第i小的记录，并交换到位 j=i; for ( k=i+1; k<=L.length; k++ ) // 在L.r[i..L.length]中选择key最小的记录 if ( L.r[k].key < L.r[j].key ) j =k ； if ( i!=j ) { W=L.r[j]；L.r[j] =L.r[i]；L.r[i] = W；} // 与第i个记录交换 } } // SelectSort
@内部排序过程中主要进行下列两种基本操作 1.比较两个关键字的大小 2.将元素从一个位置移动到另一个位置。 毁内部排序按时间复杂度来划分可分为: 1.简单排序方法0(n2) 2.先进排序方法0( nlogn) 3.基数排序(d*n) 计算机教研宦 第10页 2021/2/19
Data Structure 数 据 结 构—— 第 3 章 排 序 胡建华 2021/2/19 计算机教研室 第10页 内部排序过程中主要进行下列两种基本操作: 1.比较两个关键字的大小 2.将元素从一个位置移动到另一个位置。 内部排序按时间复杂度来划分可分为： 1. 简单排序方法O（n 2） 2. 先进排序方法O（nlogn） 3. 基数排序（d*n）