广西免费网站制作,学校建网站,微信小程序商城完整源码,对对联的网站数据结构 查找和排序 3月12日 – 天气#xff1a;晴
1. 顺序查找 顺序查找就是简单的从头一个一个的进行比较#xff0c;注意它的平均查找长度 2. 折半查找 折半查找和二叉排序树一致#xff1a; 优点#xff1a;查找效率很高 缺点#xff1a;要求必须是循序存储并且表中…数据结构 查找和排序 3月12日 – 天气晴
1. 顺序查找 顺序查找就是简单的从头一个一个的进行比较注意它的平均查找长度 2. 折半查找 折半查找和二叉排序树一致 优点查找效率很高 缺点要求必须是循序存储并且表中元素必须有序 3. 分块查找 分块查找实际上是结合了折半查找和顺序查找两种方式。 注意ASL的计算方式 优点查找效率高于顺序查找低于折半查找 4. 哈希表 使用取余的方法需要注意取余的值 取余的那个值 大于等于元素个数小于等于比当前个数大的第一个质数。假设元素个数为9则m的取值范围为【911】 采用链地址法的优点和不足 优点平均查找长度短缺点需要存储大量的指针导致空间的浪费 5. 直接插入排序 思想直接插入排序的思想是向序列分为有序序列和无序序列。每次都从无序序列中取出一个值然后跟有序序列的值一次进行比较找到和事的位置进行插入。 确定性因此插入排序中在未完成时没有一个元素的值时确定的。 稳定性稳定的 时间复杂度最好的情况下只需要比较n-1次最坏的情况是n^2 空间复杂度1 6. 希尔排序 思想希尔排序是直接插入排序的改进。它首先将元素进行分组在组内进行直接插入排序随着增量的逐渐减小最终使得整个序列都有序确定性不确定稳定性不稳定时间复杂度n^1.3空间复杂度1 希尔排序最后一次排序为直接插入排序 7. 冒泡排序 思想两两比较元素将如果次序相反则交换。这样每一轮排序都会选出最大的或者最小的元素直到所有的元素都有序稳定性稳定确定性确定每一次都会选择出最大的元素且该元素的位置不会再次发生变化时间复杂度 n^2空间复杂度 1 8. 快速排序 思想在序列中任意选择一个元素然后以这个元素为基准将小于它的元素都放在它的左边大于它的都放在右边。然后生成两个子序列。然后这两个子序列再一次执行上述操作。直到序列中只有一个元素稳定性不稳定确定性每次所选择的这个元素的位置是固定的时间复杂度nlog空间复杂度log 递归 9. 简单选择排序 思想每次从带排序的序列中找到最小的元素然后放在有序序列末尾。这里注意和直接插入排序区分。直接插入的思想是每一次都从未排序的序列中选择一个元素然后放到已经排序序列里面的合适的位置稳定性不稳定确定性确定时间复杂度 n^2空间复杂度1
