选择排序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