
选择排序10.4基本思路无序区全局有序区选出最小记录R[k]主要的选择排序方法:(1)简单选择排序(2)堆排序1/36
主要的选择排序方法: 全局有序区 无序区 选出最小记录R[k] 1/36

简单选择排序10.4.1排序思路1.E从一个无序区中选出最小的元素,最简单方法是逐个进行元素比较,例如,从无序区R[i..n-1]中选出最小元素R[minj]。//minj先置为区间中的首元素序号int minj=i;for(intj=i+l;j<n;j++)/从R[i..n-1]中选最小元素的R[minj]//与区间中其他元素比较if (R[j].key<R[minj].key)minj=j;简单选择2/36
1. 排序思路 从一个无序区中选出最小的元素,最简单方法是逐个进行元素比较,例 如,从无序区R[i.n-1]中选出最小元素R[minj]。 int minj=i; //minj先置为区间中的首元素序号 for (int j=i+1;j<n;j++) //从R[i.n-1]中选最小元素的R[minj] if (R[j].key<R[minj].key) //与区间中其他元素比较 minj=j; 简单选择 2/36

示例)次。有2n个整数,找到其中最大整数需要比较次数最少是(C.n?A.nB.1og2nD.2nE.2n-1F.n-1容我思考思考3/36
有2 n个整数,找到其中最大整数需要比较次数最少是( )次。 A.n B.log2n C.n 2 D.2n E.2n-1 F.n-1 示例 3/36

无序区全局有序区R[0]R[i-1]R[i]R[n-1]............采用简单选择方法选出最小元素R[0]R[i+1]R[n-1]R[i-1] R[i].....无序区全局有序区初始时,全局有序区为空i=0~n-2,共经过n-1排序4/36
全局有序区 R[0] . R[i-1] 无序区 R[i] . R[n-1] 全局有序区 R[0] . R[i-1] R[i] 无序区 R[i+1] . R[n-1] 采用简单选择方法选出最小元素 初始时,全局有序区为空 i=0~n-2,共经过n-1趟排序 4/36

2.排序算法public void SelectSort()//对R[0..n-1]元素进行简单选择排序RecType tmp;//做第i趟排序for (int i=o;i<n-1;i++) int minj=i;for (intj=i+l;j<n;j++)//无序区R[i..n-1]中选最小元素R[minj]if (R[j].key<R[minj].key)minj=j;if (minj!=i)//R[minj]不是无序区首元素swap(i,minj);//交换R[i]和R[min]]775/36
2. 排序算法 public void SelectSort() //对R[0.n-1]元素进行简单选择排序 { RecType tmp; for (int i=0;i<n-1;i++) //做第i趟排序 { int minj=i; for (int j=i+1;j<n;j++) //无序区R[i.n-1]中选最小元素R[minj] if (R[j].key<R[minj].key) minj=j; if (minj!=i) //R[minj]不是无序区首元素 swap(i,minj); //交换R[i]和R[minj] } } 5/36

【例10.6】设待排序的表有10个元素,其关键字分别为(6,8,7,9,0,1,3,2,4,5)。说明采用简单选择排序方法进行排序的过程。初始关键字[16i=0的结果:0=1的结果:i=2的结果:2i=3的结果:3i=4的结果:i=5的结果:Ri=6的结果:86=7的结果:8V=8的结果:6/36
【例10.6】 设待排序的表有10个元素,其关键字分别为(6,8,7,9, 0,1,3,2,4,5)。说明采用简单选择排序方法进行排序的过程。 初始关键字 []6 8 7 9 0 1 3 2 4 5 i=0的结果: [0] 8 7 9 6 1 3 2 4 5 i=1的结果: [0 1] 7 9 6 8 3 2 4 5 i=2的结果: [0 1 2] 9 6 8 3 7 4 5 i=3的结果: [0 1 2 3] 6 8 9 7 4 5 i=4的结果: [0 1 2 3 4] 8 9 7 6 5 i=5的结果: [0 1 2 3 4 5] 9 7 6 8 i=6的结果: [0 1 2 3 4 5 6] 7 9 8 i=7的结果: [0 1 2 3 4 5 6 7] 9 8 i=8的结果: [0 1 2 3 4 5 6 7 8] 9 6/36

select sort7/36
7/36

3.算法分析无论初始数据序列的状态如何,在第趟排序中选出最小元素,内for循环需做n-1-(i+1)+1=n-i-1次比较,因此,总的比较次数为n-n(n-1)= 0(n2)C(n) =(n-i-1)=2i=08/36
3. 算法分析 无论初始数据序列的状态如何,在第i趟排序中选出最小元素,内for循 环需做n-1-(i+1)+1=n-i-1次比较,因此,总的比较次数为 8/36

元素的移动次数当初始数据序列正序时,移动次数为0。反序时每排序均要执行交换操作,此时总的移动次数为最大值3(n-1)。最好、最坏和平均情况的时间复杂度均为0(n2)。9/36
元素的移动次数 当初始数据序列正序时,移动次数为0。 反序时每趟排序均要执行交换操作,此时总的移动次数为最大值 3(n-1)。 最好、最坏和平均情况的时间复杂度均为O(n 2)。 9/36

是一种不稳定的排序方法交换(5,1)5.无序区(1,5,5)10/36
是一种不稳定的排序方法 (5, 5, 1) 无序区 交换 (1, 5, 5) 10/36