C语言易错点总结（四）

9.排序技术
(1)交换类排序技术
    ①冒泡排序法   
  冒泡排序的思想如下:
      在线性表中依次查找相邻的数据元紫,将表中最大的元素不断往后移动,反复操作直到消除所有逆序，此时,该表已经排序结束。
    假设线性表的长度为n,则在最坏的情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前扫描，需要比较n(n-1)/2次，其数量级为n⒉
    ②快速排序法
快速排序法。
      快速排序法的基本思想如下:
      在线性表中逐个选取元素,将线性表进行分制，直到所有元素全部选取完毕此时线性我已经排序结束。需要比较n(n-1)/2次

(2)插入类排序法
      插人排序是指將无序序列中的各元素依次插人到已经有序的线性表中。  
     ①简单插人排序法。
      简单插人排序是把n个待排序的元素看成一个有序表和一个无序表，开始时，有序表只包含一个元素，而无序表包含n-1个元素，每次取无序表中的第一个元素插人到有序表中的正确位置， 使之成为增加一个元素的新的有序表。插人元素时,插人位置及其后的记录依次向后移动。最后有序表的长度为n,而无序表为空，此时排序完成。
      在简单插人排序中,每一次比较后最多移掉一个逆序，因此，该排序方法的效率与冒泡排序法相同。在最坏的情况下，简单插人排序需要n(n-1)/2次比较。
    ②希尔排序法。
      ​希尔排序法的基本思路为:将整个无序序列分割成若千个小的子序列并分别进行插人排序。
希尔排序的效率与所选取的增量序列有关

(3)选择类排序法
    选择类排序法的基本思想是通过每越从待排字序列中选出值最 小的元家，按顺序放在已排好序的有字子表的后面，直到全  序部序列满足排序要求为止
    ①简单选择排序法。
    简单选择排序的基本思想是:首先从所有n个待排序的数据元素中选择最小的元素，将该元素与第一个元素交换，再从剩下的n-1个元素中选出最小的元素与第二个元素交换。重复这样的操作直到所有的元素有序为止。
简单选择排序在最坏情况下需要比较n(n-1)/2次。    ②堆排序法。
堆排序的方法如下:
①将一个无序序列建成堆;
②将堆顶元素与堆中最后一个元素交换。忽略已经交换到最后的那个元素，考虑前n-1个元素构成的子序列，只有左、右子树是堆，可以将该子树调整为堆。这样重复去做第二步，直到剩下的子序列为空时止。
在最坏的情况下，堆排序需要比较的次数为nlog2n。
总结：线性表排序中，堆排序的比较次数为nlog2n；快速排序、冒泡排序、直接插入排序、简单选择排序比较次数均为​n(n-1)/2次；二分法为log2n；顺序查找为n

10.数据流图与程序流程图
数据流图------>数据流
程序流程图---->控制流
要注意区别

11.将E-R转化为数据模型属于逻辑设计阶段

12.算法复杂度指所需要的计算工作量
    计算工作量指用所执行的基本运算次数的度量

13.白盒测试与黑盒测试
    白盒测试方法：逻辑覆盖测试（语句覆盖、路径覆盖、判断覆盖、条件覆盖）、基本路径测试等
    黑盒测试方法：等价类划分法、边界值分析法、错误推理法、因果图等