排序的基本概念.pptxVIP

19.1排序的基本概念9.2插入排序9.3选择排序9.4交换排序9.5归并排序9.6基数排序9.7性能比较第9章排序

9.1排序的基本概念21.排序:将一组杂乱无章的数据按一定的规律顺次排列起来的过程。存放在数据表中按关键字排序2.排序的目的：便于查找。3.排序算法好坏的衡量标准：(1)时间复杂度——它主要是分析记录关键字的比较次数和记录的移动次数。(2)空间复杂度——算法中使用的内存辅助空间的多少。(3)稳定性——若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。4、排序的种类：分为内部排序和外部排序两大类。若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则称为外部排序。注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。

35.待排序记录在内存中怎样存储和处理？①顺序排序——排序时直接移动记录；②链表排序——排序时只移动指针；③地址排序——排序时先移动地址，最后再移动记录。注：地址排序中可以增设一维数组来专门存放记录的地址。6.内部排序的算法有哪些？——按排序的规则不同，可分为5类：插入排序、交换排序、选择排序、归并排序、基数排序——按排序算法的时间复杂度不同，可分为3类：简单的排序算法：时间效率低，O(n2)先进的排序算法:时间效率高，O(nlog2n)基数排序算法：时间效率高，O(d×n)d＝关键字的位数(长度)

9.2插入排序4最简单的排序法！插入排序的基本思想是：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。常用的插入排序有：直接插入排序和希尔排序两种。一、直接插入排序1、其基本思想是：顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。

初始关键字序列：【13】,6,3,31,9,27,5,11第一次排序：【6,13】,3,31,9,27,5,11第二次排序：【3,6,13】,31,9,27,5,11第三次排序：【3,6,13，31】,9,27,5,11第四次排序：【3,6,9,13，31】,27,5,11第五次排序：【3,6,9,13，27,31】,5,11第六次排序：【3,5,6,9,13，27,31】,11第七次排序：【3,5,6,9,11，13，27,31】例1：关键字序列T=（13，6，3，31，9，27，5，11），请写出直接插入排序的中间过程序列。注：方括号[]中为已排序记录的关键字，下划横线的关键字表示它对应的记录后移一个位置。

2、C语言程序6voidInsertSort(DataTypea[],intn)/*用直接插入法对a[0]--a[n-1]排序*/{ inti,j; DataTypetemp; for(i=0;in-1;i++) { temp=a[i+1]; j=i; while(j-1temp.keya[j].key){ a[j+1]=a[j]; j--; } a[j+1]=temp; }}

voidmain(void){DataTypetest[6]={64,5,7,89,6,24};inti,n=6;SeqListmyList;ListInitiate(myList);for(i=0;in;i++) ListInsert(myList,i,test[i]);InsertSort(myList.list,myList.size);for(i=0;in;i++)printf(%d,myList.list[i].key);}#includestdio.htypedefintKeyType;typedefstruct{KeyTypekey;}DataType;#defineMaxSize100#includeSeqList.h

3、直接插入排序算法分析二、希尔（shell）排序（又称缩小增量排序）8(1)时间效率：因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)