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);????????????if?(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));????}}
?
?
|
|
