如题，一些常用的内部排序算法。
所谓内部排序也就是排序之前需要把所有的数据都一次性读入内存，适用于小数据量（不会导致内存条爆炸）的排序。
关于排序算法的复杂度分析自己看了挺久才迷迷糊糊的懂了，数学不好是硬伤啊，各种公式纠结了很久……
话说回来，程序共演示了4 种排序算法，具体请查看相应的函数，对于算法的思想和流程注释里都有详尽的描述：
doQuickSort： 该函数演示了快速排序算法，使用递归完成。
doHeapSort：该函数演示了（大根）堆排序算法，其中使用doHeapSortAdjust 函数来进行（大根）堆调整。
doMergeSort：该函数演示了归并排序算法，对数据递归分割后进行二路归并，其中使用doMerge 函数归并两个有序列表。
doInsertSort：该函数演示了插入排序算法，其中插入位置的确定使用折半查找代替了通常使用的顺序查找，事实证明折半算法的使用能够极大的减少插入排序过程的运行时间（虽然还是很长……）。
下面是一个演示程序的使用方法：
下面是四种排序算法的时间评测：
上图中四种算法测评的输入数据是同一个33.5 MiB 的文本文件，其中包含大约46 万个长度不等的字符串，大约3300 万个字符。
四种排序算法的实际排序时间如下（user + system）：
快速排序：1.50 秒
堆排序： 0.82 秒
归并排序：0.34 秒
插入排序：71.55 秒
演示代码如下：
/*
* 文件名：sort.c
* 编译方法：gcc -O3 sort.c -o sort
* 使用方法：./sort --help
* 内部排序算法集合，包括：
* 1. 堆排序
* 2. 插入排序
* 3. 快速排序
* 4. 归并排序
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
/*
* 调试输出宏：
* DEBUG 宏设置非0 为非调试状态，不执行调试语句；
* DEBUG 宏设置为1 为调试状态，执行调试语句。
*/
#ifdef DEBUG
#undef DEBUG
#endif
#define DEBUG 0
#if 1 == DEBUG
#define DO_DEBUG(s) {s;}
#else
#define DO_DEBUG(s)
#endif
typedef char *string;
typedef enum
/* 文件读入 管道读入 */
{ FILE_MODE, PIPE_MODE, } IOMode;
typedef enum
/* 插入排序 快速排序 归并排序 堆排序 */
{ INSERT_SORT, QUICK_SORT, MERGE_SORT, HEAP_SORT, } SortMode;
/* 让strcmp 函数的行为符合正常思维 */
#define STRCMP(a,r,b) (strcmp((a),(b)) r (0))
/* 待排序和排序之后的若干字符串 */
string *toSort = NULL;
/*
* 从管道或者文件中读入数据
*/
bool
readIn (IOMode mode, string fileInName)
{
size_t size = 0, begin = 0, end = 0;
size_t stringCount = 0, stringNumber = 0;
FILE *fileIn = NULL;
string in = NULL, inTemp = NULL;
/*
* 设置数据源数据
*/
if (PIPE_MODE == mode)
{
/* 数据源为管道 */
fileIn = stdin;
}
else if (FILE_MODE == mode)
{
/* 数据源为文件 */
if (!(fileIn = fopen (fileInName, "r")))
{
perror ("fopen ():");
return false;
}
}
else
{
/* 不能解析的参数 */
fprintf (stderr, "Unkown arg in readIn (), exit!\n");
exit (EXIT_FAILURE);
}
DO_DEBUG (printf ("输入设置完成。\n"));
/*
* 开始读入数据到inTemp
* 每次读入1<<16 字节
* 防止读入串的字数过长导致溢出或者不全
* 其后会对其进行处理并分割出字符欻
*/
if (fileIn)
{
size = 1 << 16;
begin = 0;
in = (string) malloc (size);
size = fread (in, sizeof (char), size, fileIn);
end = size;
inTemp = (string) malloc (size);
while (0 < size)
{
memcpy (&inTemp[begin], in, size);
begin += size;
size = fread (in, sizeof (char), size, fileIn);
end += size;
inTemp = (string) realloc (inTemp, end);
}
}
/*
* 文件指针设置失败则报错并退出
*/
else
{
fprintf (stderr, "Unset FILE pointer in readIn (), exit!\n");
return false;
}
DO_DEBUG (printf ("读入数据完成\n"));
/*
* 根据换行符分割字符串到toSort
* toSort 数组中每一个指针指向一个分割后的字符串
* inTemp 在过程完成之后销毁
*/
size = end;
begin = 0;
stringCount = 0;
stringNumber = 1 << 10;
toSort = (string *) malloc (stringNumber * sizeof (string *));
/* 默认把指针设置为空以标记结尾 */
memset (&toSort[stringCount], 0, stringNumber - stringCount);
for (end = 0; end < size; ++end)
{
if (‘\n‘ == inTemp[end])
{
/* 在需要的时候按照倍数扩充指针数组 */
if (stringNumber == stringCount)
{
stringNumber *= 2;
toSort =
(string *) realloc (toSort, stringNumber * sizeof (string *));
/* 指针默认设置为空以标记结尾 */
memset (&toSort[stringCount], 0, stringNumber - stringCount);
}
/* 2: ‘\n‘+‘\0‘ */
toSort[stringCount] = (string) malloc (end - begin + 2);
memcpy (toSort[stringCount], &inTemp[begin], end - begin + 1);
/* 随后加上结尾 */
toSort[stringCount][end - begin + 1] = ‘\0‘;
begin = end + 1;
++stringCount;
}
}
/*
* 如果toSort 分配的空间恰好被全部用光
* 再其后设置一个NULL 指针用来标记结束
*/
if (stringCount == stringNumber)
{
toSort =
(string *) realloc (toSort, (stringNumber + 1) * sizeof (string *));
toSort[stringNumber] = 0;
}
DO_DEBUG (printf ("分割数据完成。\n"));
DO_DEBUG (printf
("分割后的字符串个数：%d\n循环遍历的字符个数：%d\n",
stringCount, end));
/*
* 如果FILE_MODE == ioMode 则关闭打开的文件
*/
if (stdin != fileIn)
{
fclose (fileIn);
}
free (in);
free (inTemp);
return true;
}
/*
* 快速排序，时间复杂度为O(nlogn)，不稳定排序
* 参数为有符号型
* 算法思想：
* 不断的重复一个递归过程，使得列表为有序
* 递归过程为：
* 将第0 个位置的元素设为key，定位和交换数据
* 使得key 左边的元素均不大于key
* 使得key 右边的元素均不小于key
*/
bool
doQuickSort (ssize_t begin, ssize_t length)
{
ssize_t left = 0, right = 0;
string key = NULL;
/*
* 每次将第一个元素作为关键字来分割数组
* 使得左边的元素都小于关键字
* 右边的元素都大于关键字
*/
left = begin;
right = length - 1;
key = toSort[begin]; /* 排序范围内的第一个元素作为Key */
/*
* 循环交换数据使得小者在左大者在右
* 其中交换数据利用一次递归中长度的第一个位置进行
*/
while (left < right)
{
/* 定位到右边小于Key 的位置 */
while ((left < right) && STRCMP (toSort[right], >, key))
{
--right;
}
/* 将这个位置的元素换到左边已保存数据的位置 */
if (left < right)
{
toSort[left] = toSort[right];
++left;
}
/* 定位到左边大于key 的位置 */
while ((left < right) && STRCMP (toSort[left], <, key))
{
++left;
}
/* 将这个位置的元素换到右边已保存数据的位置 */
if (left < right)
{
toSort[right] = toSort[left];
--right;
}
}
/*
* 将key 插入到元素数组当中left 的位置（循环结束后left <= right）
* 此时元素数组被分割为两部分
* key 左边的元素均不大于key，key 右边的元素均不小于key
*/
toSort[left] = key;
DO_DEBUG (printf ("key 被设定到位置：%5d\n", right));
/*
* 递归整个过程，不断分割元素数组
* 使得每次处理的长度中均用key 把元素数组分割为两部分
* 直到递归到足够小的规模，该递归的输入序列就已经是有序的
* 递归结束后整个序列也变为有序的
*/
if (right - 1 > begin)
{
doQuickSort (begin, right);
}
if (length - 1 > right + 1)
{
doQuickSort (right + 1, length);
}
return true;
}
/*
* 插入排序，时间复杂度为O(n^2)，稳定排序
* 算法思想：
* 把第0 个元素当作只有一个元素的有序表
* 重复一个循环过程，使得列表整体变为有序
* 该循环过程为：
* 每次将有序表其后的一个元素插入有序表中合适的位置
* 使得有序表的长度加一
*/
bool
doInsertSort (size_t length)
{
ssize_t left = 0, right = 0, middle = 0;
int compairResult = 0;
ssize_t count = 0, count2 = 0;
string key = NULL;
/*
* 从1 开始逐渐增加有序表的长度
* 直到有序表的长度和待排序的元素数量相同
* key 为待决定插入位置的元素
*/
for (count = 1; count < length; ++count)
{
key = toSort[count];
left = 0; /* 有序表头 */
right = count - 1; /* 有序表尾 */
/*
* 二分法快速寻找合适的插入点
* 当key 和middle 位置的元素不相等时循环查找
* 直到找到一个相等或者合适的位置
*/
while (left <= right)
{
middle = (left + right) / 2;
compairResult = strcmp (key, toSort[middle]);
/* key 小于middle 位置的元素，重新设定查找范围的右侧 */
if (compairResult < 0)
{
right = middle - 1;
}
/* 大于重新设置左侧 */
if (compairResult > 0)
{
left = middle + 1;
}
}
/*
* 找到合适的位置后
* 从middle 到count-1 的列表整体后移一个位置
* 之后插入key
*/
for (count2 = count - 1; count2 > middle - 1; --count2)
{
toSort[count2 + 1] = toSort[count2];
}
/*
* 插入key 并增加有序表的长度
* 此时left == right + 1
*/
toSort[left] = key;
DO_DEBUG (printf
("第%5d 个元素被插入到位置%5d \n", count, middle));
}
return true;
}
/*
* 堆调整函数，用于堆排序
* 调整无序部分为大根堆，使得：
* toSort[n] 不小于 toSort[2 * n]
* toSort[n] 不小于 toSort[2 * n + 1]
* key 为等待调整元素的位置
*/
bool
doHeapSortAdjust (size_t key, size_t length)
{
ssize_t child = 0;
string temp = NULL;
DO_DEBUG (printf
("正在调整的无序表范围：%5d到 %5d\n", key,
length - 1));
/*
* 右孩子为2*key+1，如果不是子节点则不用调整
* 不断把孩子中的较大者和父节点交换
* temp 中临时储存父节点，用于其后的子、父节点交换
*/
for (; 2 * key + 1 < length; key = child)
{
/* child 首先定位到左孩子 */
child = 2 * key;
/* 定位child 到孩子中的较大者 */
if ((child < length - 2)
&& (STRCMP (toSort[child], <, toSort[child + 1])))
{
++child;
}
/* 如果子节点大于父节点则交换两个节点 */
if (STRCMP (toSort[key], <, toSort[child]))
{
temp = toSort[key];
toSort[key] = toSort[child];
toSort[child] = temp;
doHeapSortAdjust (key, length);
}
/* 否则跳出循环 */
else
{
break;
}
}
return true;
}
/*
* 堆排序，时间复杂度O(nlogn)，不稳定排序
* 算法思想：
* 利用大根堆的堆顶元素为最大的关键字这一特性
* 首先将初始无序表构建成一棵大根堆
* 重复一个过程，直到有序表的长度为原始表长度减一，此时列表全部有序
* 该过程为：
* 将堆顶元素和最后的元素交换位置
* 此时无序表的长度减一，有序表的长度自后往前加一
* 防止交换造成大根堆性质的破坏，重新将无序区构造为大根堆
*/
bool
doHeapSort (size_t length)
{
string temp = NULL;
ssize_t count = 0;
/*
* length / 2 - 1 为第一个非子叶节点
* 不断把父节点当作key 进行调整以建立大根堆
*/
for (count = length / 2 - 1; count > -1; --count)
{
doHeapSortAdjust (count, length);
}
for (count = length - 1; count > 0; --count)
{
/*
* 交换元素使得有序表的长度加一
*/
temp = toSort[count];
toSort[count] = *toSort;
*toSort = temp;
/* 重新调整无序表为大根堆 */
doHeapSortAdjust (0, count + 1);
}
return true;
}
/*
* 归并函数，把两个有序表合成为一个有序表
* 需要额外的同等大小的内存空间做辅助
* PS：此处额外空间是指针数组的空间
* 而不包括字符串本身占据的空间
*/
bool
doMerge (string * firstPart, size_t firstPartLength, string * secondPart,
size_t secondPartLength)
{
size_t count1 = 0, count2 = 0, count3 = 0;
string *temp = NULL;
temp =
(string *) malloc ((firstPartLength + secondPartLength) *
sizeof (string *));
count1 = count2 = count3 = 0;
/*
* 合并两个字串，直到某一个字串达到尾部
*/
while ((count1 < firstPartLength) && (count2 < secondPartLength))
{
/*
* 因为是升序排序，小者先入临时数组
*/
if (STRCMP (firstPart[count1], <, secondPart[count2]))
{
temp[count3] = firstPart[count1];
++count1;
}
else
{
temp[count3] = secondPart[count2];
++count2;
}
/* 定位到下一个移动位置 */
++count3;
}
/*
* 把未处理完的串的剩余部分移动到&temp[count3] 开始的位置
* 注意下面两个while 循环有且只有一个会被执行
*/
while (count1 < firstPartLength)
{
temp[count3] = firstPart[count1];
/* 下一次移动位置定位 */
++count1;
++count3;
}
while (count2 < secondPartLength)
{
temp[count3] = secondPart[count2];
/* 下一次移动位置定位 */
++count2;
++count3;
}
/*
* 把temp 中的数据复制到firstPart
* 注意firstPart 和secondPart 在内存中相邻
* 所以这样复制也就是说把有序数组覆盖了原本的无序数组
*/
memcpy (firstPart, temp,
(firstPartLength + secondPartLength) * sizeof (string));
free (temp);
return true;
}
/*
* 归并排序，时间复杂度O(nlogn)，为稳定排序
* 排序思想：
* 先*归*再*并*，不断的递归分割无序表
* 直到分割为单个元素，这时每个子表（只含一个元素）都是有序的
* 对字表进行归并，逐步合成有序表
* 直到合成后有序表的长度等于起初无序表的长度
* 这时整个表变为有序
*/
bool
doMergeSort (string * toSort, size_t length)
{
string *firstPart = NULL;
string *secondPart = NULL;
size_t firstPartLength = 0;
size_t secondPartLength = 0;
/*
* 如果多余一个元素才进行归并，否则返回
*/
if (length > 1)
{
/* 将toSort 分为两个部分 */
firstPart = toSort;
firstPartLength = length / 2;
secondPart = &toSort[length / 2];
secondPartLength = length - firstPartLength;
/* 分别进行递*归*分割 */
doMergeSort (firstPart, firstPartLength);
doMergeSort (secondPart, secondPartLength);
DO_DEBUG (printf
("合并的长度为：%5d到 %5d\n", firstPartLength,
length));
/* 然后进行合*并* */
doMerge (firstPart, firstPartLength, secondPart, secondPartLength);
}
return true;
}
/*
* doSort 函数，执行排序动作
* 具体算法会根据sortMode 设置
*/
bool
doSort (SortMode sortMode)
{
size_t length = 0;
/*
* 确定待排序的字符串数量
*/
for (length = 0; toSort[length]; ++length);
DO_DEBUG (printf ("待排序的字符串个数：%d\n", length));
DO_DEBUG (printf ("排序模式：%d\n", sortMode));
/*
* 根据参数执行相应排序过程
*/
switch (sortMode)
{
/* 快速排序 */
case QUICK_SORT:
if (!doQuickSort (0, length))
{
return false;
}
break;
/* 插入排序 */
case INSERT_SORT:
if (!doInsertSort (length))
{
return false;
}
break;
/* 归并排序 */
case MERGE_SORT:
if (!doMergeSort (toSort, length))
{
return false;
}
break;
/* 堆排序 */
case HEAP_SORT:
if (!doHeapSort (length))
{
return false;
}
break;
/* 无法解析的参数 */
default:
fprintf (stderr,
"EE: In doSort ()，不能解析的参数，退出！\n");
return false;
}
return true;
}
/*
* printResult 函数打印结果到stdout
*/
void
printResult (void)
{
size_t stringCount = 0;
/*
* 在遇到NULL 之前打印所有的字符串
*/
for (stringCount = 0; toSort[stringCount]; ++stringCount)
{
printf ("%s", toSort[stringCount]);
}
return;
}
/*
* 打印帮助
*/
void
printHelp (void)
{
puts ("用法：./sort [参数]");
puts
("\t程序默认从标准输入读入，并接受到文件结束符后执行快速排序并打印结果");
puts ("参数：");
puts ("\t-mode：指定排序模式，其中");
puts ("\t\tis 为插入排序");
puts ("\t\tqs 为快速排序");
puts ("\t\tms 为归并排序");
puts ("\t\ths 为堆排序");
puts ("\t\t未指定或未知的参数默认执行快速排序");
puts ("\t-file：指定从文件中读入数据，后跟文件名\n");
puts ("可能的示例：");
puts
("\t从管道中读入find 的结果对其进行快速排序并输出");
puts ("\t\tfind . | ./sort -mode qs");
puts
("\t读入文件fileIn 的数据并对其进行归并排序后输出结果到文件fileOut");
puts ("\t\t./sort -file fileIn -mode ms > fileOut\n");
puts
("!!注意：这并不是一个实用程序，只是为了演示排序算法，请勿用于任何实际工作！");
puts ("\t\t\t\t\t\t\t—— by iSpeller");
return;
}
/*
* MAIN: Fast is Good ;)
*/
int
main (int argc, char *argv[])
{
size_t count = 0;
IOMode ioMode = -1; /* 数据读入模式 */
SortMode sortMode = -1; /* 排序模式 */
string fileInName = (string) malloc (1 << 9);
/*
* 扫描参数列表，默认从stdin 读入数据，使用快速排序
*/
ioMode = PIPE_MODE;
sortMode = QUICK_SORT;
for (count = 1, ioMode = PIPE_MODE; count < argc; ++count)
{
/*
* 检查是否指定从文件读入数据
*/
if (STRCMP (argv[count], ==, "-file"))
{
ioMode = FILE_MODE;
++count;
if (!argv[count])
{
fprintf (stderr, "EE: -file 参数之后未找到文件名.\n");
return 1;
}
strncpy (fileInName, argv[count], strlen (argv[count]));
continue;
}
/*
* 检查排序算法的设置，默认为快速排序
*/
if (STRCMP (argv[count], ==, "-mode"))
{
++count;
/* 未指定排序模式仍然使用默认的快速排序 */
if (!argv[count])
{
sortMode = QUICK_SORT;
continue;
}
/* is 匹配插入排序 */
else if (STRCMP (argv[count], ==, "is"))
{
sortMode = INSERT_SORT;
}
/* ms 匹配归并排序 */
else if (STRCMP (argv[count], ==, "ms"))
{
sortMode = MERGE_SORT;
}
/* hs 匹配堆排序 */
else if (STRCMP (argv[count], ==, "hs"))
{
sortMode = HEAP_SORT;
}
/* qs 和其他任何情况都使用快速排序 */
else
{
sortMode = QUICK_SORT;
}
continue;
}
/*
* 匹配--help 参数,当发现--help 参数时
* 停止一切工作，打印帮助信息并退出程序
*/
if (STRCMP (argv[count], ==, "--help"))
{
printHelp ();
return 0;
}
}
/*
* 读入待排序的数据
*/
if (!readIn (ioMode, fileInName))
{
fprintf (stderr, "EE: In readIn ()，读入数据失败，退出!\n");
return 1;
}
/*
* 依照指定的算法执行排序动作
*/
if (!doSort (sortMode))
{
fprintf (stderr, "EE: In doSort ()，排序过程失败，退出！\n");
return 1;
}
/*
* 打印排序的结果
*/
printResult ();
free (fileInName);
free (toSort);
return 0;
}