分类： C/C++
2010-06-14 00:39:30
首先，对大多数包含排序应用的程序来说，排序算法的速度并不重要，因为在程序中排序 的工作量并不是很多，或者，与排序相比，程序中其它操作所花费的时间要多得多。
实际上，没有哪一种排序算法永远是最快的，在运行程序的软硬件环境相同的情况下，不同排序算法的速度还与数据的长度、性质以及数据的初始顺序有关。
在笔者的“工具箱”中，有三种算法在不同的情况下都是最快、最有用的，这三种算法分别是快速排序、归并排序和基数排序。
快速排序
快速排序是一种分割处理式的排序算法，它将一个复杂的排序问题分解为若干较容易处理的排序问题，然后逐一解决。在快速排序算法中，首先要从数据集的数据中选择一个数据作为分割值，然后将数据分成以下3个子集：
(1) 将大于分割值的数据移到分割值前面，组成子集1；
(2) 分割值本身为子集2；
(3) 将小于分割值的数据移到分割值后面，组成子集3。
等于分割值的数据可以放在任意一个子集中，这对快速排序算法没有任何影响。
由于子集2已经是有序的，所以此后只需对子集1和子集3进行快速排序。
需要注意的是，当数据集很小时，无法进行快速排序，而要使用其它排序算法。显然，当数据集中的数据只有两个或更少时，就不可能将数据集再分割成三个子集。实际上，当数据集比
较小时，程序员就应该考虑是否仍然采用快速排序算法，因为在这种情况下另外一些排序算法往往更快。
例3. 2a用快速排序算法重写了例3．1中的字符串数组排序程序，你同样可以将它和本章末尾的有关代码一起编译成一个可执行程序。程序中定义了一个宏，它可使程序更易读，并能加快执行速度。
快速排序算法是由程序中的myQsort()函数实现的，它是按升序对一个字符串数组进行排序的。函数myQsort()的具体工作过程如下：
(1)首先检查最简单的情况。在第17行，检查数组中是否没有或只有一个元素——在这种情况下，数组已经是有序的，函数就可以返回了。在第19行，检查数组中是否只有两个元素——在这种情况下，要么数组已经是按升序排列的，要么交换这两个元素的位置，使它们按升序排列。
(2)在第28行至第53行，将数组分割为两个子集：第一个子集中的数据大于或等于分割值，第二个子集中的数据小于分割值。
在第28行，选择数组中间的元素作为分割值，并将其和数组中的第一个元素交换位置。
在第37行至第39行，在数组中找到属于第二个子集的第一个元素；在第45行至第47行，在数组中找到属于第一个子集的最后一个元素。
在第49行，检查属于第二个子集的第一个元素是否位于属于第一个子集的最后一个元素的后面，如果是，则第一个子集的所有元素都已在第二个子集的所有元素的前面，数据已经划分好了；否则，交换这两个元素的位置，然后重复上述这种检查。
(3)当两个子集分割完毕后，在第55行，将分割值和第一个子集中的最后一个元素交换位置，排序结束时这个分割值将仍然排在现在这个位置。在第57行和第58行，分别调用myQsort()函数对分割所得的子集进行排序。当所有的子集都经过排序后，整个数组也就排好序了。
例3. 2a一个不使用qsort()函数的快速排序算法程序
1: #include
2:
3: #define exchange(A, B, T) ((T) = (A), (A) = (B),(B)=(T))
4:
5:
6: / * Sorts an array of strings using quick sort algorithm * /
7: static void myQsort(const char * array[], size_t num)
8: {
9: const char * temp
10: size_t i, j;
11:
12: /*
13: * Check the simple cases first:
14: * If fewer than 2 elements, already sorted
15: * If exactly 2 elements, just swap them (if needed).
16: * /
17: if (num <2)
18: return;
19: else if (num==2)
20: {
21: if (strcmp(array[O], array[1])>O)
22: exchange (array[0], array[1] ,temp)
23: }
24: / *
25: * Partition the array using the middle (num/2)
26: element as the dividing element.
27: * /
28: exchange (array[0], array[num / 2], temp)
29: i=1;
30: j=num;
31: for (; ;)
32: {
33: / *
34: * Sweep forward until and element is found that
35: * belongs in the second partition.
36: * /
37: while (i
38: <=0)
39: i++;
40: / *
41: * Then sweep backward until an element
42: * is found that belongs in the first
43: * partition.
44: * /
45: while (i
46: >=0)
47: j--;
48: / * If no out-of-place elements, you're done * /
49: if (i>=j)
50: break
51: / * Else, swap the two out-of-place elements * /
52: exchange(array[i], array[j-l], temp)
53: }
54: / * Restore dividing element * /
55: exchange(array[O], array[i-1], temp)
56: / * Now apply quick sort to each partition * /
57: myQsort (array, i-1 )
58: myQsort (array + i, num-i)
59: }
60:
61: / * Sort strings using your own implementation of quick sort * /
62: void sortStrings (char * array[])
63: {
64: / * First, determine the length of the array * /
65: int num
66:
67: for (num = O; array[num] ; num++ )
68:
69: myQsort((void * ) array, num)
70: }
归并排序也是一种分割处理式的排序算法，它是由Johnyon Neumann于1945年提出的。
在归并排序算法中，将待排序数据看作是一个链表序列，每个链表(最坏的情况下每个链表中只有一个元素)中的数据都已经排好序，然后不断地将相邻的链表合并为一些较大的链表，当所有的链表都合并为一个链表时，排序过程也就结束了。归并排序算法特别适合于对键表或其它非数组形式的数据结构进行排序，它还能对无法放入内存的数据进行排序；或者被作为一种特定的排序算法来使用。
例3．2b是实现归并排序算法的一个例子，你可以将它和本章结尾的有关代码一起编译成一个可执行程序。有关list_t类型及其操作函数的代码也已在本章末尾列出。
在例3．2b中，字符串被存放在一个链表中，而不是一个数组中。实际上，将数据组织为链表后更利于归并排序算法对其进行处理，因为数组中的元素是无法合并的，除非利用另外分配的内存空间。
例3．2b通过以下4个函数共同实现归并排序算法：
(1)split()函数
split()函数将一个字符串链表分割为一个由多个字符串链表组成的链表，其中每一个字符串链表都已经是排好序的。例如，如果初始链表为("the" "quick""brown" "fox")，则split()函数将返回一个由3个链表组成的链表，这3个链表分别为(“the”)，("quick”)和("brown”“fox”)。因为字符串“brown”和“fox”已经是排好序的，所以它们被放到一个链表中。
尽管split()函数将初始链表分割为一系列只含一个数据的链表后，本例的排序算法仍然能很好地执行，但是，如果初始链表中的数据已经接近有序，那么在分割初始链表时，将相邻的有序数据放到同一个链表中，就能大大减少以后的工作量，从而使本例的排序算法成为自然的排序算法(见本章开始部分中的介绍)。
当输入链表不为空时，程序第14—24行的循环将一直进行下去。在每次循环中，程序第16行将构造一个新的链表；第17—22行将把输入链表中的元素不断地移到所构造的链表之中，直到处理完输入链表中的所有元素，或者检查到两个无序的元素；第23行将把所构造的链表添加到输出链表(它的数据也是链表)中。
(2)merge()函数
merge()函数将两个数据已经有序的链表合并为一个数据有序的链表。
当正在合并的两个链表都不为空时，程序第37—45行的循环将一直进行下去。第40行的if 语句将比较两个链表中的第一个元素，并把较小的元素移到输出链表中。当正在合并的两个链表中有一个为空时，另一个链表中的元素必须全部添加到输出链表中。第46行和第47行将已为空的链表和另一个链表与输出链表链接上，从而结束整个合并过程。
(3)mergePairs()函数
通过调用merge()函数，mergePairs()函数分别对一个由字符串链表组成的链表中的每个对链表进行合并，并用合并所得的链表代替原来的那对链表。
当输入链表不为空时，程序第61—77行的循环将一直进行下去。第63行的if语句检查输入链表中是否至少有两个字符串链表，如果没有，第76行就把这个单独的链表添加到输出链表中；如果有，第65行和第66行将从输入链表中选出头两个链表，第68行和69行将合并这两个链表，第72行将把合并所得的链表添加到输出链表中，第70行、第71行和第73行将释放所分配的过渡性结点，第72行和第73行将从输入链表中删去头两个链表。
(4)sortStrings()函数
sonStrings()函数对一个字符串数组进行归并排序。
程序第88行和第89行将字符串数组转换为一个字符串链表。第90行调用split()函数将初始链表分割为一个由字符串链表组成的链表。第91行和第92行调用mereePairs()函数将分割所得的链表中的所有字符串链表合并为一个字符串链表。第93行检查合并所得的链表是否为空(当原来的字符串数组中只有。个元素时该链表为空)，若不为空，才能将该链表从分割所得的链表中移出。
需要注意的是，sortStrings()函数没有释放它所用过的内存。
例3．2b一个归并排序算法程序
1. #include
2: #include "list.h"
3:
4: /*
5: * Splits a list of strings into a list of lists of strings
6: * in which each list of strings is sorted.
7: */
8: static list-t split(list_t in)
9: {
10: list-t out
11: list-t * curr;
12: out. head=out, tail=NULL;
13:
14: while (in. head)
15: {
16: curr =newList();
17: do
18: {
19: appendNode (curr, removeHead (&in));
20: }
21: while (in. head && strcmp (curr->tail->u. str,
22: in. head->u.str) < = 0);
23: appendNode(&out, newNode(curr));
24: }
25: return Out;
26: }
27:
28: /*
29: * Merge two sorted lists into a third sorted list,
30: *.which is then returned.
31: * /
32: static list_t merge (list_t first, list_t second)
33: {
34: list_t out;
35: out.head=out, tail=NULL;
36:
37: while (first. head && second, head)
38: {
39: listnode_t * temp;
40: if (strcmp (first. head->u.str,
41: second. head->u.str) <=0)
42: appendNode(&out, removeHead(&first));
43: else
44: appendNode (&out, removeHead (&second));
45: }
46: concatList (&out, &first);
47: concatList (&out, &second);
48: return out;
49: }
50:
51: /*
52: * Takes a list of lists 0{ strings and merges'each pair of
53: * lists into a single list. The resulting list has 1/2 as
54: * many lists as the original.
55: * /
56: static list_t mergePairs(list_t in)
57: {
58: list_ t out;
59: out. head:out, tail=NUll;
60:
61: while (in. head)
62: {
63: if (in. head->next)
64: {
65: list_t * first =in. head->u.list;
66: list_t * second;
67: in.head->next->u.list
68: in. head->u.list = copyOf (merge ( * first,
69: * second));
70: free (first);
71: free (second);
72: appendNode (&out, removeHead (&in))
73: free (removeHead (&in));
74: }
75: else
76: appendNode (&out, removeHead (&in));
77: }
78: return out
79: }
80:
81: / * Sort strings using merge sort * /
82: void sortStrings (const char * array[])
83: {
84: int i;
85: list_t out;
86: out.head=out, tail=NULL;
87:
88: for (i=0; array[i]; i++)
89: appendNode(&out, newNode((void * ) array[i]))
90: out= split (out);
91: while (out.head ! =out.tail)
92: out = mergePairs (out);
93: if (out.head)
94: out = * out.head->u.list;
95: for (i=O; array[i]; i++)
96: array[i] = removeHead (&out)->u.str;
97: }
