文档章节

排序和查找算法的使用

ruki
 ruki
发布于 2014/09/20 16:30
字数 909
阅读 184
收藏 9

TBOX提供了各种常用算法,对容器中的元素进行各种操作,这里主要介绍下排序和查找算法。

排序算法目前支持如下几种:

  1. 快速排序:tb_quick_sort
  2. 堆排序: tb_heap_sort
  3. 插入排序:tb_bubble_sort
  4. 冒泡排序:tb_insert_sort

并且提供通用的tb_sort接口,对各种排序算法进行自动适配,使得任何情况下,性能都是最优的。 例如:

  1. 对具有随机迭代特性的容器,采用快速排序来优化
  2. 对具有随机迭代特性,并且是超大规模的容器,采用堆排序
  3. 对只能线性迭代的容器采用冒泡排序

所以一般情况下,只需要调用tb_sort就行了

// 初始化一个vector,元素类型为tb_long_t, 满256个元素自动增长
tb_vector_ref_t vector = tb_vector_init(256, tb_item_func_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);
}

对于查找算法,目前提供:

  1. 线性查找: tb_find
  2. 反向线性查找:tb_rfind
  3. 二分法查找: tb_binary_find

如果容器具有随机迭代特性,你就可以使用二分查找来优化,例如:vector、原生数组等等。。

// 初始化一个vector,元素类型为tb_long_t, 满256个元素自动增长
tb_vector_ref_t vector = tb_vector_init(256, tb_item_func_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);
}

你也可以指定比较器函数,来更灵活的进行查找。

// 按降序比较函数
static tb_long_t your_comp_func(tb_iterator_ref_t iterator, tb_cpointer_t ltem, tb_cpointer_t rtem)
{
    return ((tb_long_t)ltem < (tb_long_t)rtem? 1 : ((tb_long_t)ltem > (tb_long_t)rtem? -1 : 0));
}

// 初始化一个vector,元素类型为tb_long_t, 满256个元素自动增长
tb_vector_ref_t vector = tb_vector_init(256, tb_item_func_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_size_t itor = tb_binary_find_all_if(vector, your_comp_func, tb_null);
    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_iterator_t iterator = tb_iterator_init_mem(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使用。


本文转载自:http://tboox.org/cn/2016/02/04/algorithm-sort-find/

ruki

ruki

粉丝 72
博文 105
码字总数 29037
作品 7
松江
高级程序员
私信 提问
一份不错的php面试题(附答案)

一份不错的php面试题,附答案,有准备换工作的同学可以参考一下. 一、基础题 1. 写出如下程序的输出结果 <?php $str1 = null; $str2 = false; echo $str1==$str2 ? '相等' : '不相等'; $str3 ......

斑驳
2014/08/17
39.7K
5
怎么判断那种排序算法和查找算法更适用当前

排序和查找算法那麽多,但是那些方法更好? 那些方法更有优势? 自己应该主要掌握那几张算法 ? 或者自己当前的数据应该怎么排序或者查找? 今天我们来对应一个实际问题来搭配使用排序算法以...

KiTok
2017/11/07
0
0
Unity 游戏中 排序算法和查找算法记录

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/KiTok/article/details/78470287 Hello ,I am Edwin 首先谢谢大家的支持,其次如果你碰到什么其他问题的话,欢...

KitStar
2017/11/07
0
0
导师计划--数据结构和算法系列(下)

数据结构和算法系列的课程分为上下两篇文章,上篇文章主要是讲解数据结构,可以戳导师计划--数据结构和算法系列(上)进行了解。本篇文章主要讲解的是基本算法,辅助的语言依旧是。POST的本篇...

call_me_R
04/07
0
0
算法知识梳理(6) - 数组第三部分

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

读书笔记:深入理解ES6 (五)

第五章 解构:使数据访问更便捷 第1节 为什么使用解构功能?   在ES5中,开发者们从对象、数组中获取特定数据并赋值给变量,编写了很多看起来同质化的代码。例如: 1 let options = {2 ...

张森ZS
11分钟前
10
0
CentOS7 yum方式安装MySQL5.7

在CentOS中默认安装有MariaDB,这个是MySQL的分支,但为了需要,还是要在系统中安装MySQL,而且安装完成之后可以直接覆盖掉MariaDB。 1 下载并安装MySQL官方的 Yum Repository [root@localho...

roockee
20分钟前
7
0
Allegro三种自定义设置快捷键的方法

Allegro自定义设置快捷键的三种方法: 1、在Allegro PCB editor 命令窗口直接定义 2、通过修改用户变量env文件来设置快捷键 3、定义笔画为快捷键 1、在Allegro PCB editor 命令窗口直接定义 ...

demyar
24分钟前
12
0
如何做一张能让人眼前一亮的大屏?

作为在职场驰骋的社会人,提到数据可视化大家应该都不陌生了。数据可视化的作用也不用我多说,主要是利用图形化手段,更清晰直观地将数据展示。多层次、交互式的可视化分析能够方便决策者理解...

朕想上头条
25分钟前
7
0
TL138/1808/6748-EthEVM开发板硬件CPU、FLASH、RAM

TL138/1808/6748-EthEVM是广州创龙基于SOM-TL138/1808/6748核心板开发的一款开发板,具有三个网络接口。由于SOM-TL138/1808/6748核心板管脚兼容,所以此三个核心板共用同一个底板。开发板采用...

Tronlong创龙
29分钟前
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部