数据结构（Java语言描述）第八章 排序.pptx

第八章 排序;;总体要求;8.1 基本概念; 设 Ki = Kj (1≤i≤n, 1≤j≤n, i≠j )，且在排序前的序列中 Ri 领先于 Rj（即 i j ）。若在排序后的序列中 Ri 仍领先于 Rj，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。 ; 内部排序和外部排序 ;public class RecordTypeT extends ComparableT { T key;//关键字域 //...... 其它域 public RecordType(){ key=null; } public RecordType(T data){ key=data; } };public class SortT extends ComparableT { protected ArrayListRecordTypeT elem; protected int length; //表长度 public Sort(T[] data,int n){ elem=new ArrayListRecordTypeT(); RecordTypeT e; for(int i=0;in;i++){ e=new RecordTypeT(data[i]); elem.add(i, e); } length=n; } //各种排序方法 };8.2 插入排序;;【算法8-1】直接插入排序算法;T(n)=O(n2) ;8.2.2希尔排序;0 1 2 3 4 5 6 7 8 9;【算法8-2】希尔排序算法;8.3 交换排序;;【算法8-3】冒泡排序算法;一般取第一个记录 ; 快速排序 ;如何实现一次划分？;解决方法： 对分割得到的两个子序列递归地执行快速排序。;8.4 选择排序;例 ;8.4.2 堆排序; 堆排序： ;;;;8.5归并排序（二路归并排序）;每趟归并的时间复杂度为O(n)，共需进行 ?log2n? 趟。;8.6各种排序方法的比较;2、从空间复杂度比较 两路归并排序的空间复杂度最大为 O(n)，快速排序的空间复杂度为 O(lon2n)，其它排序的空间复杂度为 O(1)。;4、从算法简单性比较 直接插入排序、冒泡排序、简单选择排序都是简单的排序方法，算法简单，易于理解，而堆排序、快速排序、两路归并排序都是改进型的排序方法，算法比简单排序要复杂得多，也难于理解。