算法

查找与排序技术

顺序查找

顺序表又称为顺序搜索。

从表中的第一个元素开始比较，若相等则查找成功，若元素不存在，则查找失败。

当一个线性表的长度为n时，最坏情况下，查找一个元素需要比较n次

二分查找法

二分查找只适用于顺序存储的有序表。

步骤：

将x与线性表的中间元素进行比较：

  若中间元素的值等于x，则说明查找成功，查找结束

  若x小于中间元素的值，则在线性表的前半部分以相同的方法查找。

  若x大于中间元素的值，则在线性表的后半部分以相同的方法查找。

  这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。

最糟糕的情况需要查找log₂n次。

交换类排序法

冒泡排序

通过相邻数据元素的交换逐步将线性表变成有序的。

从前往后，然后从后往前比较并交换元素。

最坏情况时要比较n(n - 1)/2 次，n代表线性表的长度。

快速排序

快速排序法是对冒泡排序法的改进，又叫作分区交换排序法。

基本思想如下：

从线性表中任意选取一个元素（通常选第一个元素），设为T，将线性表中小于T的元素移到T的前面，而大于T的元素移到T的后面，结果就将线性表分成了两部分（称为两个子表），T处于分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T，然后用同样的方法对分割后的子表进行快速排序，直到各个子表的长度为1为止。

插入类排序法

简单插入排序法

简单插入排序法也叫直接插入排序法。

插入排序是指将无序序列中各元素依次插入到已经有序的线性表中。

希尔排序法

希尔排序法（Shell Sort）又称缩小增量排序法，它对简单插入排序做了比较大的改进。

其方法如下：

将整个无序序列分割成若干小的子序列分别进行简单插入排序。

时间复杂度: O（n^1.5）

堆排序法

每个父节点同时大于等于两个子结点或每个父结点同时小于等于两个子结点的结构成为堆

时间复杂度: O（ nlog₂n ）

考点总结

1. 二分法查找只适用于顺序存储的线性表，且表中的元素必须按关键字有序（升序，但允许相邻元素值相等）排列；
2. 在长度为n的有序线性表中进行二分查找其时间复杂度为O（ log₂n ）。

交换类

1. 冒泡排序：n(n-1)/2
2. 快速排序：n(n-1)/2