-
-
Notifications
You must be signed in to change notification settings - Fork 718
排序和查找算法的使用
ruki edited this page Feb 27, 2015
·
4 revisions
TBOX提供了各种常用算法,对容器中的元素进行各种操作,这里主要介绍下排序和查找算法。
排序算法目前支持如下几种:
- 快速排序:tb_quick_sort
- 堆排序: tb_heap_sort
- 插入排序:tb_bubble_sort
- 冒泡排序:tb_insert_sort
并且提供通用的tb_sort接口,对各种排序算法进行自动适配,使得任何情况下,性能都是最优的。 例如:
- 对具有随机迭代特性的容器,采用库快速排序来优化
- 对具有随机迭代特性,并且是超大规模的容器,采用堆排序
- 对只能线性迭代的容器采用冒泡排序
所以一般情况下,只需要调用tb_sort就行了
// 初始化一个vector,元素类型为tb_long_t, 满256个元素自动增长
tb_vector_ref_t vector = tb_vector_init(256, tb_element_long());
if (vector)
{
// 插入一些元素
tb_vector_insert_tail(vector, (tb_cpointer_t)10);
tb_vector_insert_tail(vector, (tb_cpointer_t)2);
tb_vector_insert_tail(vector, (tb_cpointer_t)5);
tb_vector_insert_tail(vector, (tb_cpointer_t)6);
tb_vector_insert_tail(vector, (tb_cpointer_t)9);
// 排序所有,第二个参数是比较器函数,默认使用容器内置的比较器
tb_sort_all(vector, tb_null);
// 释放vector
tb_vector_exit(vector);
}
对于查找算法,目前提供:
- 线性查找: tb_find
- 反向线性查找:tb_rfind
- 二分法查找: tb_binary_find
如果容器具有随机迭代特性,你就可以使用二分查找来优化,例如:vector、原生数组等等。。
// 初始化一个vector,元素类型为tb_long_t, 满256个元素自动增长
tb_vector_ref_t vector = tb_vector_init(256, tb_element_long());
if (vector)
{
// 插入一些有序元素
tb_vector_insert_tail(vector, (tb_cpointer_t)1);
tb_vector_insert_tail(vector, (tb_cpointer_t)2);
tb_vector_insert_tail(vector, (tb_cpointer_t)4);
tb_vector_insert_tail(vector, (tb_cpointer_t)6);
tb_vector_insert_tail(vector, (tb_cpointer_t)9);
// 使用二分查找法,快速查找元素,算法复杂度O(log2)
tb_size_t itor = tb_binary_find_all(vector, (tb_cpointer_t)5);
if (itor != tb_iterator_tail(vector))
{
// 获取元素值:5
tb_size_t value = tb_iterator_item(vector, itor);
}
// 释放vector
tb_vector_exit(vector);
}
你也可以指定谓词函数,来更灵活的进行查找。
// 初始化一个vector,元素类型为tb_long_t, 满256个元素自动增长
tb_vector_ref_t vector = tb_vector_init(256, tb_element_long());
if (vector)
{
// 插入一些有序元素
tb_vector_insert_tail(vector, (tb_cpointer_t)1);
tb_vector_insert_tail(vector, (tb_cpointer_t)2);
tb_vector_insert_tail(vector, (tb_cpointer_t)4);
tb_vector_insert_tail(vector, (tb_cpointer_t)6);
tb_vector_insert_tail(vector, (tb_cpointer_t)9);
/* 通过内置的tb_predicate_leq(<=)谓词函数,进行查找元素
*
* 目前的内置谓词有:
* tb_predicate_le(<)
* tb_predicate_eq(==)
* tb_predicate_be(<)
* tb_predicate_leq(<=)
* tb_predicate_beq(>=)
*
* 当然你也可以自定义一个自己的谓词函数,只要满足如下原型就行了:
* tb_bool_t (*tb_predicate_ref_t)(tb_iterator_ref_t iterator, tb_cpointer_t item, tb_cpointer_t value);
*
* 如果你看到算法名带有_if后缀,基本上都是可以传递谓词函数的,例如:
* tb_find_all_if
* tb_rfind_all_if
* tb_count_if
* tb_remove_if
* tb_remove_first_if
*
* 注:
* tb_binary_find_all_if 目前是不支持谓词的,但是可以指定一个自定义的比较器
*/
tb_size_t itor = tb_find_all_if(vector, tb_predicate_leq, (tb_cpointer_t)5);
if (itor != tb_iterator_tail(vector))
{
// 获取元素值:5
tb_size_t value = tb_iterator_item(vector, itor);
}
// 释放vector
tb_vector_exit(vector);
}
原生的数组也是可以使用算法进行比较的,下面给个比较常用的查找例子
注: 这里用了二分查找,因此不能使用谓词函数,只能使用比较器函数
// 定义一个字符集操作的数据结构
typedef struct __tb_charset_t
{
tb_size_t type;
tb_char_t const* name;
tb_long_t (*get)(tb_static_stream_ref_t sstream, tb_bool_t be, tb_uint32_t* ch);
tb_long_t (*set)(tb_static_stream_ref_t sstream, tb_bool_t be, tb_uint32_t ch);
}tb_charset_t;
// 定义一个原生数组
static tb_charset_t charsets[] =
{
{TB_CHARSET_TYPE_ASCII, "ascii", tb_charset_ascii_get, tb_charset_ascii_set }
, {TB_CHARSET_TYPE_GB2312, "gb2312", tb_charset_gb2312_get, tb_charset_gb2312_set }
, {TB_CHARSET_TYPE_GBK, "gbk", tb_charset_gb2312_get, tb_charset_gb2312_set }
, {TB_CHARSET_TYPE_ISO8859, "iso8859", tb_charset_iso8859_get, tb_charset_iso8859_set }
, {TB_CHARSET_TYPE_UCS2, "ucs3", tb_charset_ucs2_get, tb_charset_ucs2_set }
, {TB_CHARSET_TYPE_UCS4, "ucs4", tb_charset_ucs4_get, tb_charset_ucs4_set }
, {TB_CHARSET_TYPE_UTF16, "utf16", tb_charset_utf16_get, tb_charset_utf16_set }
, {TB_CHARSET_TYPE_UTF32, "utf32", tb_charset_utf32_get, tb_charset_utf32_set }
, {TB_CHARSET_TYPE_UTF8, "utf8", tb_charset_utf8_get, tb_charset_utf8_set }
};
// 按名字查找比较函数
static tb_long_t tb_charset_comp_by_name(tb_iterator_ref_t iterator, tb_cpointer_t item, tb_cpointer_t name)
{
return tb_stricmp(((tb_charset_ref_t)item)->name, (tb_char_t const*)name);
}
// 将原生的数组,初始化成一个迭代器
tb_array_iterator_t array_iterator;
tb_iterator_ref_t iterator = tb_iterator_make_for_mem(&array_iterator, charsets, tb_arrayn(charsets), sizeof(tb_charset_t));
// 针对这个迭代器根据名字进行二分法查找
tb_size_t itor = tb_binary_find_all_if(iterator, tb_charset_comp_by_name, "utf8");
// 如果找到
if (itor != tb_iterator_tail(iterator))
{
// 获取元素对象
tb_charset_t* charset = (tb_charset_t*)tb_iterator_item(iterator, itor);
}
注:上面的例子摘录自TBOX库内部的代码,仅供参考,不能直接copy使用。