合肥做个网站多少钱,wordpress 标题属性,wordpress前台空白,自建网站系统MTK优美代码赏析6:电话本里的快速排序和插入排序算法 记得读书的时候学数据结构和一些程序基础的课程,学了很多的排序算法,当时感觉蛮有趣,也很简单,当大学的教育是以理论为主的,哪些教授们又没给咱举个实用的例子说明为什么要教我们这个,所以考完试就把这些没用的东东给忘了..… MTK优美代码赏析6:电话本里的快速排序和插入排序算法 记得读书的时候学数据结构和一些程序基础的课程,学了很多的排序算法,当时感觉蛮有趣,也很简单,当大学的教育是以理论为主的,哪些教授们又没给咱举个实用的例子说明为什么要教我们这个,所以考完试就把这些没用的东东给忘了... 最近为了实现自己的一个应用不得已去啃电话本,竟然发现里面有一个简单的不错的排序算法,只所以不错,是因为他所处架构的位置和作用我很清楚,但其内部的代码逻辑竟然一时没有看懂,汗! 当然电话本里排序的算法很多。这只是其中一个例子... 1.首先补习一下排序算法的基础,下班回家我在网上找了关于排序的资料,算法描述的很简单,但可能因为自己即将失业的缘故吧,有个别例子自己竟一时也没看懂,头大...希望各位看客不要象我一样荒废了大学交的学费啊! 冒泡排序 http://baike.baidu.com/view/254413.htm快速排序算法 http://baike.baidu.com/view/19016.htm插入排序 http://baike.baidu.com/view/396887.htm 2.然后看一看这个电话本排序算法的背景.电话本是任何的手机都应该具备的最基本的功能,他本身的存储和管理就已经比较复杂,还需要和通话,短信等联系在一起构成完整的系统,这里讲的就是里面最简单的需求:来电或来短信使要显示电话本里对应的姓名. 我们用的MTK平台又是如何实现这一需求的呢?写到这里就要从MTK电话本开机初始化写起,见网址http://blog.sina.com.cn/s/blog_64a85b990100hbiy.html. mmi_phb_ind_startup_read时系统逐一获得l4层给的电话本数据(SIM卡和手机里存的数据格式是一致的,都只存姓名和号码),通过mmi_phb_startup_read_entry写入PhoneBook[MAX_PB_ENTRIES]中,并用g_phb_name_index[MAX_PB_ENTRIES]来存储L4里对应号码索引store_index,用PhoneBookEntryCount来存储读出来的总数 读取完成后,mmi_phb_init_build_lookup_table里的mmi_phb_op_increase_lookup_table函数将从手机和sim卡中读取出来得姓名和号码插入将号码转化为数字的LookUpTable[MAX_LOOKUP_TABLE_COUNT]中 mmi_phb_init_populate_lookup_table,每隔500毫秒读取一次手机电话本内存储的号码拓展信息(公司号码,家庭号码等),并将有效的号码也转化为数字存入LookUpTable[MAX_LOOKUP_TABLE_COUNT]中. LookUpTable的出现很好的解决了来信息来电话显示号码对应姓名的问题,系统将这个结构数组以号码转化的数字(截取后几位,程序里可以指定这个位数)进行排序(今天讲的排序就是这个排序) typedef struct { U16 store_index; /* Store Index of Phonebook, Begin from 0 */ U32 number; } MMI_PHB_LOOKUP_NODE_STRUCT; 3. 通过获取来电号码,将来点号码转化为数字,然后在 LookUpTable中进行比对获取对应store_index,通过找到store_index在g_phb_name_index中的位置找到PhoneBook[MAX_PB_ENTRIES]中对应的姓名 LookUpTable加速了系统号码的匹配,MTK系统必须保持这个数组的排序性.系统在完成拓展号码读取后即用mmi_phb_lookup_table_sort进行对LookUpTable的排序.实际上对电话本的每一次增删改操作系统都会调用mmi_phb_lookup_table_sort对LookUpTable进行排序. 作者张素丰转载请注明出处http://www.cnblogs.com/zhangsufeng/archive/2010/09/26/1836353.html 4.下面看排序代码 //先看其切换节点的函数/***************************************************************************** * FUNCTION * mmi_phb_lookup_table_swap_node * DESCRIPTION * Swaps the look-up table nodes * PARAMETERS * i [IN] * j [IN] * RETURNS * void *****************************************************************************/void mmi_phb_lookup_table_swap_node(U16 i, U16 j){ /*----------------------------------------------------------------*/ /* Local Variables */ /*----------------------------------------------------------------*/ MMI_PHB_LOOKUP_NODE_STRUCT temp; /*----------------------------------------------------------------*/ /* Code Body */ /*----------------------------------------------------------------*/ memcpy(temp, LookUpTable[i], sizeof(MMI_PHB_LOOKUP_NODE_STRUCT)); memcpy(LookUpTable[i], LookUpTable[j], sizeof(MMI_PHB_LOOKUP_NODE_STRUCT)); memcpy(LookUpTable[j], temp, sizeof(MMI_PHB_LOOKUP_NODE_STRUCT));}//排序的main函数/***************************************************************************** * FUNCTION * mmi_phb_lookup_table_sort * DESCRIPTION * Sorts the look-up table * * This is a fast Quick-Sort as suggested by * Pluto. It will perform insertion sort for * array chunks of size less than 4 and quick * sort for size greater than 4. * PARAMETERS * void * RETURNS * void *****************************************************************************/void mmi_phb_lookup_table_sort(void){ /*----------------------------------------------------------------*/ /* Local Variables */ /*----------------------------------------------------------------*/ /*----------------------------------------------------------------*/ /* Code Body */ /*----------------------------------------------------------------*/ if (g_phb_cntx.lookup_table_count)//该标记纪录LookUpTable使用的实际长度 { /* Set to zero beore sorting, check if this flag larger than phonebook entries to see if finish sorting. */ g_phb_cntx.populate_count 0;//该标记纪录是否完成排序,为0xffff时完成排序 /* Begin to sort. */ //先用一次快速排序,在完成排序后,前端和后段中间一段各有6个元素没有排序 mmi_phb_lookup_table_quicksort(0, (U16) (g_phb_cntx.lookup_table_count - 1)); //再用一次插入排序主要对没有排序的那段排序 mmi_phb_lookup_table_insertionsort(0, (U16) (g_phb_cntx.lookup_table_count - 1)); /* After sorting, set it to total phonebook entries. */ g_phb_cntx.populate_count 0xffff;//完成排序 }}//快速排序/***************************************************************************** * FUNCTION * mmi_phb_lookup_table_quicksort * DESCRIPTION * Sorts the lookup table using quick sort algorithm * PARAMETERS * l [IN] * r [IN] * RETURNS * void *****************************************************************************/void mmi_phb_lookup_table_quicksort(U16 l, U16 r){ /*----------------------------------------------------------------*/ /* Local Variables */ /*----------------------------------------------------------------*/ U16 i, j; U32 pivot; /*----------------------------------------------------------------*/ /* Code Body */ /*----------------------------------------------------------------*/ if ((r - l) 4) { i (r l) / 2; if (LookUpTable[l].number LookUpTable[i].number) { mmi_phb_lookup_table_swap_node(l, i); } if (LookUpTable[l].number LookUpTable[r].number) { mmi_phb_lookup_table_swap_node(l, r); } if (LookUpTable[i].number LookUpTable[r].number) { mmi_phb_lookup_table_swap_node(i, r); } j r - 1; mmi_phb_lookup_table_swap_node(i, j); i l; pivot LookUpTable[j].number; for (;;) { do { } while (LookUpTable[i].number pivot); do { } while (LookUpTable[--j].number pivot); if (j i) { break; } mmi_phb_lookup_table_swap_node(i, j); } mmi_phb_lookup_table_swap_node(i, (U16) (r - 1)); mmi_phb_lookup_table_quicksort(l, j); mmi_phb_lookup_table_quicksort((U16) (i 1), r); }}//插入排序/***************************************************************************** * FUNCTION * mmi_phb_lookup_table_insertionsort * DESCRIPTION * Sorts the lookup table using insertion sort algorithm * PARAMETERS * lo [IN] * hi [IN] * RETURNS * void *****************************************************************************/void mmi_phb_lookup_table_insertionsort(U16 lo, U16 hi){ /*----------------------------------------------------------------*/ /* Local Variables */ /*----------------------------------------------------------------*/ U16 i, j; MMI_PHB_LOOKUP_NODE_STRUCT elem; /*----------------------------------------------------------------*/ /* Code Body */ /*----------------------------------------------------------------*/ for (i lo 1; i hi; i) { memcpy(elem, LookUpTable[i], sizeof(MMI_PHB_LOOKUP_NODE_STRUCT)); j i; while (j lo) { if (LookUpTable[j - 1].number elem.number) { break; } memcpy(LookUpTable[j], LookUpTable[j - 1], sizeof(MMI_PHB_LOOKUP_NODE_STRUCT)); j--; } memcpy(LookUpTable[j], elem, sizeof(MMI_PHB_LOOKUP_NODE_STRUCT)); }} posted on 2010-09-26 23:32 Anpher Zhang 阅读(...) 评论(...) 编辑 收藏 转载于:https://www.cnblogs.com/zhangsufeng/archive/2010/09/26/1836353.html
