锐客网

  1. 首页 > it技术 > >

软件设计师16-数据结构02（排序/查找）


软件设计师16-数据结构02（排序/查找）
文章图片
排序 1 衡量排序算法质量
1）时间效率：排序速度
2）空间效率：占内存辅助空间的大小
3）稳定性：相等的两个数，排序后次序不变
排序方法 1 插入排序 1）直接插入排序：将第二到n个序列，依次与前n个序列比较，逐个插入，直到整个序列有序（n-1趟）
1）时间复杂度：n的平方
2）空间复杂度：仅占用一个缓冲单元 O(1)
2）算法的稳定性：稳定
2）希尔排序：取正整数d1直接插入排序，迭代取d2 一般取d1=n/2，di+1=di/2（如果di/2<2，那么接下来分组di=1 ），如果结果为偶数，di+1
不稳定，序列不同，效率不同
选择排序 优：简单 劣：效率低
1）直接选择排序
从待排序数据中选择最小，存放于已排序列最后
2）堆排序
堆是满足下列性质的数列{r1,r2,...,rn
软件设计师16-数据结构02（排序/查找）
文章图片
小顶堆/大顶堆 小顶堆：根节点小于其左右子树


软件设计师16-数据结构02（排序/查找）
文章图片
堆排序：利用堆的特性对记录进行排序。将无序序列建成堆，取最小/大值置于根，取次小/大、次次小/大值置于左、右子树（无序）。循环
小顶堆输出：while{输出根
取最后的数置于根。
while(最小数不能下移){与左右节点比较，置换小的}
}
交换排序 【软件设计师16-数据结构02（排序/查找）】1）冒泡排序
循环{
从前到后，两两比较，大者置后
}
若顺序，则只需一趟；若逆序，则需要n-1趟
2）快速排序
对于r[0....n-1进行快速排序
选定基准元素x（一般选第一个），初始指针i=0+1；j=n-1。


while(i!=j){
j 从后往前搜寻小于x的数，
r[j]与x相颠倒。
i从前往后搜寻小于x的数
r[i]与x相颠倒。
}
//此时完成一趟循环（结果）：子序列1（小于x的数） x子序列2（大于x的数）
迭代循环子序列1 子序列2 （直到每个子序列长度为1）
归并排序 将一个长度为n的无序序列看成是n个长度为1 的有序序列
while(进行log2N次排序){
两两归并（排序）有序序列
}


软件设计师16-数据结构02（排序/查找）
文章图片
排序 查找 静态查找 1 顺序查找
1）查找方法：逐一比较、顺序查找。
2）性能：平均查找长度：(n+1)/2，时间效率O(n)
3）优：算法简单，适应面广，对表没有要求
4）缺点：n值较大时，平均查找长度大，效率低
2 折半查找/二分查找
1）查找方法：
数据排序
while(要查找元素!=中间值){
与中间值比较
大则选择前半部分
中间值=前半部分/2（如果前半部分%2=0，则中间值前移，否则向上取整）
小则选择后半部分
中间值=同上
}
2）平均查找长度：
3）要求顺序存储、按关键字有序排序。适用于不经常增删改的
3 分块查找/索引顺序查找
位于顺序查找和折半查找之间
1）把表分成若干块（保证块间有序（后一块的关键字（最大）大于与之紧邻的右侧那块的关键字（最大）））
2）按关键字建立索引表（关键字，块起始位置（1开始））
3）折半查找索引表，确定所处块
4）块内顺序查找
哈希表
1）查找方法：根据关键码值直接进行访问的数据结构
2）映射函数：散列函数；存放记录的数组：散列数组
3）优点：查找速度极快(O(1))，查找效率与元素个数无关
4）冲突：不同码值映射到同一位置
减少冲突：1）构造好的哈希函数：所选函数简单，提高运转速度；计算出的地址应在哈希地址中均匀分配，减少空间浪费
2）制定规则，在冲突发生时调整位置

    推荐阅读


    上一篇：内驱力，让孩子有活力地学习

    下一篇：Easy|Easy sleep-Music adjustment