文档介绍：数据结构与算法
算法
查找
查看文档:
为了分析实施键比较的算法和性能,我们应该使用键比较次数作为算法所做工作量的度量标准。
顺序查找
平均比较次数为 n(n+1)/2n;
二分查找
一、前置条件
操作对象为有序表。
二、算法描述
between bottom and top
middle = (bottom + top)/2;
if target > middle
 bottom = middle + 1;
 repeat the above process
else
 top = middle;
 repeat the above process
end if
查找树
2-树
二叉查找树
查看文档: 13351072_郑泽丰_11_1\
The plexity of a search, insert, or delete operation is O(logn), while the worst-plexity isO(height) = O(n), where nis number of nodes/elements.
递归实现
用递归的思想实现插入、搜索和删除等操作。
Remove From A Degree 2 Node。Replace with largest key in left subtree (or smallest in right subtree).
数组实现
查看文档: 13351072_郑泽丰_11_2\
链表实现
红黑树
Colored Nodes Definition
•Binary search tree.
•Each node is colored redor black.
•Root and all external nodes are black.
•No root-to-external-node path has two consecutive red nodes.
•All root-to-external-node paths have the same number of black nodes
词典查找树
插值查找
外部查找
B-树
排序
查看文档:
插入排序
查看文档:
算法描述
假定n是数组的长度,
首先假设第一个元素被放置在正确的位置上,这样仅需从1-n-1范围内对剩余元素进行排序。对于每次遍历,从0-i-1范围内的元素已经被排好序,
每次遍历的任务是:通过扫描前面已排序的子列表,将位置i处的元素定位到从0到i的子列表之内的正确的位置上。
将arr[i]复制为一个名为target的临时元素。
向下扫描列表,比较这个目标值target与arr[i-1]、arr[i-2]的大小,依次类推。
这个比较过程在小于或等于目标值的第一个元素(arr[j])处停止,或者在列表开始处停止(j=0)。
在arr[i]小于前面任何已排序元素时,后一个条件(j=0)为真,
因此,这个元素会占用新排序子列表的第一个位置。
在扫描期间,大于目标值target的每个元素都会向右滑动一个位置(arr[j]=arr[j-1])。
一旦确定了正确位置j,
目标值target(即原始的arr[i])就会被复制到这个位置。
与选择排序不同的是,插入排序将数据向右滑动,并且不会执行交换。
效率分析
稳定
空间复杂度O(1)
时间复杂度O(n2)
最差情况:反序,需要移动n*(n-1)/2个元素
最好情况:正序,不需要移动元素
数组在已排序或者是“近似排序”时,插入排序效率的最好情况运行时间为O(n);
插入排序最坏情况运行时间和平均情况运行时间都为O(n2)。
通常,插入排序呈现出二次排序算法中的最佳性能。
对于具有较少元素(如n<=15)的列表来说,二次算法十分有效。
在列表已被排序时,插入排序是线性算法O(n)。
在列表“近似排序”时,插入排序仍然是线性算法。
在列表的许多元素已位于正确的位置上时,就会出现“近似排序”的条件。
通过使用O(nlog2n)效率的算法(如快速排序)对数组进行部分排序,
然后再进行选择排序,某些高级的排序算法就是这样实现的。
数组版
template<class Record>
void Sortable_list<Record>::insertion_sort()
{
int first_unsorted;
int position;
Record current;
for(first_unsorted=1;frst_unsorted