河池学院：《数据结构》课程电子教案（PPT教学课件）第10章 排序 10.4 选择排序

主要的选择排序方法： 全局有序区 无序区 选出最小记录R[k] 1/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

有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[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; 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）。说明采用简单选择排序方法进行排序的过程。 初始关键字 []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

7/36

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

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

是一种不稳定的排序方法 （5， 5， 1） 无序区 交换 （1， 5， 5） 10/36