查找

1.顺序查找

• 思路：从线性表的第一个元素开始，逐个将线性表中的元素与被查元素进行比较，如果相等，则查找成功，停止查找；若整个线性表扫描完毕，仍未找到与被查元素相等的元素，则表示线性表中没有要查找的元素，查找失败。
• 最好情况下，第一个元素就是要查找的元素，则比较次数为1次
• 最坏情况下，最后一个元素才是要找的元素，或者在线性表中，没有要查找的元素，则需要与线性表中所有的元素比较，比较次数为n次
• 平均情况下，大约需要比较n/2次
• 唯一选择：
  • 线性表为无序表，则不管是顺序存储结构，还是链式存储结构，都只能用顺序查找
  • 即使线性表是有序的，如果采用链式存储结构，也只能用顺序查找
    2.二分查找
• 满足条件
  • 用顺序存储结构
  • 线性表是有序的，有序是指元素按非递减排列，即从小到大排列，且允许相邻元素相等
• 对于长度为n的有序线性表，利用二分查找元素X的过程
  • 如果X的值与中间项的值相等，则查找成功，结束查找
  • 如果X小于中间项的值，则在线性表的前半部分以二分法继续查找
  • 如果X大于中间项的值，则在线性表的后半部分以二分法继续查找
• 顺序查找法每一次比较，只将查找范围减少1，而二分法查找，每比较一次，可将查找范围减少为原来的一半，效率大大提高。对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较$log_{2}n$次

排序

1.交换类排序

• 冒泡排序
  • 冒泡排序就是通过两两相邻数据元素之间的比较和交换，不断地消去逆序，直到所有数据元素有序为止
  • 最坏情况下，长度为n的线性表排序，冒泡排序需要比较的次数为n(n-1)/2
• 快速排序
  • 快速排序就是在待排序的n个元素中取一个元素K,以元素K作为分割标准，把所有小于K元素的数据元素都移到K前面，把所有大于K元素的数据元素都移到K后面。这样，以K为分界线，把线性表分割为两个子表，这称为一趟排序。然后，对K前后的两个子表分别重复上述过程。继续下去，直到分割的子表的长度为1为止。
  • 快速排序最坏的情况需要进行n(n-1)/2次比较，实际效率比冒泡排序高

2.插入类排序

• 插入排序是每次将一个待排序元素，按其元素值的大小插入到前面已经排好序的子表中的适当位置，直到全部元素插入完成为止
• 简单插入排序
  • 把n个待排序的元素看成是一个有序表和一个无序表，开始时，有序表只包含一个元素，而无序表包含另外n-1个元素，每次取无序表中的第一个元素插入到有序表中的正确位置，使之成为增加一个元素的新的有序表。插入元素时，插入位置及其后的记录依次向后移动。最后有序表的长度为n，而无序表为空，此时排序完成
  • 最坏情况，简单插入排序需要n(n-1)/2次比较
• 希尔排序
  • 先取一个整数$d{1} < n$，把全部数据元素分成$d{1}$个组，所有距离为$d{1}$倍数的元素放在一组中，组成了一个子序列，对每个子序列分别进行简单插入排序。然后取$d{2} < d{1}$重复上述分组和排序工作，直到$d{i} = 1$，即所有记录在一组中为止
  • 希尔排序的效率与所选取的增量序列有关，最坏情况下，希尔排序需要比较的次数是$n ^{r}(1<r<2)$

3.选择类排序

• 通过每一趟从待排序序列中选出值最小的元素，顺序放在已安排好序的有序子表的后面，直到全部序列满足排序要求为止
• 简单选择排序
  • 先从所有n个待排序的数据元素中选择最小的元素，将该元素与第1个元素交换，再从剩下的n-1个元素中选出最小的元素与第2个元素交换。重复这样的操作直到所有的元素有序为止
  • 简单选择排序法在最坏的情况下需要比较n(n-1)/2次
• 堆排序
  • 若有n个元素的序列$(h{1},h{2},\cdots h{n})$，将元素按顺序组成一棵完全二叉树，当且仅当满足下列条件时称为堆。$ \begin{cases} h{i} \geq h{2i} \newline h{i} \geq h{2i+1} \end{cases}$ 或者$ \begin{cases} h{i} \leq h{2i} \newline h{i} \leq h_{2i+1} \end{cases}$ 其中，$ i=1,2,3,\cdots,n/2 $
  • 第一种情况称为大根堆，所有节点的值大于或等于左右子节点的值。第二种情况称为小根堆，所有节点的值小于或等于左右子节点的值
  • 堆排序最坏情况需要$ nlog_{2}n$次比较

赏

一只PHP开发的程序猿，偶尔搞搞摄影、画画、写作、顺便睡觉。

支付宝

微信