集合

集合的操作：查找和排序

集合包括一下内容：

Chapter8 静态查找表
Chapter9 动态查找表：查找树，散列表
Chapter10 排序算法
Chapter11 外存储器上的查找和排序

集合的基本概念

集合中的数据元素除了属于同一集合之外，没有任何逻辑关系。
在集合中，每个数据元素有一个区别于其他元素的唯一标识，通常称为键值或关键字值
说人话，集合的元素是键值对（key-value）

集合元素的类型

template <class KEY, class OTHER>
struct SET {
    KEY key;
    OTHER other;
};

集合的主要运算

查找某一个元素
将集合集合中的元素按照它的唯一标识排序
（都是对key的操作）

集合的存储

任何容器都能存储集合
常用的表示形式是借鉴于线性表或树
唯一一个仅适合于存储和处理集合的数据结构是散列表

查找的基本概念

用于查找的集合称之为查找表
查找表的分类：
- 静态查找表
- 动态查找表
- 内部查找
- 外部查找
查找的结果：成功/不成功

静态查找表

数据元素的个数和值不允许变化的查找表称为静态查找表
不允许插入和删除
实例：字典
可以用顺序表seqList存储，或直接存储在C++的原始数组中

无序表的查找

无序表：数组中的元素是无序的
无序表的查找：只能做线性的顺序查找
时间复杂度O(N)
顺序查找的优化：利用哨兵减少n次比较

顺序查找代码

template <class KEY, class OTHER>
int seqSearch(SET<KEY, OTHER> data[], 
                       int size, const KEY &x) 
{
    data[0].key = x;
    for (int i = size ; x != data[i].key; --i);
    return i;
}

优化的小trick:把要查找的key放到根节点，省得每次循环检查是否越界

有序表的查找

有以下几种方法：

顺序查找
二分查找
插值查找
分块查找

二分查找

每次检查排在中间的那个元素
- 如中间元素等于要查找的元素，则查找完成
- 否则，确定要找的数据是在前一半还是在后一半，然后缩小范围，在前一半或后一半内继续查找。
时间复杂度O(logN)

代码：

template <class KEY, class OTHER>
int binarySearch(SET<KEY, OTHER> data[],
                            int size, const KEY &x) 
{
    int low = 1,  high = size, mid;
    while (low <= high ) {                 //查找区间存在
        mid = (low + high) / 2;         //计算中间位置
    if ( x == data[mid].key )  return mid; 
    if ( x < data[mid].key) high = mid - 1;
        else low = mid + 1;
    }	
    return 0;
}

插值查找

适用于数据分布比较均匀的情况查找位置估计
查找位置估计：
缺点：计算量大

适用情况：

访问一个数据元素必须比一个典型的指令费时得多。例如，数组可能在磁盘里而不是在内存里，而且每次比较都需要访问一次磁盘。
这些数据必须不仅有序，而且分布相当均匀，这可以使每次估计都相当准确，可以将大量的数据排除出查找范围。这样，花费这些计算代价是值得的

分块查找

分块查找也称为索引顺序块的查找。
是处理大量数据查找的一种方法。
它把整个有序表分成若干块，块内的数据元素可以是有序存储，也可以是无序的，但块之间必须是有序的。

时间分析

查找由两个阶段组成：查找索引和查找块。设表长为n，被分为m块，采用顺序查找，平均所需时间为

$\dfrac{m+1}{2}+\dfrac{\frac{n}{m}+1}{2} = \dfrac{m+\frac{n}{m}}{2} +1$

故易知当 $m = \sqrt{n}$ 时，平均时间最小= $\sqrt{n}+1$