数据结构Java版第3章排序

1、数据结构（数据结构（Java版）版）叶核亚叶核亚数据结构（数据结构（Java版）版） 第1章 绪论 第2章 线性表第3章 排序 第4章 栈与队列 第5章 数组和广义表 第6章 树和二叉树 第7章 查找 第8章 图 第9章 综合应用设计第3章 排序 3.1 排序的基本概念 3.2 插入排序 3.3 交换排序 3.4 选择排序 3.5 归并排序数据结构（Java版）叶核亚3.1 排序的基本概念1数据序列数据序列（datalist）是待排序的数据元素的有限集合。2关键字通常数据元素由多个数据项组成，以其中某个数据项作为排序依据，则该数据项称为关键字（key）。 3排序算法的稳定性在数据序列中，如果有

2、两个数据元素ri和rj，它们的关键字ki等于kj，且在未排序时，ri位于rj之前。如果排序后，元素ri仍在rj之前，则称这样的排序算法是稳定的（stable），否则是不稳定的排序算法。数据结构（Java版）叶核亚4内排序与外排序n内排序：在待排序的数据序列中，数据元素个数较少，整个排序过程中所有的数据元素都可以保留在内存，则这样的排序称为内排序。n外排序：待排序的数据元素非常多，以至于它们必须存储在磁盘等外部存储介质上，则这样的排序称为外排序。显然，外排序过程中需要多次访问外存。5排序算法的性能评价n排序算法的时间复杂度：指算法执行中的数据比较次数、数据移动次数与待排序数据序列的元素个数n之间

3、的关系。n排序算法的空间复杂度：指算法执行中，除待排序数据序列本身所占用的内存空间外，需要的附加内存空间与待排序数据序列的元素个数n之间的关系。数据结构（Java版）叶核亚3.2 插入排序n插入排序（insertion sort）的基本思想是：每趟将一个待排序的数据元素，按其关键字大小，插入到已排序的数据序列中，使得插入后的数据序列仍是已排序的，直到全部元素插入完毕。n3.2.1 直接插入排序n3.2.2 希尔排序数据结构（Java版）叶核亚3.2.1 直接插入排序1直接插入排序算法2顺序存储结构线性表的直接插入排序518765432table(a) k=5，i=1，插入535(b) k=3，

4、在子序列5中查找，i=1，5向后移动,插入3253(c) k=2，在3，5中查找，i=1，3,5向后移动,插入227543(e) k=7,在2，3，4，5中查找，i=5，插入7(f) k=1，在2，3，4，5，7中查找，i=1，2,3,4,5,7向后移动,插入11754322543(d) k=4，在2，3，5中查找，i=3，5向后移动,插入4序号iiiiii1234521图3.1 直接插入排序算法描述数据结构（Java版）叶核亚【例3.1】 顺序表的直接插入排序的算法实现与测试。import ds_java.LinearList1; /顺序存储结构的线性表类public class Inser

5、tSort1 extends LinearList1 /直接插入排序 public InsertSort1(int table) /将table数组元素依次插入已排序顺序表 super(table.length); for(int i=0;i=i;j-)数据结构（Java版）叶核亚3算法分析n直接插入排序的平均比较次数为 n平均移动次数为n直接插入排序的时间复杂度为O(n2)。n直接插入排序算法是稳定的。ninnniC12241434121平均ninnniM1244) 1(2平均数据结构（Java版）叶核亚4链表的直接插入排序pprior data next 1headq2 3 (a) 空表插

6、入(c) 中间插入(b) 头插入q 3 3 head 1qheadrearheadrear 1headq2 3 (d) 尾插入rearrear 4 图3.2 双向链表的插入排序算法描述数据结构（Java版）叶核亚【例3.2】 双向链表的直接插入排序import ds_java.TwolinkNode; /双向链表的结点类import ds_java.Twolink1; /双向链表类public class Twolink2 extends Twolink1 /双向链表插入排序 protected TwolinkNode rear; /引用链表最后一个结点 Twolink2() /建立空链表 s

7、uper(); /head=null rear=null; Twolink2(int n) /n个随机值插入双向链表 int i=0,k; System.out.print(insert: ); for(i=0;ithis.get(j+jump)时，表示该元素this.get(j)已在这趟排序后的位置，不需交换，则退出最内层循环。数据结构（Java版）叶核亚希尔排序算法 public void shellsort()/对顺序表对象进行希尔排序/数据元素已存储在table数组中 int i,j,jump,n=this.length(); jump=n/2; while(jump0) /控制增量

8、for(i=jump;i0) if(this.get(j)this.get(j+jump) /与相隔jump的元素比较、交换 swap(j,j+jump); /反序时，交换 j=j-jump;/继续与前面的元素比较 数据结构（Java版）叶核亚3.3 交换排序n3.3.1 冒泡排序n3.3.2 快速排序数据结构（Java版）叶核亚3.3.1 冒泡排序1冒泡排序算法public void bubblesort() int i,j,n=this.length(); for(i=1;in;i+) /n-1趟排序 for(j=1;jthis.get(j+1) this.swap(j,j+1); /反序

9、时，交换 System.out.print(第+i+趟 ); this.output(); 2算法分析 时间复杂度为O(n2)，空间复杂度为O(1) 。数据结构（Java版）叶核亚3改进的冒泡排序 public void bubblesort() int i=1,j,n=this.length(),index=1; boolean exchange=true; /是否交换的标记 while(in & exchange) /最多n-1趟排序 System.out.print(第+i+趟 index=+index+ n-i=+(n-i)+ ); exchange=false; /假定元素未

10、交换 j=index; /起始比较位置 while(j=n-i) /一轮比较、交换 System.out.print(this.get(j)+this.get(j+1) this.swap(j,j+1); /反序时，交换数据结构（Java版）叶核亚改进的冒泡排序算法描述1567843218765432table(a) 第1趟，i=1,从index到n-i+1的相邻位置元素比较、交换交换index交换交换18567432(b) 第2趟，i=2,从index到n-i+1的相邻位置元素比较、交换交换index交换n-i+1n-i+118756432(c) 第3趟，i=3，比较、交换交换indexn-

11、i+118765432(d) 第3趟，i=4，比较,没有交换，已排序indexn-i+1序号数据结构（Java版）叶核亚3.3.2 快速排序图3.6 快速排序算法描述5713842618765432table(a) vot=5，tablejvot，不移动，j- i j17685423(i) i+，j-，分成两个子序列（left,j）与(i,right)ijrightleft57138426(b) vot=5，tablejvot，将tablei值赋给tablej，j-ijrightleft17638426(d) vot=5，tablejvot，将tablej值赋给tablei，i+ij17638

12、423(e) vot=5，tableivot，i+ij17638423(f) vot=5，tableivot，将tablei值赋给tablej，j-17688423(h) i=j，将vot值赋给tableiij序号图3.6 快速排序算法描述数据结构（Java版）叶核亚1快速排序算法 public void quicksort(int left,int right) /实现一趟快速排序 int i,j,n,vot; if(leftright) /左边界小于右边界，序列有效 i=left; j=right; vot=this.get(i); /第一个值作为基准值 while(i!=j) /进行一轮

13、比较 while(votthis.get(j) & ij) j-; /从右向左寻找较小值 if(ij) this.set(i,this.get(j); /较小值元素向左移动数据结构（Java版）叶核亚2算法分析n快速排序的平均比较次数为O(nlog2n)，时间复杂度为O(nlog2n)。n由于快速排序是递归算法，系统调用时需要设立一个栈（stack）存放参数，最大递归调用层次数为。因此，算法的空间复杂度为O(nlog2n)。数据结构（Java版）叶核亚3.4 选择排序1顺序表的直接选择排序算法 public void selectsort() int i,j,min,k,n = thi

14、s.length(); for(i=1;in;i+) /n-1趟排序 min=i; /记下本趟最小值位置 for(j=i+1;j=n;j+) /一轮比较、交换 if(get(j)get(min) min=j; /记下新的最小值位置 if(min!=i) swap(i,min); /本趟最小值交换到左边 System.out.print(min=+min+ ); this.output(); 数据结构（Java版）叶核亚3单向链表的直接选择排序 3 1head 4 minprior 2(b) 将min结点添加到已排序的单向链表之后 1 (a) 选择值最小的结点(由min指向),将min结点删除s

15、ortedheadmin 3head 4 minprior=null 2(d) 将min结点添加到已排序的单向链表之后 1 2 (c) 选择值最小的结点(由min指向),将min结点删除minheadsortedrearsortedrearsortedrearsortedrearminmin图3.8 单向链表的直接选择排序算法描述数据结构（Java版）叶核亚单向链表的直接选择排序算法 public void selectsort() OnelinkNode sortedhead=null,sortedrear=null; OnelinkNode p=null,q=null,min=null,m

16、inprior=null; do min=head; p=head.next; q=head; while(p!=null) if(p.datamin.data) /比较,min记住最小值位置 minprior=q; /minprior是min的前驱结点 min=p;数据结构（Java版）叶核亚3.5 归并排序1归并排序算法描述n所谓归并，就是将两个已排序的数据序列合并，形成一个已排序的数据序列，又称两路归并。图3.9 归并排序算法描述数据结构（Java版）叶核亚顺序存储线性表的归并排序算法描述数据结构（Java版）叶核亚2顺序表的归并排序算法实现 MergeSort1 temp; /辅助线性

17、表 public void mergesort() /归并排序算法 MergeSort1 x=this; int len=1; /已排序的序列长度,初始值为1 temp=new MergeSort1(x.length(); /temp所需空间与x一样 do x.mergepass(temp,len); /将x中元素归并到temp中 temp.output(); len=len*2; temp.mergepass(x,len); /将temp中元素归并到x中 x.output(); len=len*2; while(lenq.data) /比较两个链表第1个结点的值 q=h1.head;数据结构（Java版）叶核亚实习31实习目的：学习多种排序算法，灵活运行排序算法