数据结构（C语言描述） 马秋菊 第9章排序

《数据结构（C语言描述） 马秋菊 第9章排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、9.1基本概念9.2插入排序9.3交换排序9.4选择排序9.5归并排序9.6基数排序9.7内部排序的比较9.8外部排序9.9小结第九章排序1本章主要内容本章主要内容，本章详细介绍了排序的基本概念和常见的排序方法，包括常用的内部排序方法，外部排序方法等内容。通过本章的学习，应掌握如下内容：l插入排序l交换排序l选择排序l归并排序l基数排序l外部排序l各种排序的比较2关键字：在排序过程中，所依据的数据项称为“关键字”，也称为排序记录的关键码。排序：对任意排列的数据元素序列，通过某种算法使其满足按关键字递增（或递

2、减）关系的过程。排序的稳定性和不稳定性：对需要排序的数据元素序列，将其按关键字进行排序，若相同关键字元素之间的位置关系，排序前与排序后的相对位置不发生变化，称此排序方法满足稳定性；否则称这种排序方法满足不稳定性。9.1基本概念3排序算法中结点的数据类型描述方法：typedefintKeyType;typedefstruct{KeyTypekey;……}ElemType;typedefstruct{ElemTypedata[MAXSIZE+1]；/*结点数组*/intlength；/*表长度*/}SL；内部排

3、序和外部排序：内排序是指待排序列完全存放在内存中所进行的排序过程，适合记录较少的序列。如果待排序列记录数量非常多，排序过程不能一次在内存中完成，必需对外存储器进行访问，这样的排序称为外部排序。49.2.1直接插入排序直接插入排序：是指将一个记录按关键字大小的顺序插入到有序序列中的过程。排序过程如下：设有一组关键字{key1,key2,……,keyn};认为key1就是一个有序序列;令关键字为key2的数据元素插入到上述表长为1的有序序列中,使之成为一个表长为2的有序序列;……最后让关键字为keyn的数据元素

4、插入到上述表长为n-1的有序序列中,使之成为一个表长为n的有序序列。5【例9-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]6【算法9.1】直接插入排序voidInsertSort(SL*p){for(i=2；i<=p->length；i++)if(p->data[i].key

5、data[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]926117算法分析：空间复杂度：该算法只使用了一个辅助存储单元p->data[

6、0]，所以是O(1)；时间复杂度：向有序表中逐个插入记录的操作，进行了n-1趟，每一趟比较和移动记录的次数取决于待排序列按关键码的初始排列状态。最好情况下，即初始序列已经有序的情况下，比较n-1次，移动2(n-1)次。最坏情况下，即初始序列在呈逆序的情况下，比较n(n-1)/2次，移动n(n-1)/2+2n次。因此，时间复杂度为O(n2)，排序方法稳定，适合于记录个数比较少的情况，若原始数据序列在基本有序的情况下，算法效率比较高。8直接插入排序算法中，数据的移动是一步步进行的，当数据量很大时，比较和移动的次

7、数都非常大。希尔排序是对该算法的改进。希尔排序基本思想是先将整个待排序列分割成若干个子序列，然后对各子序列分别进行直接插入排序，当达到有序状态时，再进行一次直接插入排序。排序过程如下：每趟排序，根据对应的步长，将待排序列分割成若干长度为m的子序列，分别对各子序列进行直接插入排序;缩小步长再继续划分子序列排序，直到步长为1为止。9.2.2希尔排序9【例9-2】待排序列为34，81，72，42，10，28，52，77，33，13，109，4，42，89。步长因子di分别取5、3、1，则排序过程如下：d0=5

8、3481724210285277331310944289└────────┴───────┘└────────┴───────┘└────────┴───────┘└────────┴───────┘└───────┘子序列分别为{34，28，109}，{81，52，4}，{72，77，42}，{42，33，89}，{10，13}。10第一趟排序结果：2844233103452724213109817789└──