哈希结构      摘要: 哈希结构

C++博客 Alex-Lee 2009-10-21

哈希结构在处理大量数据时具有很好的优势，在插入，查询，删除等操作上具有常量的时间复杂度O(1)。使用范围是数据集具有自然数上的关键字域（不是自然数也需要能够转为自然数域），通过哈希函数将关键字映射到寻址数组的槽。由于关键字域U[0...n]与寻址数组[0...m]中，总是n>m，也就是说，总有多个关键字对应一个槽。这个碰撞就需要通过一些方法改变。可以通过拉链法（链表法）和开放地址法。对于拉链法中，链表不能太长，否则影响速度，最好控制在10个元素之内，这样就要去寻址数组长度m>= n/10，这样就会多消耗些空间。为了让每个链表长度基本一致，就需要  阅读全文

快速排序算法、计数排序算法      摘要: 快速排序算法、计数排序算法

C++博客 Alex-Lee 2009-10-20

快速排序是分治算法，将数组分为几部分，在各部分内完成排序，递归排序。算法时间复杂度O(nlgn)。这是比较排序算法中速度最快的一个算法了。计数排序、基数排序、桶排序算法是非比较排序算法，他们的算法复杂度是O(n)。快速排序算法在选取支点上要有技巧，最好能达到随即要求。
  阅读全文

优先级队列      摘要: 优先级队列

C++博客 Alex-Lee 2009-10-18

上篇随笔谈到了堆结构的一个应用就是堆排序算法，虽然堆排序算法性能不错，但是比起快速排序算法还是有些差距。但是堆结构的另外一个应该就比较广泛了，就是优先级队列。
优先级队列有3中操作：插入(O(lgn))，最大最小值(O(1)),删去最大最小值(O(lgn))。其算法性能很好，在优先级调度作业上应用比较广泛。基于优先级的调度算法中，基于堆结构的实现算法是一个比较好选择。在事件驱动的仿真器中也有应用。  阅读全文

堆排序算法      摘要: 堆排序算法

---------- C++博客 Alex-Lee 2009-10-15

（二叉）堆结构是一种数组对象，它可以被视为一颗完全二叉树。算法时间复杂度O(nlgn)，具有插入排序和合并排序的优点。堆结构满足堆性质：对除根以外的每个节点i,满足A[PARENT(i)] >= A[i]。

堆排序算法实现有三个部分完成：
1，保持堆性质函数heap_ify;
2,构建堆函数build_heap;
3,堆排序函数 heap_sort;
另外，在优先级队列中有extract-max 过程和insert过程，在作业队列中常用，比如消息队列。这部分在优先级排序中说明。
  阅读全文