c语言版习题数据结构1

1、第十章 内部排序10.1 概述10.2 插入排序 10.2.1 直接插入排序 10.2.3 shell排序10.3 交换排序（快速排序）10.4 选择排序 10.4.1 简单选择排序 10.4.3 堆排序10.5 归并排序10.6 基数排序10.7 各种排序方法的比较讨论10.1 内部排序概述排序(Sorting):将数据元素(或记录)的一个任意序列,重新排列成一个按关键字有序的序列。排序方法的稳定性：对关键字相同的数据元素，排序前后它们的领先关系保持不变，则称该排序方法是稳定的。反之，称该排序方法是不稳定的。内部排序待排序记录存放在计算机的内存中进行排序。外部排序待排序记录的数量很大，以致内

2、存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序。排序的分类按排序过程依据的不同原则进行分类：插入排序、交换排序、选择排序、归并排序和基数排序按工作量分类，可以分为三类：(1)简单的排序方法,其时间复杂度为O(n2);(2)先进的排序方法,其时间复杂度为O(nlog2n);(3)基数排序，其时间复杂度为O(dn);排序的基本操作和记录的存储方式排序过程中需要的两种基本操作：（1）比较关键字的大小；（2）将记录从一个位置移至另一个位置。待排序记录序列可有下列三种存储方式：（1）记录存放在一组连续的存储单元中；类似于线性表的顺序存储结构，记录次序由存储位置决定，实现排序需移动记录。（2

3、）记录存放在静态链表中；记录次序由指针指示，实现排序不需移动记录，仅需修改指针。- 链排序（3）记录本身存放在一组连续的存储单元中，同时另设指示各个记录存储位置的地址向量，排序过程中不移动记录本身，而移动地址向量中相应记录的地址。排序结束后再根据地址调整记录的存储位置。- 地址排序待排序记录的数据类型#define MAXSIZE 20typedef int KeyType;typedef struct KeyType key; InfoType otherinfo;RcdType;typedef struct RedType rMAXSIZE+1; int length;SqList;10.

4、2 插入排序10.2.1 直接插入排序例：序列为49，38，65，97，76，13，27，49 (49)，38，65，97，76，13，27，49 (38) (38，49)，65，97，76，13，27，49 (65) (38，49，65)，97，76，13，27，49 (97) (38，49，65，97)，76，13，27，49 (76) (38，49，65，76，97)，13，27，49 (13) (13，38，49，65，76，97)，27，49 (27) (13，27，38，49，65，76，97)，49 (49) (13，27，38，49，49，65，76，97)直接插入排序算法vo

5、id InsertSort(SqList &L) for(i=2; i=L.length; +i) if ( LT(L.ri.key, L.ri-1.key) ) L.r0 = L.ri; / 复制为哨兵 for(j=i-1; LT(L.r0.key, L.rj.key); -j) L.rj+1 = L.rj; / 记录后移 L.rj+1 = L.r0; / InsertSort时间：最坏情形判断与移动各接近 n(n+1)/2; 最好情形判断n次，无移动；故时间复杂度：O(n2)空间：一个辅助空间10.2.2 Shell排序算法基本思想： 先将整个待排序记录序列分割成若干子序列分别进行直接插入

6、排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序。算法复杂度：O(n3/2)Shell排序举例（非稳定的）二趟结果13，04，49，38，27，49，55，65，97，76增量取1：13，04，49，38，27，49，55，65，97，76三趟结果04，13，27，38，49，49，55，65，76，97一趟结果13，27，49，55，04，49，38，65，97，76增量取3：13 55 38 76 27 04 65 49 49 97例： 49，38，65，97，76，13，27，49，55，04增量取5： 49 13 38 27 65 49 97 55 76 0410.3

7、交换排序 1. 冒泡排序（其时间复杂度O(n2)）初始关键字第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后第六趟排序后例： 49 38 38 38 38 13 13 38 49 49 49 13 27 27 65 65 65 13 27 38 38 97 76 13 27 49 49 76 13 27 49 49 13 27 49 65 27 49 76 49 972. 快速排序- 对冒泡排序的一种改进基本思想： 通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，则可分别对这两部分记录继续分别进行排序，以达到整个序列有序。快速排序举例初始关键字

8、：49，38，65，97，76，13，27，49pivot key 49jji1次交换后：27，38，65，97，76，13， ，49iji2次交换后：27，38， ，97，76，13，65，49ijj3次交换后：27，38，13，97，76， ，65，49iji4次交换后：27，38，13， ，76，97，65，49jij一趟完成后：27，38，13，49，76，97，65，49快速排序分析快速排序的平均时间为T(n) = knlog(n)k为某个常数因子经验表明,在同数量级的排序方法中,快速排序的常数因子k最小.就平均时间而言,快速排序是最好的.若初始序列按关键字基本有序,快速排序蜕化为起

9、泡排序,其时间复杂度为O(n2)。改进的方法，用“三者取中”的法则选取枢轴记录（pivotkey).快速排序举例初始关键字：49，38，65，97，76，13，27，49pivot key 49jji1次交换后：27，38，65，97，76，13， ，49iji2次交换后：27，38， ，97，76，13，65，49ijj3次交换后：27，38，13，97，76， ，65，49iji4次交换后：27，38，13， ，76，97，65，49jij一趟完成后：27，38，13，49，76，97，65，49快速排序算法（一）int Partition(SqList &L, int low, int

10、high)L.r0 = L.rlow; / 用子表的第一记录作枢轴记录 pivotkey = L.rlow.key; while(lowhigh) while(low=pivotkey) -high; L.rlow = L.rhigh; / 将比pivotkey 小的记录移到低端 while(lowhigh & L.rlow.key=pivotkey) +low; L.rhigh = L.rlow; / 将比pivotkey 大的记录移到高端 L.rlow = l.r0; return low;快速排序算法（二）void Qsort(SqList &L, int low, int high)

11、if(lowhigh) pivotloc = Partition(L, low, high); Qsort(L, low, pivotloc-1); Qsort(L, pivotloc+1, high); / QSortvoid QuickSort(SqList &L) Qsort(L, 1, L.length); / QuickSort10.4 选择排序 10.4.1. 简单选择排序（其时间复杂度O(n2)）基本思想： 每一趟在序列的后n-i+1(i=1,2,.,n-1)个记录中选取关键字最小的记录作为第i个记录。void SelectSort(SqList &L) for(i=1; iL.

12、length; +i) j = SelectMinKey(L, i); / 在L.ri.length中选择key最小 if(i != j) L.ri L.rj; / 与第i个记录交换 / SelectSort初始关键字：49，38，65，97，76，13，27，49第一次交换：13，38，65，97，76，49，27，49ij10.4.3 堆排序堆的定义：n个元素的序列k1,k2,.,kn当且仅当满足下列条件时，称之为堆。ki = k2iki = k2i+1或( i = 1, 2, . , n/2 )堆举例：96,83,27,38,11,09)12,36,24,85,47,30,53,9196

13、83381109271236854730245391完全二叉树,且所有非叶结点的值均不大于(不小于)其左、右孩子结点的值实现堆要解决的问题（1）如何从一个无序序列建成一个堆？（2）如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？1236854730245391(a)9136854730245312(b)91368547302453(c)24368547913053(d)无序序列建成一个堆（从第n/2到1个元素） 49，38，65，97，76，13，27，494938497613652797(b)4938497665132797(c)49389776132749(a)654938497665

14、132797(d)1338497665274997(e)10.5 归并排序(Merging Sort)将两个或两个以上的有序表组合成一个新的有序表2-路归并举例:初始关键字: 49 38 65 97 76 13 27一趟归并后: 38 49 65 97 13 76 27二趟归并后: 38 49 65 97 13 27 76 三趟归并后: 13 27 38 49 65 76 97 2-路归并算法void Merge(RcdType SR, RcdType &TR, int i, int m, int n) / 将有序的SRi.m和SRm+1.n合并为有序的TRi.n for(j=m+1,k=i;

15、 i=m&j=n; +k) if LQ(SRi.key,SRj.key) TRk = SRi+; else TRk = SRj+; if(i=m) TRk.n = SRi.m; /复制剩余的SRi.m if(j=n) TRk.n = SRj.n; /复制剩余的SRj.n / Merge归并算法的特点需要辅助空间: O(n)整个归并需要 log2n 趟时间复杂度: O(n log2n)它是稳定的排序方法思想可以推广到 “多-路归并“10.6 基数排序(Radix Sorting)不需要进行关键字之间的比较借助多关键字排序的思想对单关键字排序10.6.1 多关键字排序 2345678910JQKA

16、 2345678910JQKA2345678910JQKA2345678910JQKA花色 ()优先于面值(23.109-063-930-589-184-505-269-008-0830132456789278109063930184505589269008083930-063-083-184-505-278-008-109-589-269930-063-083-184-505-278-008-109-589-2690132456789278109063930184505589269008184505-008-109-930-063-269-278-083-184-58901324567895

17、05008109930063269278083083589008-063-083-109-184-269-278-505-589-930基数排序分析(d个关键字的取值范围rd）“收集”重复的次数为d;一轮“分配”的次数为n+rd;时间复杂度为O(d(n+rd);链式基数排序所需辅助存储量为O(n)。10.7 各种排序方法的比较讨论排序方法简单排序Shell排序快速排序堆排序归并排序基数排序平均时间O(n2)O(n3/2)O(nlogn)O(nlogn)O(nlogn)O(d(n+rd)最坏情况O(n2)O(n2)O(n2)O(nlogn)O(nlogn)O(d(n+rd)辅助存储O(1)O(1)O(logn)O(1)O(n)O(rd)插入, 交换, 选择, 归