数据库——排序VIP免费

2024年12月29日星期日1第十章排序10.1基本概念10.2插入排序10.3交换排序10.4选择排序10.5归并排序10.6基数排序10.7内部排序的比较10.8外部排序10.9小结10.1基本概念10.2插入排序10.3交换排序10.4选择排序10.5归并排序10.6基数排序10.7内部排序的比较10.8外部排序10.9小结2024年12月29日星期日2第十章排序本章主要内容本章主要内容，本章详细介绍了排序的基本概念和常见的排序方法，包括常用的内部排序方法，外部排序方法等内容。通过本章的学习，应掌握如下内容：插入排序交换排序选择排序归并排序基数排序外部排序各种排序的比较2024年12月29日星期日3第十章排序关键字：在排序过程中，所依据的数据项称为“关键字”，也称为排序记录的关键码。排序：对任意排列的数据元素序列，通过某种算法使其满足按关键字递增（或递减）关系的过程。排序的稳定性和不稳定性：对需要排序的数据元素序列，将其按关键字进行排序，若相同关键字元素之间的位置关系，排序前与排序后的相对位置不发生变化，称此排序方法满足稳定性；否则称这种排序方法满足不稳定性。10.1基本概念2024年12月29日星期日4第十章排序排序算法中结点的数据类型描述方法：typedefintKeyType;typedefstruct{KeyTypekey;……}ElemType;typedefstruct{ElemTypedata[MAXSIZE+1]；/*结点数组*/intlength；/*表长度*/}SL；内部排序和外部排序：内排序是指待排序列完全存放在内存中所进行的排序过程，适合记录较少的序列。如果待排序列记录数量非常多，排序过程不能一次在内存中完成，必需对外存储器进行访问，这样的排序称为外部排序。2024年12月29日星期日5第十章排序10.2.1直接插入排序直接插入排序：是指将一个记录按关键字大小的顺序插入到有序序列中的过程。排序过程如下：设有一组关键字{key1,key2,……,keyn};认为key1就是一个有序序列;令关键字为key2的数据元素插入到上述表长为1的有序序列中,使之成为一个表长为2的有序序列;……最后让关键字为keyn的数据元素插入到上述表长为n-1的有序序列中,使之成为一个表长为n的有序序列。2024年12月29日星期日6第十章排序【算法10.1】直接插入排序voidInsertSort(SL*p){for(i=2；i<=p->length；i++)if(p->data[i].keydata[i-1].key){p->data[0]=p->data[i]；/*设置监视哨*/for(j=i-1；p->data[0].keydata[j].key；j--)p->data[j+1]=p->data[j]；/*记录后移*/p->data[j+1]=p->data[0]；/*插入到正确位置*/}/*if*/}a[0]a[1]a[2]a[3]a[4]a[5]i=1：[6]1392611i=2：[613]926112024年12月29日星期日7第十章排序【例10-1】有一个待排序列{6，13，9，26，11}，将其按照直接插入方法实现排序。如图所示：初始关键字：a[1]a[2]a[3]a[4]a[5]i=1：[6]1392611i=2：[613]92611i=3：[6913]2611i=4：[691326]11i=5：[69111326]2024年12月29日星期日8第十章排序算法分析：空间复杂度：该算法只使用了一个辅助存储单元p->data[0]，所以是O(1)；时间复杂度：向有序表中逐个插入记录的操作，进行了n-1趟，每一趟比较和移动记录的次数取决于待排序列按关键码的初始排列状态。最好情况下，即初始序列已经有序的情况下，比较n-1次，移动2(n-1)次。最坏情况下，即初始序列在呈逆序的情况下，比较n(n-1)/2次，移动n(n-1)/2+2n次。因此，时间复杂度为O(n2)，排序方法稳定，适合于记录个数比较少的情况，若原始数据序列在基本有序的情况下，算法效率比较高。2024年12月29日星期日9第十章排序直接插入排序算法中，数据的移动是一步步进行的，当数据量很大时，比较和移动的次数都非常大。希尔排序是对该算法的改进。希尔排序基本思想是先将整个待排序列分割成若干个子序列，然后对各子序列分别进行直接插入排序，当达到有序状态时，再进行一次直接插入排序。排序过程如下：每趟排序，根据对应的步长，将待排序列分割成若干长度为m的子序列，分别对各子序列进行直接插入排序;缩小步长再继续划分子序列排序，直到步长为1为止。10.2.2希尔排序2024年12月29日星期日10第十章排序【例10-2】待排序列为34，81，72，42，10，28，52，77，33，13，10...