待排序记录在内存中怎样存储和处理? ①顺序排序排序时直接移动记录 ②链表排序排序时只移动指针 ③地址排序排序时先移动地址,最后再移动记录 注:地址排序中可以增设一维数组来专门存放记录的地址
第 11 页 待排序记录在内存中怎样存储和处理？ ① 顺序排序——排序时直接移动记录； ② 链表排序——排序时只移动指针； ③ 地址排序——排序时先移动地址，最后再移动记录。 注：地址排序中可以增设一维数组来专门存放记录的地址
内部排序的方法 内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。 有序序列区元序序列区 经过一趟排序 有序序列区无序序列区
第 12 页 内部排序的方法 内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。 经过一趟排序 有序序列区 无 序 序 列 区 有序序列区 无 序 序 列 区
选择排序 从记录的无序子序列中“选择”关键字最小或最大的记录,并 将它加入到有序子序列中,以方法增加记录的有序子序列的长度。 【算法31】一趟选择排序的算法如下: void selectPass( SqList &L, int i) ∥已知Lr1.1中记录按关键字非递减有序,本算法实现第趟选择排序, ∥即在Lrn的记录中选出关键字最小的记录Lr和Lr[交换 RcdType W; ∥指示关键字最小记录的位置,初值设为i for(k=i+1; k<=L length; k++) if(Lrk]key< L.[]. key)j=k;∥暂不进行记录交换,只记录位置 if(il=j) 【W=Lr;Lr=Lr;Lr=W;}∥最后互换记录R]和R[ }∥ SelectPass
第 13 页 选择排序 从记录的无序子序列中“选择”关键字最小或最大的记录，并 将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。 【算法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
整个选择排序的过程是一趟选择排序过程的多次重复 融合 SelectPass。 【算法32】 void SelectSort (sqList &L) ∥对顺序表L作简单选择排序。 RcdType WE for(i=1;:i< L length;++)∥选择第i小的记录,并交换到位 for(k=+1;k<= L length;k++)∥在Lr[L. ength]中选择key最小的记录 if (L r[k]. key <L rO]. key)j=k; if(ij){W=L.r;L.r=L.r[;Lr=W;}∥与第个记录交换 ∥ Selectsort
第 14 页 【算法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 整个选择排序的过程是一趟选择排序过程的多次重复， 融合SelectPass
【例3-1】对下面一组关键字: 491386549276132752 进行选择排序,每趟排序之后的状况如下 初试关键字: 491386549276132752 (13)3865492764912752 i=2 (1327)65492764913852 (132738)492764916552 i=4 (132738492)764916552 i=5 (132738492491)766552 i=6 (13273849249152)6576 (1327384924915265)76
第 15 页 初试关键字： 491 38 65 492 76 13 27 52 i=1 （13） 38 65 492 76 491 27 52 i=2 （13 27）65 492 76 491 38 52 i=3 （13 27 38） 492 76 491 65 52 i=4 （13 27 38 492）76 491 65 52 i=5 （13 27 38 492 491）76 65 52 i=6 （13 27 38 492 491 52）65 76 i=7 （13 27 38 492 491 52 65 ）76 【例3-1 】对下面一组关键字： 491 38 65 492 76 13 27 52 进行选择排序，每趟排序之后的状况如下：