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