数据结构(Java版)排序说课讲解.ppt

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

1、数据结构(Java版)排序排序2基本概念内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序排序3几种常用的排序方法冒泡排序选择排序快速排序插入排序希尔排序归并排序排序4冒泡排序基本思想：对所有相邻记录的关键字值进行比较，如果是逆序（a[j]>a[j+1]），则将其交换，最终达到有序化排序5冒泡排序实例初始关键字序列：5133629687172851第一趟排序结果：33516287172851[96]第二趟排序结果：33516217285

2、1[8796]第三趟排序结果：3351172851[628796]第四趟排序结果：33172851[51628796]第五趟排序结果：172833[5151628796]第六趟排序结果：[1728335151628796]51336296872817513351628717512896排序6课堂练习与算法设计一组关键字（19,01,26,92,87,11,43,87,21），进行冒泡排序，试列出每一趟排序后的关键字序列19,1,26,92,87,11,43,87,21i=111926871143872192i=211926114387218792i=3119

3、11264321878792i=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选择排序基本思想：依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的记录、……，并分别将它们定位到序列左侧（或右侧）的第1

4、个位置、第2个位置、……，从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。选择排序种类：直接选择排序和堆排序排序8直接选择排序实例初始关键字序列：5133629687172851↑↑第一趟排序后：[17]33629687512851↑↑第二趟排序后：[1728]629687513351↑↑第三趟排序后：[172833]9687516251第四趟排序后：[17283351]87966251第五趟排序后：[1728335151]966287第六趟排序后：[172833515162]9687第七趟排序后：[1728335151628796

5、]排序9课堂练习与算法设计选择排序过程：3412452187263i=13124521872634i=23124521872634i=33122145872634i=43122126874534i=53122126344587i=63122126344587算法设计：n=a.length;for(i=0,ia[j])min=j;if(min!=i)交换a[min]和a[i]}排序10插入排序主要思想：不断地将待排序的

6、数值插入到有序序列中，使有序序列逐渐扩大，直至所有数值都进入有序序列中位置插入排序种类：直接插入排序、折半插入排序、二路插入排序、表插入排序和希尔排序排序11直接插入排序基本思想：将记录R[i]插入到有序子序列R[0..i-1]中，使记录的有序序列从R[0..i-1]变为R[0..i]排序12直接插入排序实例初始关键字序列：[51]33629687172851i=1(33)[3351]629687172851i=2(62)[335162]9687172851i=3(96)[33516296]87172851i=4(87)[3351628796]172851i

7、=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=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,2

8、6,87,92,43,87,21i=61,11,19