3478 34322964 7.23直接选择排序 78453432296 ■算法思想 =11229 4534323464 找出剩下的未排序记录中的最小 12293 464 记录,然后直接与数组中第个记 录交换,比冒泡排序减少了移动 1=312293234g74564 次数 1229323437564 1229323434586 举位▲张倍墙写 229323434 template <dass Record, class Compare Void Straightselectsorter<Record, Compare>: 直接选择排序 Sort(Record Array ll, int n) 依次选出第小的记录,即剩余记录中最小的那个 template <class record, class for(int i=0; i<n-1; i++)t 首先假设记录就是最小的 Compare> class Straightselectsorter:public /开始向后扫描所有剩余记录 Sorter<Record Compare> ∥/如果发现更小的记录,记录它的位置 /直接选择排序类 public void Sort(Record Array[],int n); 将第小的记录放在数组中第个位置 swap(Array, i, Smallest) 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 724简单排序算法的时间代 算法分析 价对比 ■不稳定 比较次数立接插改进二分法插冒泡排改进的选择 入排序序冒泡排排序 空间代价:⊙(1) 时间代价 最佳情况e(n)e(n)e( nlog n)e(n)e(n)e(n2) a比较次数:e(n2),与冒泡排序一样 交换次数:n-1 平均情况e(n)e(m)e( nlog n)e(m)e(m3)e(m2 总时间代价:e(n2) 最差情况e(n)e(m)e( nlog n)e(m)e(m)e(m2 北真大学张铭编写 聊张帖写 权新有,究7 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 37 7.2.3 直接选择排序 „ 算法思想: „ 找出剩下的未排序记录中的最小 记录，然后直接与数组中第i个记 录交换 ，比冒泡排序减少了移动 次数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 38 45 34 78 12 3 4 32 29 64 i=0 12 34 78 45 3 4 32 29 64 i=1 12 29 78 45 3 4 32 34 64 i=2 12 29 32 45 3 4 78 34 64 i=3 12 29 32 34 3 4 78 45 64 i=4 12 29 32 34 3 4 78 45 64 i=5 12 29 32 34 3 4 45 78 64 i=6 12 29 32 34 3 4 45 64 78 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 39 直接选择排序 template <class Record,class Compare> class StraightSelectSorter:public Sorter<Record,Compare> { //直接选择排序类 public: void Sort(Record Array[],int n); }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 40 template <class Record,class Compare> Void StraightSelectSorter<Record,Compare>:: Sort(Record Array[], int n) { // 依次选出第i小的记录，即剩余记录中最小的那个 for (int i=0; i<n-1; i++) { // 首先假设记录i就是最小的 int Smallest = i; // 开始向后扫描所有剩余记录 for (int j=i+1;j<n; j++) // 如果发现更小的记录，记录它的位置 if (Compare::lt(Array[j], Array[Smallest])) Smallest = j; //将第i小的记录放在数组中第i个位置 swap(Array, i, Smallest); } } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 41 算法分析 „ 不稳定 „ 空间代价：Θ(1) „ 时间代价 ： „ 比较次数：Θ(n2)，与冒泡排序一样 „ 交换次数：n-1 „ 总时间代价：Θ(n2) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 42 7.2.4 简单排序算法的时间代 价对比 Θ(n2 Θ(n ) 2 Θ(n ) 2 Θ(n Θ(nlog n) ) 2 Θ(n ) 2 最差情况 ) Θ(n2 Θ(n ) 2 Θ(n ) 2 Θ(n Θ(nlog n) ) 2 Θ(n ) 2 平均情况 ) Θ(n2 Θ(n Θ(n) ) 2 最佳情况 Θ(n) Θ(n) Θ(nlog n) ) 选择 排序 改进的 冒泡排 序 冒泡排 序 二分法插 入排序 改进 的插 入排 序 直接插 入排序 比较次数