最新数据结构(Java版)排序课件ppt.ppt

《最新数据结构(Java版)排序课件ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构(Java版)排序基本概念排序：将n个数字按一定顺序排列（比如：升序，或者降序）班上有30个学生，按照学号进行由小到大的排序2排序基本概念内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序3排序课堂练习与算法设计一组关键字（19,01,26,92,87,11,43,87,21），进行冒泡排序，试列出每一趟排序后的关键字序列19,1,26,92,87,11,43,87,21i=11192687114387

2、2192i=211926114387218792i=311911264321878792i=411119262143878792i=511119212643878792i=611119212643878792i=711119212643878792i=811119212643878792算法设计：for(inti=1;i<=a.length-1;i++)for(j=0;ja[j+1])交换a[j]和a[j+1]编程实现7排序选择排序基本思想：依次从待排序记录序列中选择出关键字值最小

3、（或最大）的记录、关键字值次之的记录、……，并分别将它们定位到序列左侧（或右侧）的第1个位置、第2个位置、……，从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。选择排序种类：直接选择排序和堆排序8排序直接选择排序实例初始关键字序列：5133629687172851↑↑第一趟排序后：[17]33629687512851↑↑第二趟排序后：[1728]629687513351↑↑第三趟排序后：[172833]9687516251第四趟排序后：[17283351]87966251第五趟排序后：[1728335151

4、]966287第六趟排序后：[172833515162]9687第七趟排序后：[1728335151628796]9排序课堂练习与算法设计选择排序过程：3412452187263i=13124521872634i=23124521872634i=33122145872634i=43122126874534i=53122126344587i=63122126344587算法设计：n=a.length;for(i=0,i

5、++)if(a[min]>a[j])min=j;if(min!=i)交换a[min]和a[i]}10排序插入排序主要思想：不断地将待排序的数值插入到有序序列中，使有序序列逐渐扩大，直至所有数值都进入有序序列中位置插入排序种类：直接插入排序、折半插入排序、二路插入排序、表插入排序和希尔排序11排序直接插入排序基本思想：将记录R[i]插入到有序子序列R[0..i-1]中，使记录的有序序列从R[0..i-1]变为R[0..i]12排序直接插入排序实例初始关键字序列：[51]33629687172851i=1(33)[3351]629687

6、172851i=2(62)[335162]9687172851i=3(96)[33516296]87172851i=4(87)[3351628796]172851i=5(17)[173351628796]2851i=6(28)[17283351628796]51i=7(51)[1728335151628796]13排序一组关键字（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

7、=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;i

8、]中,保持原来的排序1在a[0]…a[i-1]中找到插入的位置j2把a[j]…a[i-1]逐个后移一个位置(a[i-1]移到a[i],…a[j]移到a[j+1]])3把a[i]放到a[j]处}}课堂练习与算法设计14排序快速排序基本思