计算机统考重难点班讲义数据结构-第四讲.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * 排序方法： 插入排序 直接插入排序、折半插入排序、2路插入排序 希尔排序 交换排序 冒泡排序、快速排序 选择排序 简单选择排序、堆排序 归并排序 2路归并排序 基数排序 直接插入排序算法思想： 排序区间R[1..n]； 在排序的过程中，整个排序区间被分为两个子区间： 有序区R[1..i-1]和无序区R[i..n]； 共进行n－1趟排序，每趟排序都是把无序区的第一条记录Ri插到有序区的合适位置上。 R R1 R2 Ri-1 Ri Ri+1 Rn-1 Rn 0 1 2 i-1 i i+1 n-1 n R R1 R2 Ri-1 Ri Ri+1 Rn-1 Rn 0 1 2 i-1 i i+1 n-1 n 直接插入排序性能分析： 最好的情况：表的初态恰好是正序排列 比较次数： 移动次数：Mmin＝0 最坏的情况：表的初态恰好是逆序排列 比较次数： 移动次数： 等概条件下平均情况： 平均比较次数： 平均移动次数： 时间复杂度：O(n2) 直接插入排序是一种稳定的排序方法 希尔排序算法思想： 在排序的过程中，整个排序区间被分为几个子表; 对每个子表分别进行直接插入排序 由于n2n12+n22+…+nk2 ( n=n1+n2+…+nk ) 所以对每个子表排序所耗费的时间之和要小于对整个区间排序所耗费的时间 通过对子表小范围的排序,将排序区间调整成基本有序的序列; 不断减少子表的个数(即扩大子表的长度), 直至子表的个数为1, 完成整个排序操作. 冒泡排序( Bubble Sort ) 自下而上(或上而下)扫描记录序列， 相邻的两条记录Ri与Ri－1(或Ri+1)如果是逆序， 则交换位置 冒泡排序性能分析： 最好的情况：表的初态恰好是正序排列，第一趟扫描 没有移动发生 比较次数：Cmin＝n-1 移动次数：Mmin＝0 最坏的情况：表的初态恰好是逆序排列，需要进行n-1趟排序，每趟都要移动整个区间 比较次数： 移动次数： 等概条件下平均情况： 平均比较次数： 平均移动次数： 时间复杂度：O(n2) 冒泡排序是一种稳定的排序方法 快速排序算法思想 设排序区间为R[ low . . high ]； 在排序区间任选一个记录Rx做为基准； 经过一趟排序后，将排序区间分为左、右两个子区间： R[ low . . i-1 ] Rx R[ i+1 . . high ] 使得：R[ low. .i-1 ].key≤ Rx.key≤R[ i+1. .high ].key 然后再用相同的方法分别对左、右区间进行排序，直至每个区间长度都是1为止。 快速排序性能分析： 最坏的情况：表的初态恰好是正序或逆序排列。每次 分区时，基准都恰好是区间的最大或最小键值，分区的结果是有一个区间为空: 对于初态是正序或逆序排列的表，需要进行n－1趟排序，每趟要进行n－i次比较: 快速排序退化成冒泡排序，时间复杂度达到O(n2). 最好的情况：每次分区时，基准都恰好是区间的中间 值，分区的结果使得左、右两个区间长度一样，同步地收敛到1。 就平均性能而言，快速排序的时间复杂度是O(nlogn)。 快速排序被认为是所有O(nlogn)级别的排序方法中平均性能最好的。 快速排序由于是递归实现的，需要消耗运行栈的空间 简单选择排序算法思想： 设：排序区间R[1..n]; 在排序的过程中，整个排序区间被分为两个子区间：有序区R[1..i-1]和无序区R[i..n]; 共进行n－1趟排序，每趟排序都是选择无序区的最小记录Rmin；将Rmin与无序区的第一条记录位置互换，使得无序区长度减1，有序区长度增1。 R R1 R2 Ri-1 Ri Ri+1 Rn-1 Rn 0 1 2 i-1 i i+1 n-1 n 有序区 无序区 简单选择排序性能分析： 比较次数与表的初态无关： 最好的情况：表的初态恰好是正序排列 移动次数：Mmin＝0 最坏的情况：每趟都有移动发生 移动次数：Mmax＝3(n-1) 平均O(n2), 不稳定的排序方法 堆排序 以大顶堆为例： 堆顶是排序区间最大的元素 去掉堆顶，将堆顶与堆的最后一个元素交换位置： ①最大元素归位； ②新树根不满足堆定义，需要通过筛选调整为堆 归并排序(Mergin