◎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）