计算机二级c语言知识查找与排序思维导图

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序

从线性表中取一个元素，设为T，将线性表中后面小于T的元素移到前面

而前面大于T的元素移到后面，结果就是将线性表分成两部分（称两个子表）

T插入到其分割线的位置处，这个过程称为线性表的分割

然后再用同样的方法对分割处的子表再进行同样的分割。

快速排序不是对两个相邻元素进行比较，可以实现通过一次交换而消除多个逆序，但由于均与T（基准元素）比较，也可能会产生新的逆序。

有序表的二分查找为log2n,堆排序为nlog2n，顺序查找为n，寻找最大项或寻找最小项为n-1，希尔排序比较次数为nr(1<r<2)。

先取整数（称为增量）d1<n，把全部数据元素分成d1组，所有距离为d1倍数的元素放在一组中，组成了一个子序列

对每个子序列分别进行简单插入排序

然后去d2<d1重复上述分组和排序工作，直到di=1，即所有记录在一组中为止。

希尔排序可以实现通过一次交换而消除多个逆序。

用顺序存储结构

线性表是有序表。