数据结构(Java版)排序PPT课件

-,1,排序,深圳职业技术学院软件系,-,2,基本概念,排序：将n个数字按一定顺序排列（比如：升序，或者降序）班上有30个学生，按照学号进行由小到大的排序,-,3,基本概念,内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序,-,4,几种常用的排序方法,冒泡排序选择排序快速排序插入排序希尔排序归并排序,-,5,冒泡排序,基本思想：对所有相邻记录的关键字值进行比较，如果是逆序（ajaj+1），则将其交换，最终达到有序化,-,6,冒泡排序实例,初始关键字序列：5133629687172851第一趟排序结果：3351628717285196第二趟排序结果：3351621728518796第三趟排序结果：3351172851628796第四趟排序结果：3317285151628796第五趟排序结果：1728335151628796第六趟排序结果：1728335151628796,51,33,62,96,87,28,17,51,33,51,62,87,17,51,28,96,-,7,课堂练习与算法设计,一组关键字（19,01,26,92,87,11,43,87,21），进行冒泡排序，试列出每一趟排序后的关键字序列19,1,26,92,87,11,43,87,21i=111926871143872192i=211926114387218792i=311911264321878792i=411119262143878792i=511119212643878792i=611119212643878792i=711119212643878792i=811119212643878792,算法设计：for(inti=1;iaj+1)交换aj和aj+1,编程实现,-,8,选择排序,基本思想：依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的记录、，并分别将它们定位到序列左侧（或右侧）的第1个位置、第2个位置、，从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。选择排序种类：直接选择排序和堆排序,-,9,直接选择排序实例,初始关键字序列：5133629687172851第一趟排序后：1733629687512851第二趟排序后：1728629687513351第三趟排序后：1728339687516251第四趟排序后：1728335187966251第五趟排序后：1728335151966287第六趟排序后：1728335151629687第七趟排序后：1728335151628796,-,10,课堂练习与算法设计,选择排序过程：3412452187263i=13124521872634i=23124521872634i=33122145872634i=43122126874534i=53122126344587i=63122126344587,算法设计：n=a.length;for(i=0,iaj)min=j;if(min!=i)交换amin和ai,-,11,插入排序,主要思想：不断地将待排序的数值插入到有序序列中，使有序序列逐渐扩大，直至所有数值都进入有序序列中位置插入排序种类：直接插入排序、折半插入排序、二路插入排序、表插入排序和希尔排序,-,12,直接插入排序,基本思想：将记录Ri插入到有序子序列R0.i-1中，使记录的有序序列从R0.i-1变为R0.i,-,13,直接插入排序实例,初始关键字序列：5133629687172851i=1(33)3351629687172851i=2(62)3351629687172851i=3(96)3351629687172851i=4(87)3351628796172851i=5(17)1733516287962851i=6(28)1728335162879651i=7(51)1728335151628796,-,14,一组关键字（19,1,26,92,87,11,43,87,21），进行插入排序，试列出每一趟排序后的关键字序列19,1,26,92,87,11,43,87,21i=11,19,26,92,87,11,43,87,21i=21,19,26,92,87,11,43,87,21i=31,19,26,92,87,11,43,87,21i=41,19,26,87,92,11,43,87,21i=51,11,19,26,87,92,43,87,21i=61,11,19,26,43,87,92,87,21i=71,11,19,26,43,87,87,92,21i=81,11,19,21,26,43,87,87,92,算法设计：voidinsertSort(inta)n=a.length;for(i=1;in;i+)将ai插入到a0ai-1中,保持原来的排序1在a0ai-1中找到插入的位置j2把ajai-1逐个后移一个位置(ai-1移到ai,aj移到aj+1)3把ai放到aj处,课堂练习与算法设计,-,15,快速排序,基本思想：首先将待排序记录序列中的所有记录作为当前待排序区域，从中任选取一个记录（通常可选第一个记录），以它的关键字作为枢轴（或支点）（pivot），凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后,-,16,快速排序一趟排序过程,初始关键字序列：5133629687172851R0=51ij第一次交换之后：2833629687172851ij第二次交换之后：2833629687176251ij第三次交换之后：2833179687176251ij第四次交换之后：2833179687966251ij完成一趟排序：2833175187966251,-,17,快速排序结果,初始关键字序列：5133629687172851一趟排序之后：2833175187966251分别进行快速排序：172833516287965162有序序列：1728335151628796,-,18,课堂练习与算法设计,给出一组关键字，快速排序的每一趟的排序结果：46,58,15,45,90,18,10,62,87,23t=4623,58,15,45,90,18,10,62,87,23ijt=4623,58,15,45,90,18,10,62,87,58ijt=4623,10,15,45,90,18,10,62,87,58ijt=4623,10,15,45,90,18,90,62,87,58ijt=4623,10,15,45,46,18,90,62,87,58ij,算法设计：voidquickSort(inta,ints,intt)if(st)k=partion(a,s,t);quickSort(a,s,k-1)quickSort(a,k+1,t)intpartion(inta,intl,intr)temp=al;j=r;i=l;whi