iOS標(biāo)準(zhǔn)庫中常用數(shù)據(jù)結(jié)構(gòu)和算法之排序

上一篇：iOS系統(tǒng)中的常用數(shù)據(jù)結(jié)構(gòu)之鏈表

??排序

排序是指將亂序數(shù)組變?yōu)橛行蚺帕械奶幚怼OS提供了快速排序是钥、堆排序僻肖、歸并排序肖爵、并行排序、基數(shù)排序一共5種排序函數(shù)臀脏。具體每種排序的概念介紹請大家參考相關(guān)的文檔這里就不再贅述了劝堪。下面的表格將會從時間復(fù)雜度、穩(wěn)定性揉稚、是否需要分配額外內(nèi)存秒啦、是否對有序數(shù)組進(jìn)行優(yōu)化、應(yīng)用范圍搀玖、平臺支持6個維度來考察各種排序函數(shù)：

排序算法	時間復(fù)雜度	是否穩(wěn)定	是否需要分配額外內(nèi)存	是否對有序數(shù)組進(jìn)行優(yōu)化	應(yīng)用范圍	平臺支持
快速排序	N*logN	否	遞歸棧內(nèi)存	無	任意數(shù)組	POSIX
堆排序	N*logN	否	無	有	任意數(shù)組	BSD UNIX/iOS
歸并排序	N*logN	是	有	有	任意數(shù)組	BSD UNIX/iOS
并行排序	N*logN	否	有	無	任意數(shù)組	iOS
穩(wěn)定基數(shù)排序	N*D	是	有	無	字節(jié)串	BSD UNIX/iOS
不穩(wěn)定基數(shù)排序	N*D	否	無	無	字節(jié)串	BSD UNIX/iOS

一余境、快速、堆、歸并葛超、并行排序

功能：這四類排序函數(shù)的參數(shù)都是一致的暴氏，所以列在一起進(jìn)行介紹。
頭文件：#include <stdlib.h>
平臺：qsort被POSIX支持绣张、psort為iOS獨(dú)有、其他的都被BSD Unix支持
函數(shù)簽名：

//快速排序
void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
//快速排序block版本
void qsort_b(void *base, size_t nel, size_t width, int (^compar)(const void *, const void *));
//快速排序附加參數(shù)版本
void qsort_r(void *base, size_t nel, size_t width, void *thunk, int (*compar)(void *, const void *, const void *));

//堆排序
int heapsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
//堆排序block版本
int heapsort_b(void *base, size_t nel, size_t width, int (^compar)(const void *, const void *));

//歸并排序
int mergesort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
//歸并排序block版本
int mergesort_b(void *base, size_t nel, size_t width, int (^compar)(const void *, const void *));

//并行排序
void psort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
//并行排序block版本
void psort_b(void *base, size_t nel, size_t width, int (^compar)(const void *, const void *));
//并行排序附加參數(shù)版本
void psort_r(void *base, size_t nel, size_t width, void *thunk, int (*compar)(void *, const void *, const void *));

參數(shù)：
base:[in/out] 參與排序的數(shù)組的首地址关带。
nel:[in] 數(shù)組的元素的個數(shù)侥涵。
width:[in] 數(shù)組中每個元素的尺寸。
compar: [in] 函數(shù)比較器宋雏，排序時會通過對數(shù)組中的兩個元素調(diào)用函數(shù)比較器來判斷排序的順序芜飘。函數(shù)比較器的格式如下：

/*
@thunk: 函數(shù)比較器的附加參數(shù)，其值就是上述的帶附加參數(shù)版本的排序函數(shù)的thunk參數(shù)磨总。
@element1, element2: 元素在數(shù)組中的地址嗦明，這里需要注意的是這個參數(shù)不是元素本身，而是元素所在的數(shù)組中的偏移地址蚪燕。
@return: 如果比較結(jié)果相等則返回0, 如果element1在element2前返回小于0娶牌，如果element1在elemen2后面則返回大于0
*/
 int compar(const void *element1, const void *element2);
 //帶附加參數(shù)版本
 int compar(void *thunk, const void *element1, const void *element2);

return:[out] 對于堆排序和歸并排序來說有可能會排序失敗，如果排序成功會返回0否則返回非0馆纳，其他幾個函數(shù)則一定會排序成功诗良。

描述：

qsort函數(shù)是用于快速排序的函數(shù)，采用的是C.A.R. Hoare 所實(shí)現(xiàn)的快速排序算法鲁驶〖快速排序是一種不穩(wěn)定排序，排序速度最快钥弯，平均時間復(fù)雜度為O(N*logN)径荔，因?yàn)槠洳⑽磳τ行驍?shù)組進(jìn)行優(yōu)化處理，因此最差的時間可能是O(N^2)脆霎∽艽Γ快速排序內(nèi)部采用遞歸的機(jī)制進(jìn)行排序，因此沒有額外的內(nèi)存分配绪穆，當(dāng)然如果數(shù)組元素數(shù)量眾多則過度的遞歸可能會導(dǎo)致棧溢出辨泳，因此其內(nèi)部實(shí)現(xiàn)如果超過了約定的遞歸次數(shù)后就會轉(zhuǎn)化為堆排序。
heapsort函數(shù)是用于堆排序的函數(shù)玖院，采用的是J.W.J. William所實(shí)現(xiàn)的堆排序算法菠红。堆排序是一種不穩(wěn)定排序，其時間復(fù)雜度比較穩(wěn)定為O(N*logN)难菌。堆排序?qū)τ行驍?shù)組進(jìn)行優(yōu)化處理试溯。堆排序進(jìn)行排序時幾乎沒有附加內(nèi)存的分配和消耗處理。
mergesort函數(shù)是用于歸并排序的函數(shù)郊酒，歸并排序是一種穩(wěn)定的排序遇绞，平均時間復(fù)雜度為O(N*logN), 因?yàn)槠鋵τ行驍?shù)組進(jìn)行了優(yōu)化處理键袱，因此最好的時間可能達(dá)到O(N)。歸并排序的缺點(diǎn)是有可能會在排序?qū)崿F(xiàn)內(nèi)部分配大量的額外內(nèi)存(排序數(shù)組的尺寸)摹闽，所以不適合用在數(shù)組元素過多的排序中拜姿。
psort函數(shù)是用于并行排序的函數(shù)屡谐，這函數(shù)是iOS系統(tǒng)獨(dú)有的函數(shù)。并行排序也是一種不穩(wěn)定的排序。當(dāng)數(shù)組的元素數(shù)量小于2000或者CPU是單核時并行排序內(nèi)部使用快速排序qsort來實(shí)現(xiàn)赔硫，而當(dāng)數(shù)量大于2000并且是多核CPU時系統(tǒng)內(nèi)部會開辟多線程來執(zhí)行并行的排序處理英岭。因此當(dāng)數(shù)量眾多而且又希望能并行處理時可以用這個函數(shù)來進(jìn)行排序飒炎，當(dāng)然缺點(diǎn)就是排序時有線程創(chuàng)建和調(diào)度的開銷册赛。
上述的排序函數(shù)有_r結(jié)尾的表明是帶有附加參數(shù)的排序函數(shù)，這樣在比較器中就可以使用這個附加參數(shù)坐梯，從而實(shí)現(xiàn)一些擴(kuò)展的能力徽诲，這個就和帶_b結(jié)尾的用block進(jìn)行比較的元素比較能力是一樣。

示例代碼:

int compar(const void *element1, const  void *element2)
{
   //注意這里的element1,element2是元素在數(shù)組中的指針而非元素本身
    const char *p1 = *(const char **)element1;
    const char *p2 = *(const char **)element2;
    return strcmp(p1, p2);
}

void main()
{
     char *arr[6] = {"Bob","Max","Alice","Jone","Lucy","Lili"};
    
      qsort(arr, sizeof(arr)/sizeof(char*), sizeof(char*), compar); 
      heapsort(arr, sizeof(arr)/sizeof(char*), sizeof(char*), compar); 
      mergesort(arr, sizeof(arr)/sizeof(char*), sizeof(char*), compar); 
      psort(arr, sizeof(arr)/sizeof(char*), sizeof(char*), compar); 
}

基數(shù)排序

功能：基數(shù)排序是利用了排序元素取值的一些限制來進(jìn)行排序的排序方式吵血。因此基數(shù)排序并不能適用于任何的數(shù)據(jù)結(jié)構(gòu)谎替。就以系統(tǒng)提供的函數(shù)來說，目前只支持基于字節(jié)串?dāng)?shù)組(字節(jié)串包括字符串)的排序践瓷。系統(tǒng)為基數(shù)排序分別提供了穩(wěn)定和非穩(wěn)定兩種版本的排序函數(shù)院喜。要想更加詳細(xì)的了解基數(shù)排序請參考相關(guān)的文檔。

頭文件：#include <stdlib.h>, #include <limits.h>
平臺：BSD Unix
函數(shù)簽名：

//基數(shù)排序非穩(wěn)定版
int radixsort(const unsigned char **base, int nmemb, const unsigned char *table,unsigned endbyte);
//基數(shù)排序穩(wěn)定版,穩(wěn)定版排序會有double的附加內(nèi)存分配
int sradixsort(const unsigned char **base, int nmemb, const unsigned char *table,unsigned endbyte);

參數(shù)：
base: [in/out]: 字節(jié)串?dāng)?shù)組指針晕翠。
nmemb:[in] 字節(jié)串?dāng)?shù)組元素個數(shù)喷舀。
table:[in] 可以傳NULL或者一個長度為256的數(shù)組。因?yàn)橐粋€字節(jié)符號的編碼取值范圍是0-255淋肾，所以這個表中的每個元素的值就表明每個字節(jié)符號的比重值硫麻，其取值也是0-255。這個表用來決定基數(shù)字節(jié)串?dāng)?shù)組的排序是升序還是降序樊卓，如果表中的值分別是從0到255那么字節(jié)串就按升序排列拿愧，如果表中的值分別是從255到0則表示按降序排列。同時這個表還可以用來決定是否對字符的大小寫敏感碌尔，舉例來說對于字符A-Z以及a-z的字節(jié)編碼值不一樣浇辜，因此如果table中對應(yīng)位置的比重值不一樣那么就表示是大小寫敏感，而如果將表中對應(yīng)位置的比重值設(shè)置為一樣唾戚，那么就可以實(shí)現(xiàn)大小寫不敏感的排序了柳洋。具體的對table的使用將會在下面的例子中有詳細(xì)說明。如果我們不想自定義排序規(guī)則那么將這個參數(shù)傳遞NULL即可表明按升序進(jìn)行排序叹坦。
endbyte:[in] 每個字節(jié)串的結(jié)尾字節(jié)值熊镣，因?yàn)榛鶖?shù)排序不局限于字符串，也可以用在字節(jié)串上，所以需要有一個標(biāo)志來標(biāo)識每個字節(jié)或者字符串是以什么字節(jié)結(jié)尾的绪囱。默認(rèn)情況下的字符串一般都是以'\0'結(jié)尾测蹲，所以這個參數(shù)對于常規(guī)字符串來說傳0即可。
return:[out] 返回排序成功與否鬼吵，成功返回0扣甲，否則返回其他。

功能：

基數(shù)排序只能對字節(jié)串?dāng)?shù)組進(jìn)行排序齿椅，而不能對任意的數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序處理文捶，因此其排序具有一定的局限性∶娇龋基數(shù)排序的時間復(fù)雜度為O(N*D)，這里的D是指待排序字節(jié)串中最長的字節(jié)串的長度种远，因此基數(shù)排序幾乎接近于線性時間的長度了涩澡。
基數(shù)排序中的table表決定著基數(shù)排序的排序順序和結(jié)果。這個表所表達(dá)的每個字節(jié)編碼的比重值坠敷。因?yàn)樽止?jié)的編碼是從0到255妙同，而默認(rèn)的每個字節(jié)的比重值和編碼值相等，這樣就表明著字節(jié)串將按照編碼的大小進(jìn)行升序排列膝迎。
基數(shù)排序分為穩(wěn)定版本和不穩(wěn)定版本粥帚，二者的區(qū)別就是當(dāng)值相同時，是否會位置保持而不被交換限次。穩(wěn)定版基數(shù)排序的一個缺點(diǎn)就是會產(chǎn)生雙倍大小的額外內(nèi)存分配芒涡。

示例代碼1：

void main()
{
   char *arr[6] = {"Bob","Max","Alice","ada","lucy","Lili"};
    
    //默認(rèn)升序排列
    radixsort(arr, sizeof(arr)/sizeof(char*), NULL, '\0');
    
    //降序排列，這里需要構(gòu)建table表卖漫，其比重順序變?yōu)橛纱蟮叫　?    unsigned char table1[UCHAR_MAX + 1] = {0};
    for (int i = 0; i < UCHAR_MAX + 1; i++)
        table1[i] = UCHAR_MAX - i;    //每個字節(jié)編碼位置的比重值由大到小
    radixsort(arr, sizeof(arr)/sizeof(char*), table1, '\0');
    
    
    //大小寫不敏感升序排序费尽，這里需要構(gòu)建table表，將大寫字母和小寫字母的比重值設(shè)置為一致羊始。因?yàn)樯厦娴呐判騼?nèi)容只有字母符號所以只需要修改字母符號位置的比重值即可旱幼。
    unsigned char table2[UCHAR_MAX + 1] = {0};
    for (int i = 'A';i <= 'Z'; i++)
    {
        table2[i] = i;
        table2[i+32] = i;  //小寫部分的比重值也設(shè)置和大寫部分的比重值一致。
    }
    radixsort(arr, sizeof(arr)/sizeof(char*), table2, '\0');
}

示例代碼2：
雖然基數(shù)排序正常情況下只能用于字節(jié)串?dāng)?shù)組進(jìn)行排序突委，如果字節(jié)串是某個結(jié)構(gòu)體的成員時柏卤，我們希望整個結(jié)構(gòu)體也跟著排序。這時候就需要進(jìn)行結(jié)構(gòu)體的特殊設(shè)計(jì)匀油，我們需要將結(jié)構(gòu)體的第一個數(shù)據(jù)成員設(shè)置為字節(jié)串?dāng)?shù)組即可實(shí)現(xiàn)將結(jié)構(gòu)體來應(yīng)用基數(shù)排序缘缚。具體的代碼如下：

//對結(jié)構(gòu)體的排序。要求字符串作為結(jié)構(gòu)體的第一個成員钧唐，而且字符串成員必須是數(shù)組忙灼，而不能是字符串指針。
    typedef struct student
    {
        char name[16];    //結(jié)構(gòu)體中字符串必須以數(shù)組的形式被定義并且作為第一個數(shù)據(jù)成員。
        int age;
    }student_t;
    
    student_t *a1 = malloc(sizeof(student_t));
    strcpy(a1->name, "Bob");
    a1->age = 10;
    
    student_t *a2 = malloc(sizeof(student_t));
    strcpy(a2->name, "Jone");
    a2->age = 15;
    
    student_t *a3 = malloc(sizeof(student_t));
    strcpy(a3->name, "Alice");
    a3->age = 12;
    
    student_t *a4 = malloc(sizeof(student_t));
    strcpy(a4->name, "Tom");
    a4->age = 12;
    
    student_t *a5 = malloc(sizeof(student_t));
    strcpy(a5->name, "Lucy");
    a5->age = 8;
    
    student_t *a6 = malloc(sizeof(student_t));
    strcpy(a6->name, "Lily");
    a6->age = 18;
    
    student_t *arr[6] = {a1,a2,a3,a4,a5,a6};
    radixsort(arr, 6, NULL, '\0');

下一篇：iOS標(biāo)準(zhǔn)庫中常用數(shù)據(jù)結(jié)構(gòu)和算法之二叉排序樹

歡迎大家訪問歐陽大哥2013的github地址和簡書地址