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

總結

以上是生活随笔為你收集整理的MTK优美代码赏析6:电话本里的快速排序和插入排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。