2.3 归并排序
接口定义：
int merge(void* data, int esize, int lpos, int dpos, int rpos,
int (*compare)(const void* key1, const void* key2));
返回值：成功 0；失败 -1。
int merge_sort(void* data, int size, int esize,
int lpos, int rpos, int (*compare)(const void* key1, const void* key2));
返回值：成功 0；失败 -1。
算法描述：
归并排序是另一种利用分治法排序的算法，其首先将数据集二等分为左右两个区间，分别在左右区间上递归地使用归并排序算法，然后将排序后的两个区间合并为一个有序区间。与快速排序一样，它依赖于元素之间的比较。归并排序的归并过程就是合并两个已经排好序的数据集合，此时对需要合并的元素遍历一次即可，非常高效，因此，归并排序在所有的情况下都能达到快速排序的平均性能。但是，其主要的缺点是排序过程需要额外的存储空间来支持，因为合并过程不能在无序数据集本身中进行，因此需要两倍于无序数据集的空间来运行算法，这也就极大地降低了实际中使用归并排序的频率，反而由快速排序取代它的工作。接口中的lpos、dpos、rpos分别表示一个区间的左端、中间、右端位置。
算法分析：
归并排序本质上就是将一个无序数据集分割成许多只包含一个元素的集合，然后按序将这些小集合合并为大集合，直到生成一个最大的有序数据集为止。由于归并过程需要额外的存储空间，所以merge_sort()要为合并过程分配足够多的内存，在排序结束时，将归并后的结果复制到data中。归并的关键部分就是merge()函数，其余部分都可以递归地完成。merge将data中lpos到dpos，dpos + 1到rpos这两个有序小区间合并为data中的lpos到rpos这个有序区间中，中间使用了额外的存储空间m。由于归并元素需要不断地二分区间，因此，需要lgn级分割。对于两个包含p和q个元素的有序区间的合并，由于需要遍历全部元素，因此需要的合并时间为O(p + q)。在每个分割级别下，恰好都需要合并所有元素一次（即需要遍历全部n个元素一次），因此，归并算法的时间复杂度为O(nlgn)，此外，在不进行算法改进的情况下，需要两倍于无序数据集的存储空间，因此可以认为是O(n)。
算法实现：
1 /** 2 merge(): 3 return: success 0; fail -1 4 */ 5 int merge(void* data, int esize, int lpos, int dpos, int rpos, 6 int (*compare)(const void* key1, const void* key2)) 7 { 8 char* pd = (char*)data; 9 char* m;10 int pl, pr, pm;11 12 /* 初始化指示器 */13 pl = lpos; /* pl指向分割后的左分区 */14 pr = dpos + 1; /* pr指向分割后的右分区 */15 pm = 0; /* pm指向合并后的分区 */16 17 /* 分配归并后结果的存储空间 */18 if((m = (char*)malloc((rpos - lpos + 1) * esize)) == NULL)19 return -1;20 21 /* 两个区间中仍然有需要合并的元素 */22 while(pl <= dpos || pr <= rpos)23 {24 if(pl > dpos)25 {26 /* 左分区元素已经全部合并 */27 while(pr <= rpos) /* 此时将右分区剩下的元素全部接在m的后边 */28 {29 memcpy(&m[pm * esize], &pd[pr * esize], esize);30 pr++;31 pm++;32 }33 continue;34 }35 else if(pr > rpos)36 {37 /* 右分区元素已经全部合并 */38 while(pl <= dpos) /* 此时将左分区剩下的元素全部接在m的后边 */39 {40 memcpy(&m[pm * esize], &pd[pl * esize], esize);41 pl++;42 pm++;43 }44 continue;45 }46 47 /* 将下一个有序集合添加到合并结果中 */48 if(compare(&pd[pl * esize], &pd[pr * esize]) < 0)49 {50 memcpy(&m[pm * esize], &pd[pl * esize], esize);51 pl++;52 pm++;53 }54 else55 {56 memcpy(&m[pm * esize], &pd[pr * esize], esize);57 pr++;58 pm++;59 }60 }61 62 /* 复制合并结果到data中，然后释放m */63 memcpy(&pd[lpos * esize], m, (rpos - lpos + 1) * esize);64 65 /* 释放空间 */66 free(m);67 68 return 0;69 } 1 /** 2 merge_sort(): 3 return: success 0; fail -1 4 */ 5 int merge_sort(void* data, int size, int esize, 6 int lpos, int rpos, int (*compare)(const void* key1, const void* key2)) 7 { 8 int dpos; 9 if(lpos < rpos)10 {11 /* 计算中间位置 */12 dpos = (int)((lpos + rpos - 1) / 2);13 14 /* 递归地对左分区进行归并排序 */15 if(merge_sort(data, size, esize, lpos, dpos, compare) < 0)16 return -1;17 18 /* 递归地对右分区进行归并排序 */19 if(merge_sort(data, size, esize, dpos + 1, rpos, compare) < 0)20 return -1;21 22 /* 合并已经排好序的左右分区 */23 if(merge(data, esize, lpos, dpos, rpos, compare) < 0)24 return -1;25 }26 27 return 0;28 }
2.4 计数排序
接口定义：
int counts_sort(int* data, int size, int pnumbers);
返回值：成功 0；失败 -1。
算法描述：
计数排序是一种高效的线性排序,该算法不需要进行元素比较操作,而是通过计算数据集中元素出现的次数来确定该元素在有序集合中的正确偏移位置，其效率一般高于基于比较操作的O(nlgn)。接口中的pnumbers表示数据集中可能出现的元素个数，为最大值加1，比如：最大值为9意味着可能有0~9存在，因此pnumbers设为10。计数排序需要利用一个索引数组来记录各个元素的出现次数，如此，也就限制了计数排序只能对”可计算元素”进行排序。data数据集中的size个元素经过counts_sort()后将变得有序。
算法分析：
计数排序本质上就是通过计算无序数据集中每个元素出现的次数，将其转换为有序数据集中的偏移量来指导排序过程的。设计时需要定义一个索引数组counts，索引本身代表数据集中可能出现的值。而通过与前一个索引元素的相加即可得到当前索引的在有序数据集中的偏移量（注：如果有多个重复的元素，则为最后一个位置的偏移量）。接着，将索引元素按照偏移量插入到temp中，插入后对应的偏移量减1，表示已插入了一个重复的元素，再一次插入该元素时偏移指针向前移动一个单位。由于算法中包含三个循环，其中两个都为O(n)，一个为O(p)，因此时间复杂度为O(n + p)；由于用到了额外的数组temp与counts，因此需要多分配一些内存空间，大致可以记为O(n)。
算法实现：
1 /** 2 counts_sort(): 3 return: success 0; fail -1 4 */ 5 int counts_sort(int* data, int size, int pnumbers) 6 { 7 int* counts; 8 int* temp; 9 int value, i;10 11 /* 分配计数数组counts的存储空间 */12 if((counts = (int*)malloc(pnumbers * sizeof(int))) == NULL)13 return -1;14 15 /* 分配存储排序后元素的临时空间 */16 if((temp = (int*)malloc(size * sizeof(int))) == NULL)17 return -1;18 19 /* 初始化counts */20 for(value = 0; value < pnumbers; value++)21 counts[value] = 0;22 23 /* 计算每个元素出现的次数 */24 for(i = 0; i < size; i++)25 counts[data[i]] = counts[data[i]] + 1;26 27 /* 更新counts数组，使得其值代表对应元素在排序后的偏移量 */28 for(i = 1; i < pnumbers; i++)29 counts[i] = counts[i] + counts[i - 1];30 31 /* 使用更新后counts中的偏移量计算每个元素的正确位置 */32 for(i = size - 1; i >= 0; i--)33 {34 temp[counts[data[i]] - 1] = data[i]; /* 多个重复的值总是从后向前依次放置 */35 printf("temp[%d] stores %d\n", counts[data[i]] - 1, data[i]);36 counts[data[i]] = counts[data[i]] - 1;37 }38 39 /* 将排序后的数据集复制到data中 */40 memcpy(data, temp, size * sizeof(int));41 42 free(temp);43 free(counts);44 45 return 0;46 }
2.5 基数排序
接口定义：
int radix_sort(int* data, int size, int bits, int radix);
返回值：成功 0；失败 -1。
算法描述：
基数排序是另外一种高效的线性排序方法。其将数据按位分离，并从数据的最低有效位到最高有效位依次进行排序，从而得到有序数据集合。但是对某个位进行排序时必须选择稳定的排序算法。基数排序并不局限于对整型数据进行排序，凡是将元素分割为整型的，就可以使用它。基数的选择依赖于数据本身，例如以28为基对字符串进行排序，以10为基对整型进行排序...。bits表示每个待排元素包含的位数，radix表示基数。
算法分析：
基数排序实质上就是对元素的每一位进行计数排序，因此其时间复杂度为O(b(n + r))，其中n为数据集中元素个数，r为基数radix，b为每个元素的位数bits；其空间复杂度与计数排序一样，需要额外的temp和counts，大致可以记为O(n)。
算法实现：
1 /** 2 radix_sort(): 3 return: success 0; fail -1 4 */ 5 int radix_sort(int* data, int size, int bits, int radix) 6 { 7 int* counts; 8 int* temp; 9 int bit, bitvalue, value, i, index;10 11 /* 分配计数数组counts的存储空间 */12 if((counts = (int*)malloc(radix * sizeof(int))) == NULL)13 return -1;14 15 /* 分配存储排序后元素的临时空间 */16 if((temp = (int*)malloc(size * sizeof(int))) == NULL)17 return -1;18 19 /* 从最低有效位到最高有效位依次进行计数排序 */20 for(bit = 0; bit < bits; bit++)21 {22 /* 分离有效位 */23 bitvalue = (int)pow((double)radix, (double)bit);24 25 /* 初始化counts */26 for(value = 0; value < radix; value++)27 counts[value] = 0;28 29 /* 计算每个元素出现的次数 */30 for(i = 0; i < size; i++)31 {32 index = (int)(data[i] / bitvalue) % radix;33 counts[index] = counts[index] + 1;34 }35 36 /* 更新counts数组，使得其值代表对应元素在排序后的偏移量 */37 for(i = 1; i < radix; i++)38 counts[i] = counts[i] + counts[i - 1];39 40 /* 使用更新后counts中的偏移量计算每个元素的正确位置 */41 for(i = size - 1; i >= 0; i--)42 {43 index = (int)(data[i] / bitvalue) % radix;44 temp[counts[index] - 1] = data[i]; /* 多个重复的值总是从后向前依次放置 */45 printf("temp[%d] stores %d\n", counts[index] - 1, data[i]);46 counts[index] = counts[index] - 1;47 }48 49 /* 将排序后的数据集复制到data中 */50 memcpy(data, temp, size * sizeof(int));51 }52 53 free(temp);54 free(counts);55 56 return 0;57 }
2.6 冒泡排序和选择排序
还有两种比较常用的排序方法，分别为冒泡排序和选择排序，如下简单描述：
冒泡排序：
基本思想就是两两比较相邻的元素，如果逆序，则交换位置，最后最小的元素就像气泡一样浮到最上面。为了避免对已然有序的数据集一直执行比较操作，可以设置标志位flag控制循环，如果某次循环存在元素交换，设flag = 1，表明下次仍然需要继续循环比较；如果false = 0，表明剩余元素已然有序，此时排序工作结束。改进后的冒泡排序最好情况下，只需要n-1次比较，时间复杂度为O(n)；在数据集为逆序时，情况最糟糕，为O(n2)。
算法实现：
1 /** 2 bubble_sort(): 3 return: success 0; fail -1 4 */ 5 int bubble_sort(void* data, int size, int esize, 6 int (*compare)(const void* key1, const void* key2)) 7 { 8 char* pd = (char*)data; 9 void* ptemp;10 int num, i;11 int flag = 1;12 13 if((ptemp = (char*)malloc(esize)) == NULL)14 return -1;15 16 for(num = 0; (num < size - 1) && (flag == 1); num++) /* 循环次数 */17 {18 flag = 0; /* 初始化为 0 */19 for(i = size - 2; i >= num; i--)20 {21 if(compare(&pd[i * esize], &pd[(i + 1) * esize]) > 0)22 {23 memcpy(ptemp, &pd[i * esize], esize);24 memcpy(&pd[i * esize], &pd[(i + 1) * esize], esize);25 memcpy(&pd[(i + 1) * esize], ptemp, esize);26 flag = 1;27 }28 }29 }30 free(ptemp);31 32 return 0;33 }
选择排序：
基本思想就是在第num次循环中找出最小的元素与pd[num]进行交换，num范围为[0, size -1)，因为只剩下最后一个元素时，不必再进行选择了。第num次循环中，需要size – 1 – num次比较操作。因此，其时间复杂度为O(n2)。
算法实现：
1 /** 2 select_sort(): 3 return: success 0; fail -1 4 */ 5 int select_sort(void* data, int size, int esize, 6 int (*compare)(const void* key1, const void* key2)) 7 { 8 char* pd = (char*)data; 9 void* ptemp;10 int num, i, min;11 12 if((ptemp = (char*)malloc(esize)) == NULL)13 return -1;14 15 for(num = 0; num < size - 1; num++)16 {17 18 min = num; /* 假设索引为num的元素值最小 */19 for(i = num + 1; i < size; i++)20 {21 if(compare(&pd[min * esize], &pd[i * esize]) > 0)22 min = i;23 }24 if(compare(&min, &num) != 0)25 {26 memcpy(ptemp, &pd[num * esize], esize);27 memcpy(&pd[num * esize], &pd[min * esize], esize);28 memcpy(&pd[min * esize], ptemp, esize);29 }30 }31 free(ptemp);32 33 return 0;34 }
3 性能分析
为了对不同排序算法的性能进行定量分析，采用随机产生的数据集：规模分别为1000、5000、10000、50000。同一规模下的输入数据集分别有随机排序、正序排序、逆序排列三种，输出均为升序排序。运行环境为：处理器 奔腾T4300，主频2.1GHz，内存 2G，编译器 GUN gcc 4.7.1。
表1 随机序列排序耗时
|
| 执行时间 /s | ||||||
| 规模 /个 | 插入排序 | 快速排序 | 归并排序 | 计数排序 | 基数排序 | 冒泡排序 | 选择排序 |
| 1000 | 0.006000 | 0.002000 | 0.001000 | 5.206000 | 5.206000 | 0.016000 | 0.007000 |
| 5000 | 0.149000 | 0.014000 | 0.005000 | 18.132000 | 71.043000 | 0.443000 | 0.133000 |
| 10000 | 0.561000 | 0.023000 | 0.011000 | 34.643000 | 141.395000 | 1.791000 | 0.547000 |
| 50000 | 14.320000 | 0.126000 | 0.057000 | 185.015000 | 888.030000 | 45.331000 | 13.638000 |
表2 正序序列排序耗时
|
| 执行时间 /s | ||||||
| 规模 /个 | 插入排序 | 快速排序 | 归并排序 | 计数排序 | 基数排序 | 冒泡排序 | 选择排序 |
| 1000 | 0.000000 | 0.002000 | 0.001000 | 2.973000 | 9.086000 | 0.010000 | 0.005000 |
| 5000 | 0.000000 | 0.012000 | 0.004000 | 16.025000 | 63.358000 | 0.085000 | 0.130000 |
| 10000 | 0.001000 | 0.024000 | 0.010000 | 32.207000 | 128.935000 | 0.222000 | 0.522000 |
| 50000 | 0.004000 | 0.130000 | 0.044000 | 178.152000 | 938.841000 | 1.680000 | 13.425000 |
表3 逆序序列排序耗时
|
| 执行时间 /s | ||||||
| 规模 /个 | 插入排序 | 快速排序 | 归并排序 | 计数排序 | 基数排序 | 冒泡排序 | 选择排序 |
| 1000 | 0.010000 | 0.002000 | 0.002000 | 3.247000 | 10.031000 | 0.022000 | 0.007000 |
| 5000 | 0.285000 | 0.014000 | 0.004000 | 17.477000 | 70.101000 | 0.561000 | 0.194000 |
| 10000 | 1.155000 | 0.025000 | 0.008000 | 35.476000 | 141.936000 | 2.239000 | 0.751000 |
| 50000 | 29.223000 | 29.223000 | 0.048000 | 198.325000 | 806.668000 | 58.161000 | 20.617000 |
如表1所示，在数据集规模比较小时，选择任何一种算法来进行排序，其性能都不会有太大的差别；随着输入数据规模的扩大，快速排序和归并排序表现优秀，插入排序和选择排序性能受到一定的影响；冒泡排序不适合用于大规模排序任务。表2为对正序数据集进行排序的时间开销，一般而言，好的排序算法对于已经有序的序列应该立刻给出响应，不需要再次重新排序，插入算法完美地解决了这个问题，其他算法如快速排序、归并排序、冒泡排序等也比较适合这种工作；对于数据规模比较大时，选择排序会做一些无用的工作。表3中，归并排序对于任何规模的逆序数据集性能优越，显然插入排序、快速排序、选择排序、冒泡排序不适合大规模的逆序数据集。总结一下，无论是随机、正序、逆序、甚至不同规模，归并排序总能得到最佳的性能，而快速排序只是对于大规模逆序集不太适应，其他情况同样优秀。同样值得一提的是，在预先得知数据序列大部分有序的情况下，插入排序也是一个很好的选择。从表1，表2，表3中得出一个结论，对于随机、正序、逆序数据集，计数排序和基数排序的性能几乎总是一样的，这是由于这两种排序的方式并不依赖于比较操作，因此，其并不受序列是否有序的影响，只依赖于数据集的规模大小。之所以上述实验中这两种排序方式的时间开销最大，是因为对于整型我们习惯性地选择了10作为基数，但是计算机却是以2进制为基的，因此可以采用2的幂次作为基数，这样在分离不同的位时就可以避免乘除操作而采用位运算以提高速度。但是计数排序和基数排序的复杂度是线性增长的，如果数据规模超级大，此时和其他排序算法的性能差距必然会越来越小，甚至超过其他算法。
对算法的定性评价主要是基于两条标准：时间复杂度和空间复杂度。如果算法所需的额外空间不依赖于数据集的规模，则认为其辅助空间为O(1)，此时称之为原地排序，比如：插入排序、冒泡排序、选择排序；而对于归并排序、计数排序、基数排序而言，也需要O(n)量级的辅助空间；对快速排序进行改进后，可能需要O(lgn)的空间即可完成工作了。下面总结了不同算法的定性比较：
| 排序算法 | 空间复杂度S(n) | 最坏时间复杂度T(n) | 平均时间复杂度T(n) |
| 插入排序 | O(1) | O(n2) | O(n2) |
| 快速排序 | O(lgn) | O(n2) | O(nlgn) |
| 归并排序 | O(n) | O(nlgn) | O(nlgn) |
| 计数排序 | O(n) | O(n + p) | O(n + p) |
| 基数排序 | O(n) | O(b(n + r)) | O(b(n + r)) |
| 冒泡排序 | O(1) | O(n2) | O(n2) |
| 选择排序 | O(1) | O(n2) | O(n2) |
4 结论
实际中如何选择合适的算法时，不能单纯地依赖于算法的复杂度分析，更重要的是要考虑具体应用到哪个数据集上，实验数据表明，在数据规模比较小时，任何算法都可以看作是等价的。但是对于大规模数据集，必须全面衡量排序算法的选择。同时，一个算法的设计不能仅仅依赖于实现功能即可，对于关键部分必须进行优化设计才能很好地发挥其作用。
附表（上述排序中用到的额外操作）
1 /** 2 比较两个int的大小（正序） 3 */ 4 int compare_int(const void* key1, const void* key2){ 5 return *(const int*)key1 < *(const int*)key2 ? -1 : 6 *(const int*)key1 > *(const int*)key2 ? 1 : 0; 7 } 8 9 /**10 比较两个int的大小（逆序）11 */12 int compare_int_reverse(const void* key1, const void* key2){13 return *(const int*)key1 > *(const int*)key2 ? -1 :14 *(const int*)key1 < *(const int*)key2 ? 1 : 0;15 }16 17 /**18 打印int型数组19 */20 void print_arr(const void* arr, int size)21 {22 const int* pint = (const int*)arr;23 int i;24 for(i = 0; i < size; i++)25 {26 printf("%d ", pint[i]);27 }28 printf("\n");29 }